Introduction to Algorithms PPT
Instructor 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.
Slides:
Instructor 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. |
No comments:
Post a Comment