| 1/10/06 | Lecture 1. Introduction. The Stable Marriage Problem. Reading: Kleinberg-Tardos Section 1.1 |
|---|---|
| 1/12/06 | Lecture 2. More on Stable Marriage. Big-O notation. Five representative problems. Reading: Kleinberg-Tardos Section 1.1 and 1.2. Some of Section 2.2. |
| 1/17/06 | Lecture 3. Asymptotic notation and analysis of algorithms. Directed Graph Algorithms. Reading: Kleinberg-Tardos Chapter 2 and Sections 3.5 and 3.6. Review: Kleinberg-Tardos Sections 3.1-3.4, if you are not familiar with the material. Problem set 1 out. |
| 1/19/06 | Lecture 4. Greedy Algorithsm, part 1. Reading: Kleinberg-Tardos Section 4.1 |
| 1/24/06 | Lecture 5. Greedy algorithms, part 2. Shortest Paths. Reading: Kleinberg-Tardos Section 4.4. Reading: My notes for this lecture Postscript or PDF. Problem set 1 due, problem set 2 out. |
| 1/26/06 | Lecture 6. Minimum Spanning Trees. Reading: Kleinberg-Tardos Section 4.5 and 4.6. |
| 1/31/06 | Lecture 7. Divide and Conquer 1
Reading: Kleinberg-Tardos Section 5.1 and 5.3. Problem set 2 due, problem set 3 out. |
| 2/02/06 | Lecture 8. Divide and Conquer 2: Median Finding
Reading: Kleinberg-Tardos Section 13.5. |
| 2/07/06 | Lecture 9. Divide and Conquer 3.
Reading: Kleinberg-Tardos Section 5.4. Problem set 3 due, problem set 4 out. |
| 2/09/06 | Lecture 10. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1 and 6.2. |
| 2/14/06 | Lecture 11. Dynamic Programming 2
Reading: Kleinberg-Tardos Sections 6.3 and 6.5. Problem set 4 due, problem set 5 out. |
| 2/16/06 | Lecture 12. Dynamic Programming 3. Guest Lecture by Ravi Kannan.
Reading: Kleinberg-Tardos Sections 6.4. |
| 2/21/06 | Lecture 14. Dynamic Programming 4
Reading: Kleinberg-Tardos Sections 6.8. Problem set 5 due. |
| 2/23/06 | Lecture 14. Network Flow 1
Reading: Kleinberg-Tardos Section 7.1 |
| 2/28/06 | Lecture 15. Network Flow 2
Reading: Kleinberg-Tardos Section 7.2 |
| 3/02/06 | Midterm, in-class. |
| 3/21/06 | Lecture 16. Reductions.
Reading: Kleinberg-Tardos Sections 7.5 and 8.1. Problem set 6 out. |
| 3/23/06 | Lecture 17. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.2. |
| 3/28/06 | Lecture 18 . NP hard problems 3
Reading: Kleinberg-Tardos Section 8.3 and 8.4. Problem set 6 due, problem set 7 out. |
| 3/30/06 | Lecture 19. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.7. |
| 4/04/06 | Lecture 20. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2. Problem set 7 due, problem set 8 out. |
| 4/06/06 | Lecture 21. Approximation Algorithnms, part 2.
Reading: see my lecture notes |
| 4/11/06 | Lecture 22. Approximatino Algorithms, part 3.
Reading: Kleinberg-Tardos Section 11.6. Problem set 8 due, problem set 9 out. |
| 4/13/06 | Lecture 23. Randomized Algorithms.
Reading: Kleinberg-Tardos Section 13.1 and 13.4. |
| 4/18/06 | Lecture 24. Randomized Algorithms, part 2.
Reading: Kleinberg-Tardos Section 13.2. Problem set 9 due. |
| 4/20/06 | Lecture 25. Guest lecture. |