This is a tentative outline of lecture topics, recitations, and assignment dates for the semester. Although I have tried to predict our schedule accurately, the dates on this calendar are subject to change, depending on how quickly we cover the material. Readings are from Kleinberg and Tardos unless otherwise indicated.
Note that we will not have a class meeting on Monday, 9/5 (Labor Day) or Monday, 10/10 (Fall Break). I plan to provide some additional asynchronous material instead. Lecture, recitation, and homework deadlines will be as normal for those weeks unless otherwise shown on the schedule.
Unless otherwise specified, homework is due by 11:59 PM on Tuesday.
| Week | Lecture Topic | Recitation | Readings | Homework Due | Homework Assigned |
|---|---|---|---|---|---|
| 1: 8/29-9/2 | Introduction via a scheduling problem | R1: recitation logistics | Sec 4.1 | Hwk 0 (turn-in practice) | |
| 2: 9/5-9/9 | Greedy algorithms | R2: greedy | Chapter 4 | Hwk 0 | Hwk 1 |
| 3: 9/12-9/16 | Divide-and-conquer | R3: D&C | Chapter 5 | Hwk 1 | Hwk 2 |
| 4: 9/19-9/23 | Dynamic programming | R4: DP | Chapter 6 | Hwk 2 | Hwk 3 |
| 5: 9/26-9/30 | Maximum flow | Exam 1 review | Secs 7.1-7.3 | Hwk 3 | |
| 6: 10/3-10/7 | Exam 1 (weeks 1-4); no lecture | R6: max flow | Hwk 4 | ||
| 7:10/10-10/14 | Reductions | R7: reductions | Secs 7.5-7.10, 8.1-8.2 | Hwk 4 (due 11:59 PM 10/13) |
Hwk 5 |
| 8: 10/17-10/21 | NP and Intractability I | R8: NP-completeness | Secs 8.2-8.4 | Hwk 5 | Hwk 6 |
| 9: 10/24-10/28 | NP and Intractability II | R9: more NP-completeness | Secs 8.4, 8.8 | Hwk 6 | Hwk 7 |
| 10: 10/31-11/4 | Approximation algorithms | Exam 2 review | Chapter 11 | Hwk 7 | |
| 11: 11/7-11/11 | Exam 2 (weeks 5-9); no lecture | R11: approximation | Hwk 8 | ||
| 12: 11/14-11/18 | Randomized algorithms | R12: randomized algos | Sec 13.1-13.5 | Hwk 8 | Hwk 9 |
| Thanksgiving week | no lecture | no recitation | |||
| 13: 11/28-12/2 | Online algorithms I | R13: online | Secs 4.3, 13.8 | Hwk 9 | Hwk 10 |
| 14: 12/5-12/9 | Online algorithms II | Exam 3 review | Sec 13.8 | Hwk 10 | |
| Finals period | Exam 3 (weeks 10-14) |