The course is an introduction to the design and analysis of efficient algorithms, with emphasis on design techniques. Algorithmic problems include sorting and searching, discrete optimization, algorithmic graph theory, and basic numerics. Design techniques include divide-and-conquer methods, dynamic programming, randomization, 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. 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 to solve algorithm problems when appropriate. They will have derived and solved recurrences describing the performance of divide-and-conquer algorithms, analyzed the time and space complexity of dynamic programming algorithms, and analyzed the efficiency of the basic graph algorithms, using asymptotic analysis.
Topics covered include: sorting and searching; divide-and-conquer; randomization; dynamic programming; hash tables and binary search trees; gradient descent and Newton's method; graph search; shortest paths; minimum spanning trees; network flow; and graph reductions.
Lectures: Students are responsible for all material presented in lectures.
Class sessions: Course material for the current week and assigned homework from the previous week will be discussed at the class meetings.
Homework: Weekly homework assignments are posted after class and are due the day before class on the following week. Homework must be submitted electronically. Homework will include a weekly programming assignment in Python.
Exams: There will be a midterm exam (week 5), and an online final exam on the last day of class. There will be no make-up exams.
The course grade will be based on homework and exams:
- Homework: 30%
- Midterm: 35%.
- Final: 35%.
Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8).