| Date | Lecture Topic | Readings | Homework Due | Homework Assigned |
|---|---|---|---|---|
| Thur, Sept 2 | Introduction via a scheduling problem | Homework 0 | ||
| Tue, Sept 7 | Greedy Algorithms | 16.1-16.2 | Homework 1 | |
| Thur, Sept 9 | Greedy Algorithms (cont) | 16.3 | ||
| Tue, Sept 14 | Greedy Algorithms (cont) | 16.5 | ||
| Thur, Sept 16 | Discuss HW 1 Practice Problems (optional) | |||
| Tue, Sept 21 | Dynamic Programming | 15.1-15.2 | Homework 1 | Homework 2 |
| Thur, Sept 23 | Dynamic Programming (cont) | 15.3 | Tue, Sept 28 | Dynamic Programming (cont) | 15.4-15.5 | Thur, Sept 30 | More Dynamic Programming (cont) |
| Tue, Oct 5 | Linear Programming | 29.1-29.2 | Homework 2 | |
| Thur, Oct 7 | NP-completeness | 34.1-34.3 | ||
| Tue, Oct 12 | EXAM 1 | Homework 3 | ||
| Thur, Oct 17 | NP-completeness (cont) | 34.4 | ||
| Tue, Oct 19 | NP-completeness (cont) | 34.5 | ||
| Thur, Oct 21 | NP-completeness (cont) | 34.5 | ||
| Tue, Oct 26 | Approximation Algorithms | 35.1-35.2 | Homework 3 | Homework 4 |
| Thur, Oct 28 | Approximation Algorithms (cont) | 35.3 | ||
| Tue, Nov 2 | Approximation Algorithms (cont) | 35.4 | ||
| Thur, Nov 4 | Approximation Algorithms (cont) | 35.5 | ||
| Tue, Nov 9 | Approximation Algorithms (cont) | Homework 4 | ||
| Thur, Nov 11 | Finding exact complexity of a problem | 9.1 | ||
| Tue, Nov 16 | EXAM 2 | |||
| Thur, Nov 18 | Lower Bound Techniques | Handout | Homework 5 | |
| Tue, Nov 23 | Lower Bound Techniques (cont) | |||
| Thur, Nov 25 | No Class -- Thanksgiving Break | |||
| Tue, Nov 30 | Lower Bound Techniques (cont) | |||
| Thur, Dec 2 | On-line Algorithms and Competitive Analysis | Handout | ||
| Tue, Dec 7 | On-line Algorithms and Competitive Analysis (cont) | Homework 5 | ||
| Thur, Dec 9 | Review | |||
| Wed, Dec 15 | Final Exam 1-3pm (location TBA) |
Readings are from Cormen, Leiserson, Rivest and Stein (2nd Edition).