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. I will try to post updated schedules after each exam.
| Date | Lecture Topic | Readings | Homework Due | Homework Assigned |
|---|---|---|---|---|
| Wed, Aug 29 | Introduction via a scheduling problem | Homework 0 (ungraded) | ||
| Mon, Sep 3 | Labor Day -- no class | |||
| Wed, Sep 5 | Greedy Algorithms | 16.1-16.2 | Homework 1 | |
| Mon, Sep 10 | Greedy Algorithms (cont) | 16.3 | ||
| Wed, Sep 12 | Greedy Algorithms (cont) | 16.5 | ||
| Mon, Sep 17 | Dynamic Programming | 15.1-15.2 | ||
| Wed, Sep 19 | Dynamic Programming (cont) | 15.3-15.4 | Homework 1 | Homework 2 |
| Mon, Sep 24 | Dynamic Programming (cont) | |||
| Wed, Sep 26 | Dynamic Programming (cont) | 25.2 | ||
| Mon, Oct 1 | Linear Programming | 29.1-29.2 | ||
| Wed, Oct 3 | NP-completeness | 34.1-34.2 | Homework 2 | |
| Mon, Oct 8 | EXAM 1 | |||
| Wed, Oct 10 | NP-completeness (cont) | 34.4 | ||
| Mon, Oct 15 | NP-completeness (cont) | 34.3 | Homework 3 | |
| Wed, Oct 17 | NP-completeness (cont) | 34.4 | ||
| Mon, Oct 22 | NP-completeness (cont) | 34.5.1,34.5.5 | ||
| Wed, Oct 24 | Approximation Algorithms | 34.5.2,35.1 | ||
| Mon, Oct 29 | Approximation Algorithms (cont) | Homework 3 | Homework 4 | |
| Wed, Oct 31 | Approximation Algorithms (cont) | 35.3 | ||
| Mon, Nov 5 | Approximation Algorithms (cont) | 35.4 | ||
| Wed, Nov 7 | Approximation Algorithms (cont) | 35.4 | Homework 4 | |
| Mon, Nov 12 | EXAM 2 | |||
| Wed, Nov 14 | Finding exact complexity of a problem | 9.1 | ||
| Mon, Nov 19 | Lower Bound Techniques | Handout | Homework 5 | |
| Wed, Nov 21 | Lower Bound Techniques (cont) | |||
| Mon, Nov 26 | Randomized Algorithms | Handout | ||
| Wed, Nov 28 | Thanksgiving Break -- no class | |||
| Mon, Dec 3 | Randomized Algorithms (cont) | Handout | ||
| Wed, Dec 5 | Randomized Algorithms (cont) | Handout | Homework 5 | |
| Mon, Dec 10 | Final Exam 1-3pm (location TBA) |
Readings are from Cormen, Leiserson, Rivest, and Stein (2nd Edition).