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 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 Determine resource usage as a function of input size Ignore multiplicative constants and lower order terms Measure performance as input size increases without bound (toward infinity) Use some standard measure for comparison 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 Exhaustive Search 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
The database is protected by copyright ©sckool.org 2016