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. |