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

 Page 1/24 Date conversion 03.05.2017 Size 186,06 Kb.

## 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:
• 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
• 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

• A
• G
• F
• E
• C
• B
• D

## 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