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) |