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 shown are from Cormen, Leiserson, Rivest, and Stein (3rd edition) unless otherwise indicated.
Homeworks are due Wednesday at 2:30 PM Central Time unless otherwise specified.
| Week | Lecture Topic | Recitation | Readings | Homework Due | Homework Assigned |
|---|---|---|---|---|---|
| 1: 1/25-1-29 | Introduction and review of greedy algorithms | R0: recitation logistics | 16.1-16.2 | Hwk 0 (turn-in practice) | |
| 2: 2/1-2/5 | Dynamic Programming I | R1: greedy | 15.1,15.4 | ||
| 3: 2/8-2/12 | Dynamic Programming II | R2: DP | 15.2-15.3 | Hwk 0 | Hwk 1 |
| 4: 2/15-2/19 | P, NP, and NP-completeness | R3: more DP | 34.1-34.3 | ||
| 5: 2/22-2/26 | Proving NP-hardness via reductions | R4: proving problems NP-hard | 34.4-34.5 | Hwk 1 | Hwk 2 |
| 6: 3/1-3/5 | Why is 3SAT Hard? Cook's Theorem | wellness day -- no recitation | 34.3 | ||
| 7: 3/8-3/12 | Intro to approximation algorithms | R5: more practice proving problems hard | 35.1,35.3 | Hwk 2 | |
| 8: 3/15-3/19 | Exam 1 -- no lecture | no recitation | |||
| 9: 3/22-3/26 | Approximation schemes, randomized approximation | R6: approximation | 35.4 | Hwk 3 | |
| 10: 3/29-4/2 | Linear programming and its use in approximation | R7: more approximation | 29.1-29.2,35.4 | ||
| 11: 4/5-4/9 | More approximations via linear programming | R8: linear programming | Hwk 3 | ||
| 12: 4/12-4/16 | Approximation via submodular functions | R9: more linear programming | review article Secs. 1, 2, 3.1 | Hwk 4 | |
| 13: 4/19-4/23 | LP duality and the primal-dual method | R10: submodular functions | |||
| 14: 4/26-4/30 | Approximation via semidefinite programming | R11: LP duality | Hwk 4 | ||
| 5/3-finals | Exam 2 |