This schedule will be updated periodically throughout the term. Last update: Aug 16
Readings and, in some cases, web-links are given for each of the topics listed below. Readings are from the course text unless otherwise noted.
Text: Algorithm Design by Jon Kleinberg and Eva Tardos
| Date | Topics | Reading |
|---|---|---|
| Jul 9 | Course Overview; Stable Matching | 1.1; review Ch2 |
| 10 | Some Representative Problems | 1.2; review Ch3 |
| 11 | Greedy Algorithms | Ch4 (exclude 4.7 - 4.9) |
| 12 | Greedy Algorithms | |
| 13 | Greedy Algorithms | |
| 16 | Divide & Conquer | Ch5 (exclude 5.6) |
| 17 | Divide & Conquer | |
| 18 | Dynamic Programming | Ch6 (exclude 6.5, 6.7, and 6.10) |
| 19 | Dynamic Programming | |
| 20 | Dynamic Programming | |
| 23 | Network Flow | Ch7 (exclude 7.4, 7.11, 7.12, and 7.13) |
| 24 | Prelim I (Stable Matching, Basics of Algorithm Analysis, Graphs, Greedy Algorithms, Divide & Conquer, Dynamic Programming) | |
| 25 | Network Flow | |
| 26 | Network Flow | |
| 27 | Network Flow | |
| 30 | NP-Completeness | Ch8 (all sections) |
| 31 | NP-Completeness | |
| Aug 1 | NP-Completeness | |
| 2 | NP-Completeness | |
| 3 | NP-Completeness | |
| 6 | Review for Prelim II | |
| 7 | Prelim II (earlier topics plus Network Flow, NP-Completeness) | |
| 8 | NP-Completeness: Special Cases | Ch10 (10.1 and 10.2 only) |
| 9 | NP-Completeness: Approximations | Ch 11 (exclude 11.4, 11.5, and 11.7) |
| 10 | NP-Completeness: Approximations | |
| 13 | Randomized Algorithms | Ch13 (13.1 through 13.5, and 13.7) |
| 14 | Randomized Algorithms | |
| 15 | Classes of Problems beyond NP (co-NP, PSPACE) | 8.9 and Ch9 (9.1 through 9.3) |
| 16 | Review for Final Exam | |
| 17 | Final Exam (topics from entire course) |