| before class | Background that I will not cover (or that I will cover very little). Reading: Kleinberg-Tardos Sections 2 and 3. |
|---|---|
| 1/10/12 | Lecture 1. Introduction. The Stable Marriage Problem. Reading: Kleinberg-Tardos Section 1.1 |
| 1/12/12 | Lecture 2. More on Stable Marriage. Reading: Kleinberg-Tardos Section 1.1. |
| 1/17/12 | 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/19/12 | Lecture 4. Greedy Algorithms, part 2. Reading: Kleinberg-Tardos Sections 4.2 and 4.1. |
| 1/24/12 | Lecture 5. Minimum Spanning Trees. Reading: Kleinberg-Tardos Section 4.5 and 4.6. Problem set 1 due, problem set 2 out. |
| 1/26/12 | Lecture 6. Shortest Paths. Reading: Kleinberg-Tardos Section 4.4. My notes for this lecture, in pdf or postscript. |
| 1/31/12 | 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. I also recommend the disucssion of the "Master Theorem" for solving recurrences at Wikipedia. Problem set 2 due, problem set 3 out. |
| 2/2/12 | Lecture 8. Divide and Conquer 2. Closest Points and the Fast Fourier Transform.
Reading: Kleinberg-Tardos Sections 5.4 and 5.6. Today's explanation of the FFT was inspired by that in the book by Dasgupta, Papadimitriou and Vazirani. There is an on-line version here. |
| 2/7/12 | Lecture 10. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3. Problem set 3 due, problem set 4 out. |
| 2/9/12 | Lecture 11. Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6. |
| 2/14/12 | Lecture 12. Dynamic Programming 3.
Reading: Kleinberg-Tardos Sections 6.8 and 6.9. Problem set 4 due, problem set 5 out. |
| 2/16/12 | Lecture 13. Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1. The demo from class |
| 2/21/12 | Lecture 14. Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2 Problem set 5 due. |
| 2/23/12 | Lecture 15. Network Flow 3.
Reading: Kleinberg-Tardos Section 7.5. |
| 2/28/12 | Midterm, in-class. |
| 3/1/12 |
Midterm, returned and reviewed.
Lecture 16. Randomized Algorithms 1. Reading: Kleinberg-Tardos Section 13.1. |
| 3/20/12 | Lecture 17. Randomized Algorithms 2. Randomized Quick-Select and Quick-Sort.
Reading: Kleinberg-Tardos Section 13.5 Problem set 6 out. |
| 3/22/12 | Lecture 18. Randomized Algorithms 3. Min-Cut and Bipartite Matching.
Reading: Kleinberg-Tardos Section 13.2 and my lecture notes on the paper Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs by Goel, Kapralov and Khanna. |
| 3/27/12 | Lecture 19. Reductions.
Reading: Kleinberg-Tardos Section 8.1 and 8.2. Problem set 6 due, problem set 7 out. |
| 3/29/12 | Lecture 20. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4. |
| 4/3/12 | Lecture 21 . NP hard problems 3
Reading: Kleinberg-Tardos Section 8.4,8.5 and 8.7. Reading: My slides for this lecture Problem set 7 due, problem set 8 out. |
| 4/5/12 | Lecture 22. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.8. Reading: My slides for this lecture |
| 4/10/12 | Lecture 23. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2. Problem set 8 due, problem set 9 out. |
| 4/12/12 | Lecture 24. Approximation Algorithnms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.6. |
| 4/17/12 | Problem set 9 due. |
| 4/19/12 | Lecture 25. Where it goes from here.
|
| 5/4/12 | Final exam. 2:00 PM. ML 211. |