Computer Science 365b Schedule, Spring 2008

[Home] [Schedule]
The following schedule lists the topics of each lecture, the readings that go along with them, and the associated homeworks. Listings of future events are speculative.
?/?/08 Background that I will not cover (or that I will cover very little).
Reading: Kleinberg-Tardos Sections 2 and 3.
1/15/08 Lecture 1. Introduction. The Stable Marriage Problem.
Reading: Kleinberg-Tardos Section 1.1
1/17/08 Lecture 2. More on Stable Marriage.
Reading: Kleinberg-Tardos Section 1.1.
1/22/08 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/24/08 Lecture 4. Greedy Algorithms, part 2.
Reading: Kleinberg-Tardos Sections 4.2 and 4.1.
1/29/08 Lecture 5. Minimum Spanning Trees.
Reading: Kleinberg-Tardos Section 4.5 and 4.6.
Problem set 1 due, problem set 2 out.
1/31/08 Lecture 6. Shortest Paths.
Reading: Kleinberg-Tardos Section 4.4.
2/05/08 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/07/08 Lecture 8. Divide and Conquer 2: Median Finding
Reading: Kleinberg-Tardos Section 13.5.
2/12/08 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/14/08 Lecture 10. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3.
2/19/08 Lecture 11. Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6.
Problem set 4 due, problem set 5 out.
2/21/08 Lecture 12. Dynamic Programming 3.
Reading: Kleinberg-Tardos Sections 6.8 and 6.9.
2/26/06 Lecture 13. Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1.
Problem set 5 due.
2/28/08 Lecture 14. Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2
The demo I did in class
3/04/08 Midterm, in-class.
3/06/08 Lecture 15. Network Flow 3.
Reading: Kleinberg-Tardos Section 7.3.
Midterm, returned and reviewed.
Spring Break!
3/25/08 Lecture 16. Reductions.
Reading: Kleinberg-Tardos Section 8.1 and 8.2.
Problem set 6 out.
3/27/08 Lecture 17. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4.
4/1/08 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/3/08 Lecture 19. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.8.
Reading: My slides for this lecture
4/8/08 Lecture 20. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2.
Problem set 7 due, problem set 8 out.
4/10/08 Lecture 21. Approximation Algorithnms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.4.
4/15/08 Lecture 22. Approximation Algorithms and Linear Programming.
Reading: Kleinberg-Tardos Section 11.6.
Problem set 8 due, problem set 9 out.
4/17/08 Lecture 23. Randomized Algorithms.
Reading: Kleinberg-Tardos Section 13.2 and 13.4.
4/22/08 Lecture 24. Recent advances in algorithms.
4/24/08 Lecture 25. Where it goes from here.
  • My slides from this lecture.
    • 5/06/08 Final exam. 2:00 PM.
    Last modified: Thu Apr 24 14:18:56 EDT 2008