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?