These notes are intended for use by students in CS1501 at the University of Pittsburgh and no one else
These notes are provided free of charge and may not be sold in any shape or form
These notes are NOT a substitute for material covered during course lectures. If you miss a lecture, you should definitely obtain both these notes and notes written by a student who attended the lecture.
Material from these notes is obtained from various sources, including, but not limited to, the following:
Algorithms in C++ by Robert Sedgewick
Introduction to Algorithms, by Cormen, Leiserson and Rivest
Various Java and C++ textbooks
Goals of Course
Definitions:
Offline Problem:
We provide the computer with some input and after some time receive some acceptable output
Algorithm
A step-by-step procedure for solving a problem or accomplishing some end
Program
an algorithm expressed in a language the computer can understand
Note how drastic some of the differences are for large problem sizes
Algorithm Analysis
Consider 2 choices for a programmer
Implement an algorithm, then run it to find out how long it takes
Determine the asymptotic run-time of the algorithm, then, based on the result, decide whether or not it is worthwhile to implement the algorithm
Which choice would you prefer?
Discuss
Exhaustive Search
Idea:
We find a solution to a problem by considering (possibly) all potential solutions and selecting the correct one
Run-time:
The run-time is bounded by the number of possible solutions to the problem
If the number of potential solutions is exponential, then the run-time will be exponential
Exhaustive Search
Example: Hamiltonian Cycle
A Hamiltonian Cycle (HC) in a graph is a cycle that visits each node in the graph exactly one time
See example on board and on next slide
Note that an HC is a permutation of the nodes in the graph (with a final edge back to the starting vertex)
Thus a fairly simple exhaustive search algorithm could be created to try all permutations of the vertices, checking each with the actual edges in the graph
See text Chapter 44 for more details
Exhaustive Search
A
G
F
E
C
B
D
Hamiltonian Cycle Problem
A solution is:
ACBEDGFA
Exhaustive Search
Unfortunately, for N vertices, there are N! permutations, so the run-time here is poor
Pruning and Branch and Bound
How can we improve our exhaustive search algorithms?