This is a tentative outline of lecture topics and assignment dates for the semester. Although I have tried to predict our schedule accurately, the dates on this syllabus are subject to change, depending on how quickly we cover the material.
| Date | Lecture Topic | Readings | Homework Due | Homework Assigned |
|---|---|---|---|---|
| Wed, Aug 26 | Introduction via a scheduling problem | Homework 0 (ungraded) | ||
| Mon, Aug 31 | Greedy Algorithms | 16.1-16.2 | Homework 1 | |
| Wed, Sep 2 | Greedy Algorithms (cont) | 16.3 | ||
| Mon, Sep 7 | Labor Day -- no class | |||
| Wed, Sep 9 | Greedy Algorithms (cont) | 16.5 | ||
| Mon, Sep 14 | Dynamic Programming | 15.1-15.2 | ||
| Wed, Sep 16 | Dynamic Programming (cont) | 15.3-15.4 | Homework 1 | Homework 2 |
| Mon, Sep 21 | Dynamic Programming (cont) | |||
| Wed, Sep 23 | Dynamic Programming (cont) | 25.2 | ||
| Mon, Sep 28 | Yom Kippur -- no class | |||
| Wed, Sep 30 | finish up greedy/DP techniques | |||
| Mon, Oct 5 | NP-completeness | 34.1-34.2 | Homework 2 | |
| Wed, Oct 7 | NP-completeness (cont) | 34.4 | Homework 3 | |
| Mon, Oct 12 | EXAM 1 | |||
| Wed, Oct 14 | NP-completeness (cont) | 34.3 | ||
| Mon, Oct 19 | NP-completeness (cont) | 34.4 | ||
| Wed, Oct 21 | NP-completeness (cont) | 34.5.1,34.5.5 | ||
| Mon, Oct 26 | finish up NP-completeness | Homework 3 | Homework 4 | |
| Wed, Oct 28 | Intro to Approximation Algorithms | 34.5.2,35.1 | ||
| Mon, Nov 2 | More Simple Approximation Algorithms | |||
| Wed, Nov 4 | Log-Factor Approximation: Set Cover | 35.3 | ||
| Mon, Nov 9 | Randomization: Approximating SAT Variants | 35.4 | ||
| Wed, Nov 11 | Linear Programming | 29.1-29.2 | Homework 4 | |
| Mon, Nov 16 | EXAM 2 | |||
| Wed, Nov 18 | More Randomization: Linear Programming with Rounding | 35.4 | ||
| Mon, Nov 23 | Linear Programming with Rounding, Continued | 9.1 | ||
| Wed, Nov 25 | Thanksgiving Break -- no class | |||
| Mon, Nov 30 | TBA 1 | |||
| Wed, Dec 2 | TBA 2 | |||
| Mon, Dec 7 | TBA 3 | |||
| Thu, Dec 17 | Final Exam 1-3 PM |
Readings are from Cormen, Leiserson, Rivest, and Stein (2nd Edition).