Introduction to Algorithms PPTInstructor Alon Efrat alon@cs.arizona.edu Description After a short illustration of algorithm design and analysis, the course begins by reviewing basic
analysis techniques (approximating functions asymptotically, bounding sums, and solving recurrences). We then study problems that are efficiently solvable, focusing on basic
design techniques (divide-and-conquer, dynamic programming, greed, and amortization),
graph algorithms (minimum spanning trees, shortest paths, maximum flow and stable marriage),
string algorithms (on- and off-line string matching), and
geometric algorithms (convex hull, line sweep and closest point-pair). We conclude with techniques for dealing with
approximation algorithms and branch-and-bound algorithms.
The emphasis is on learning algorithm
design (the ability to synthesize correct and efficient procedures for new combinatorial problems), acquiring an algorithm
repertoire (a toolbox of classic algorithms for well-solved problems), and applying algorithm
reduction (the ability to reduce new problems to known problems from your repertoire). These skills are developed through written assignments containing challenging exercises.
| Required text | Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein,
Introduction to Algorithms, second edition,
McGraw-Hill, Boston, 2001.
|
| Optional text | Steven S. Skiena,
The Algorithm Design Manual,
Springer-Verlag, New York, 1998. |
Slides:
