Computer Science 365b Schedule, Spring 2017

This page contains the schedule of lectures and assignments. Other information, such as office hours, may be found on the course homepage. Please consult these, as well as announcements on Canvas, before emailing the course staff.
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.
before class Background that I will not cover (or that I will cover very little).
Reading: Kleinberg-Tardos Sections 2 and 3.
If you have not taken CPSC 223, you should definitely read this!
1/17/17 Lecture 1. Introduction. The Stable Matching Problem.
Reading: Kleinberg-Tardos Section 1.1
How to learn to write proofs.
I wrote an optional Problem Set 0 that you can use to practice your discrete math skills. We will not collect it.
1/19/17 Lecture 2. More on Stable Matchings. Asymptotics and common running times.
Reading: Kleinberg-Tardos Sections 1.1 and 1.2. A Note on Asymptotics
1/24/17 Lecture 3. Representative problems. Scheduling problems, part 1.
Reading: Kleinberg-Tardos Sections 1.2 and 4.1.
A Note on Asymptotics
Problem set 1 out. Find it on Canvas
1/26/17 Lecture 4. Scheduling problems, part 2.
Reading: Kleinberg-Tardos Sections 4.2 and 4.1.
1/31/17 Lecture 5. Shortest Paths.
Reading: Kleinberg-Tardos Section 4.4, and my notes on Dijkstra's Algorithm.
Assignment 0 : Upload a current picture of yourself to Gradescope.
2/2/17 Lecture 6. Minimum Spanning Trees, Part 1.
Reading: Kleinberg-Tardos Section 4.5 and 4.6.
Problem set 1 due.
Problem set 2 out.
2/7/17 Lecture 7. Minimum Spanning Trees, Part 2. Union Find and Clustering.
Reading: Kleinberg-Tardos Section 4.5, 4.6 and 4.7.
2/9/17 Cancelled due to snow
This missed lecture will cause us to skip covering dynamic programming algorithms for shortest paths in graphs with positive and negative edge lengths. That material is in sections 6.8 and 6.9.
2/14/17 Lecture 8. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3.
Problem set 2 due.
Problem set 3 out.
2/16/17 Lecture 9. Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6.
2/21/17 Lecture 10. Divide and Conquer 1 (Merge Sort, Counting Inversions, and Closest Points).
Reading: Kleinberg-Tardos Section 5.1, 5.3 and 5.4.
2/23/17 Lecture 11. Divide and Conquer 2. Randomized Quick-Select and Quick-Sort.
Reading: Kleinberg-Tardos Section 13.5
Problem set 3 due.
2/28/17 First in-class test. In Davies!
3/2/17 Lecture 12. Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1.
The demo from class
Problem set 4 out.
3/7/17 Lecture 13. Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2
3/9/17 Lecture 14. Network Flow 3.
Reading: Kleinberg-Tardos Section 7.5.
Problem set 4 due, problem set 5 out.
Spring Break!
3/28/17 Lecture 15. Reductions.
Reading: Kleinberg-Tardos Section 8.1 and 8.2.
3/30/17 Lecture 16. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4.
Problem set 5 due. Problem set 6 out.
4/4/17 Lecture 17. NP hard problems 3
Reading: Kleinberg-Tardos Section 8.4,8.5 and 8.7.
Reading: My slides for this lecture
4/6/17 Lecture 18. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.8.
Reading: My slides for this lecture
Problem set 6 due. Problem set 7 out.
4/11/17 Lecture 19. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2.
4/13/17 Lecture 20. Approximation Algorithms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.6.
Problem set 7 due.
4/18/17 Second in-class test. In Davies!
4/20/17 Lecture 21. Randomized Algorithms 1.
Reading: Kleinberg-Tardos Section 13.1.
Problem set 8 out.
4/25/17 Lecture 22. Randomized Algorithms 2.
4/27/17 Lecture 23. Where it goes from here. My slides from this lecture
Problem set 8 due.