These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

These notes are intended for use by students in CS1501 at the University of Pittsburgh and no one else

• 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
• An algorithm solves a problem if it produces an acceptable output on EVERY input

Goals of Course

• Goals of this course:
• To learn how to convert (nontrivial) algorithms into programs
• Often what seems like a fairly simple algorithm is not so simple when converted into a program
• Other algorithms are complex to begin with, and the conversion must be carefully considered
• Many issues must be dealt with during the implementation process
• Let's hear some

Goals of Course

• To see and understand differences in algorithms and how they affect the run-times of the associated programs
• Many problems can be solved in more than one way
• Different solutions can be compared using many factors
• One important factor is program run-time
• Sometimes a better run-time makes one algorithm more desirable than another
• Sometimes a better run-time makes a problem solution feasible where it was not feasible before
• However, there are other factors for comparing algorithms
• Let's hear some

Algorithm Analysis

• Determine resource usage as a function of input size
• Which resources?
• Ignore multiplicative constants and lower order terms
• Why?
• Measure performance as input size increases without bound (toward infinity)
• Asymptotic performance
• Use some standard measure for comparison
• Do we know any measures?

Algorithm Analysis

• Big O
• Upper bound on the asymptotic performance
• Big Omega
• Lower bound on the asymptotic performance
• Theta
• Upper and lower bound on the asymptotic performance – Exact bound
• Compare on the board
• So why would we ever use Big O?
• Theta is harder to show in some cases
• Lower bounds are typically harder to show than upper bounds
• So sometimes we can just determine the upper bound

Algorithm Analysis

• So is algorithm analysis really important?
• Yes! Different algorithms can have considerably different run-times
• Sometimes the differences are subtle but sometimes they are extreme
• Let's look at a table of growth rates on the board
• 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?
• Think of the execution of our algorithm as a tree
• Each path from the root to a leaf is an attempt at a solution
• The exhaustive search algorithm may try every path
• We'd like to eliminate some (many) of these execution paths if possible
• If we can prune an entire subtree of solutions, we can greatly improve our algorithm runtime