The course is an introduction to the design and analysis of efficient algorithms, with emphasis on developing design techniques. Algorithmic problems include sorting and searching, discrete optimization, and algorithmic graph theory. Design techniques include divide-and-conquer methods, dynamic programming, greedy methods, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrences, and the concepts of polynomial-time algorithms. NP-complete problems and reductions are discussed at the end the course. Students who complete the course will have demonstrated the ability to use divide-and-conquer methods, dynamic programming methods, and greedy methods, when an algorithmic design problem calls for such a method. They will have learned the design strategies employed by the major sorting algorithms and the major graph algorithms, and will have demonstrated the ability to use these design strategies or modify such algorithms to solve algorithm problems when appropriate. They will have derived and solved recurrences describing the performance of divide-and-conquer algorithms, have analyzed the time and space complexity of dynamic programming algorithms, and have analyzed the efficiency of the major graph algorithms, using asymptotic analysis.
Topics covered include: sorting and searching; divide-and-conquer; randomization; dynamic programming; graph search; shortest paths; minimum spanning trees; network flow; NP-complete problems and reductions.
Lectures: Students are responsible for all material presented in lectures.
Problem sessions: Weekly problem sessions are held on Saturdays. Students are responsible for all material covered at the problem sessions. Class participation is encouraged.
Homework: Weekly homework assignments are posted after class and are due the following week at the beginning of class. Homework is submitted electronically using LaTeX.
Exams: There are four quizzes (weeks 3, 4, 9, and 10), a midterm exam (week 5), and a final exam (week 11). There will be no make-up exams.
The course grade will be based on homework and exams:
- Homework: 5%.
- Quizzes: 20% (5% for each of 4 quizzes).
- Midterm: 25%.
- Final: 50%.
Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8).