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 27 | Introduction via a scheduling problem | Chapters 1-3 covers material I expect you to already know. | Homework 0 pdf (ungraded) | |
| Mon, Sep 1 | Labor Day -- no class | |||
| Wed, Sep 3 | Greedy Algorithms (Knapsack, Huffman Intro) | 4.1-4.3 | Homework 1 | |
| Mon, Sep 8 | Greedy Algorithms (Huffman) | 4.8 | ||
| Wed, Sep 10 | Greedy Algorithms (cont) | 4.4-4.5 | ||
| Mon, Sep 15 | Dynamic Programming | Chapter 6 | ||
| Wed, Sep 17 | Dynamic Programming (cont) | Chapter 6 | Homework 1 | Homework 2 |
| Mon, Sep 22 | Dynamic Programming (cont) | Chapter 6 | ||
| Wed, Sep 24 | Dynamic Programming (cont) | Chapter 6 | ||
| Mon, Sept 29 | Linear Programming | Handout | ||
| Wed, Oct 1 | NP-completeness | Chapter 8 | Homework 2 | |
| Mon, Oct 6 | EXAM 1 | |||
| Wed, Oct 8 | NP-completeness (cont) | Chapter 8 | ||
| Mon, Oct 13 | NP-completeness (cont) | Chapter 8 | Homework 3 | |
| Wed, Oct 15 | NP-completeness (cont) | Chapter 8 | ||
| Mon, Oct 20 | NP-completeness (cont) | Chapter 8 | ||
| Wed, Oct 22 | Approximation Algorithms | Chapter 11 | ||
| Mon, Oct 27 | Approximation Algorithms (cont) | Chapter 11 | Homework 3 | Homework 4 |
| Wed, Oct 29 | Approximation Algorithms (cont) | Chapter 11 | ||
| Mon, Nov 3 | Approximation Algorithms (cont) | Chapter 11 | ||
| Wed, Nov 5 | Approximation Algorithms (cont) | Chapter 11 | Homework 4 | |
| Mon, Nov 10 | EXAM 2 | |||
| Wed, Nov 12 | Finding exact complexity of a problem | |||
| Mon, Nov 17 | Lower Bound Techniques | Handout | Homework 5 | |
| Wed, Nov 19 | Lower Bound Techniques (cont) | |||
| Mon, Nov 24 | Randomized Algorithms | Chapter 13 | ||
| Wed, Nov 28 | Thanksgiving Break -- no class | |||
| Mon, Dec 1 | Randomized Algorithms (cont) | Chapter 13 | ||
| Wed, Dec 3 | Randomized Algorithms (cont) | Chapter 13 | Homework 5 | |
| Mon, Dec 8 | Randomized Algorithms (cont) | Chapter 13 | ||
| Wed, December 17, 2008 | Final Exam 1-3pm (Cupples II, 217) |
Readings are from "Algorithm Design", Jon Kleinberg