Introduction to Algorithms PPT

Introduction to Algorithms PPT

Instructor     Alon Efrat 

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.