| before class | Background that I will not cover (or that I will cover very little). Reading: Kleinberg-Tardos Sections 2 and 3. |
|---|---|
| 1/13/09 | Lecture 1. Introduction. The Stable Marriage Problem. Reading: Kleinberg-Tardos Section 1.1 |
| 1/15/09 | Lecture 2. More on Stable Marriage. Reading: Kleinberg-Tardos Section 1.1. |
| 1/20/09 | Lecture 3. Representative problems. Greedy Algorithms, part 1. Reading: Kleinberg-Tardos Sections 1.2 and 4.1. Problem set 1 out. Find it on Classes V2 |
| 1/22/09 | Lecture 4. Greedy Algorithms, part 2. Reading: Kleinberg-Tardos Sections 4.2 and 4.1. |
| 1/27/09 | Lecture 5. Minimum Spanning Trees. Reading: Kleinberg-Tardos Section 4.5 and 4.6. Problem set 1 due, problem set 2 out. |
| 1/29/09 | Lecture 6. Shortest Paths. Reading: Kleinberg-Tardos Section 4.4. My notes for this lecture, in pdf or postscript. |
| 2/03/09 | Lecture 7. Divide and Conquer 1 (Integer Multiplication and Merge Sort).
Reading: Kleinberg-Tardos Section 5.1, 5.2, 5.3 and 5.5. Note on solving recurrences. An exposition of the method of Akra and Bazzi may be found in the "Chapter notes" of Chapter 4 of the book Introduction to Algorithm Design by Cormen, Leiserson, Rivest and Stein, which is available electronically inside Yale. Problem set 2 due, problem set 3 out. |
| 2/05/09 | Lecture 8. Divide and Conquer 2: Median Finding
Reading: Kleinberg-Tardos Section 13.5. |
| 2/10/09 | Lecture 9. Divide and Conquer 3. Closest Points and the Fast Fourier Transform.
Reading: Kleinberg-Tardos Sections 5.4 and 5.6. Problem set 3 due, problem set 4 out. |
| 2/12/09 | Lecture 10. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3. |
| 2/17/09 | Lecture 11. Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6. Problem set 4 due, problem set 5 out. |
| 2/19/09 | Lecture 12. Dynamic Programming 3.
Reading: Kleinberg-Tardos Sections 6.8 and 6.9. |
| 2/24/09 | Lecture 13. Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1. Problem set 5 due. |
| 2/26/09 | Lecture 14. Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2 The demo I did in class |
| 3/03/09 | Midterm, in-class. |
| 3/05/09 | Lecture 15. Network Flow 3.
Reading: Kleinberg-Tardos Section 7.5. Midterm, returned and reviewed. |
| Spring | Break! |
| 3/24/09 | Lecture 16. Reductions.
Reading: Kleinberg-Tardos Section 8.1 and 8.2. Problem set 6 out. |
| 3/26/09 | Lecture 17. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4. |
| 3/31/09 | Lecture 18 . NP hard problems 3
Reading: Kleinberg-Tardos Section 8.4,8.5 and 8.7. Reading: My slides for this lecture Problem set 6 due, problem set 7 out. |
| 4/2/09 | Lecture 19. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.8. Reading: My slides for this lecture |
| 4/7/09 | Lecture 20. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2. Problem set 7 due, problem set 8 out. |
| 4/9/09 | Lecture 21. Approximation Algorithnms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.6. |
| 4/14/09 | Lecture 22. Randomized Algorithms, part 1.
Reading: Kleinberg-Tardos Section 13.1 and 13.2. Problem set 8 due, problem set 9 out. |
| 4/16/09 | Lecture 23. Randomized Algorithms, part 2.
Reading: Kleinberg-Tardos Section 13.5 and 13.4. |
| 4/21/09 | Lecture 24. Randomized Algorithms and solving SAT.
Problem set 9 due. Reading: Kleinberg-Tardos Section 13.4. My lecture notes on this Schoening's paper |
| 4/23/09 | Lecture 25. Where it goes from here.
|
| 5/06/09 | Final exam. 2:00 PM. |