Computer Science 366b Schedule, Spring 2018

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/16/18 Lecture 1. Introduction and Scheduling Problems.
Reading: Kleinberg-Tardos Sections 1.2, 2.4, and 4.1
A Note on Asymptotics

Assignment 0 : Upload a current picture of yourself with your name to Gradescope: look on Canvas for instructions.
1/18/18 Lecture 2. Scheduling problems, part 2.
Reading: Kleinberg-Tardos Section 4.2.
Problem set 1 out. Find it on Canvas
1/23/18 Lecture 3. Shortest Paths.
Reading: Kleinberg-Tardos Section 4.4, and my notes on Dijkstra's Algorithm.
1/25/18 Lecture 4. Minimum Spanning Trees, Part 1.
Reading: Kleinberg-Tardos Section 4.5 and 4.6.
1/30/18 Lecture 5. Minimum Spanning Trees, Part 2. Clustering, d-ary heaps, Union-Find, and other data structures
Reading: Kleinberg-Tardos Section 4.5, 4.6 and 4.7.
For d-ary heaps, I recommend Wikipedia
Problem set 1 due. Problem set 2 out.
2/1/18 Lecture 6. Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3.
2/6/18 Lecture 7. Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6.
2/8/18 Lecture 8. Dynamic Programming 3.
Reading: Kleinberg-Tardos Sections 6.8 and 6.9.
Problem set 2 due. Problem set 3 out.
2/13/18 Lecture 9. Divide and Conquer 1.
Mergesort: Kleinberg-Tardos Section 5.1
Integer Multiplication: Kleinberg-Tardos Section 5.4.
Fast Matrix Multiplication. Try Wikipedia.
Recurrences: Kleinberg-Tardos Section 5.2
2/15/18 Lecture 10. Divide and Conquer 2: Convolutions and the Fast Fourier Transform (FFT).
Background on polynomials: Notes by Satish Rao and David Tse.
Reading: Kleinberg-Tardos Section 5.6, or Jeff Erickson's notes
2/20/18 Lecture 11. Rearranging computations to save time and space. my lecture notes
Problem set 3 due. Problem set 4 out.
2/22/18 Lecture 12. Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1.
The demo from class
2/27/18 Lecture 13. Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2 and 7.5.
3/1/18 Lecture 14. Network Flow 3.
Reading: Kleinberg-Tardos Section 7.3.
Bobby Kleinberg's notes on the Edmonds Karp Algorithm
3/6/18 Lecture 15. Linear Programming
Reading: Jeff Erickson's notes on Linear Programming.
Problem set 4 due. Problem set 5 out.
3/8/18 Lecture 16. Reductions. And NP-completeness.
Reading: Kleinberg-Tardos Section 8.1 and 8.2.
Spring Break!
3/27/18 Lecture 17. NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4.
3/29/18 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 5 due. Problem set 6 out.
4/3/18 Lecture 19. NP hard problems 4
Reading: Kleinberg-Tardos Section 8.6 and 8.8.
Reading: My slides for this lecture
4/5/18 Lecture 20. Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2.
4/10/18 Lecture 21. Approximation Algorithms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.6.
Problem set 6 due. Problem set 7 out.
4/12/18 Lecture 22. Randomized Algorithms, part 1.
Reading: Kleinberg-Tardos Section 13.1 and 13.3.
4/17/18 Lecture 23. Randomized Algorithms, part 2. Randomized Quick-Select and Quick-Sort.
Reading: Kleinberg-Tardos Section 13.5
Problem set 7 due. Problem set 8 out.
4/19/18 Lecture 24. Matchings in Regular Bipartite Graphs. my lecture notes
4/25/18 Lecture 25. SAT Solvers.
Reading: Jeff Erickson's notes on Backtrack Algorithms for 3-SAT.
Reading: My notes on Schoening's algorithm
4/26/18 Lecture 26. Where it goes from here.
Problem set 8 due.
5/4/18 Final exam. 10:00 AM - 12:00AM. This is a 90 minute final, with an extra 30 minutes. In WLH 119.