| 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/25/22 | Lecture 1. (Zoom) Introduction and Scheduling Problems. Reading: Kleinberg-Tardos Sections 1.2, 2.4, and 4.1 A Note on Asymptotics Problem set 1 out. Find it on Canvas |
| 1/27/22 | Lecture 2. (Zoom)
Scheduling problems, part 2. Reading: Kleinberg-Tardos Section 4.2. |
| 2/1/22 | Lecture 3. (Zoom)
Shortest Paths. Reading: Kleinberg-Tardos Section 4.4, and my notes on Dijkstra's Algorithm. |
| 2/3/22 | Lecture 4. (Zoom)
Minimum Spanning Trees, Part 1. Reading: Kleinberg-Tardos Section 4.5 and 4.6. |
| 2/8/22 | 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/10/22 | Lecture 6.
Dynamic Programming 1
Reading: Kleinberg-Tardos Sections 6.1, 6.2 and 6.3. |
| 2/15/22 | Lecture 7.
Dynamic Programming 2
Reading: Kleinberg-Tardos Section 6.4 and 6.6. |
| 2/17/22 | Lecture 8.
Dynamic Programming 3.
Reading: Kleinberg-Tardos Sections 6.8 and 6.9. Problem set 2 due. Problem set 3 out. |
| 2/22/22 | Lecture 9.
Divide and Conquer 1.
Mergesort: Kleinberg-Tardos Section 5.1 Integer Multiplication: Kleinberg-Tardos Section 5.5. Fast Matrix Multiplication. Try Wikipedia. Recurrences: Kleinberg-Tardos Section 5.2. And, here's an exposition of the method of Akra and Bazzi, written by Tom Leighton. |
| 2/24/22 | 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 |
| 3/1/22 | Lecture 11.
Rearranging computations to save time and space.
my lecture notes
Problem set 3 due. Problem set 4 out. |
| 3/3/22 | Lecture 12.
Network Flow 1.
Reading: Kleinberg-Tardos Sections 7.1. The demo from class |
| 3/8/22 | Lecture 13.
Network Flow 2.
Reading: Kleinberg-Tardos Section 7.2 and 7.5. |
| 3/10/22 | Lecture 14.
Network Flow 3.
Reading: Kleinberg-Tardos Section 7.3. Bobby Kleinberg's notes on the Edmonds Karp Algorithm |
| 3/15/22 |
Lecture 15.
Linear Programming
Reading: Jeff Erickson's notes on Linear Programming. Problem set 4 due. Problem set 5 out. |
| 3/17/22 | Lecture 16.
Reductions. And NP-completeness.
Reading: Kleinberg-Tardos Section 8.1 and 8.2. |
| Spring Break! | |
| 3/29/22 | Lecture 17.
NP hard problems 2
Reading: Kleinberg-Tardos Section 8.3 and 8.4. |
| 3/31/22 | Lecture 18.
NP hard problems 3
Reading: Kleinberg-Tardos Section 8.6 and 8.8. Reading: My slides for this lecture Problem set 5 due. Problem set 6 out. |
| 4/5/22 | Lecture 19.
NP hard problems 4.
Reading: Kleinberg-Tardos Section 8.4,8.5 and 8.7. Reading: My slides for this lecture |
| 4/7/22 | Lecture 20.
Approximation Algorithms.
Reading: Kleinberg-Tardos Section 11.1 and 11.2. |
| 4/12/22 | Lecture 21.
Approximation Algorithms, part 2.
Reading: Kleinberg-Tardos Section 11.3 and 11.6. Problem set 6 due. Problem set 7 out. |
| 4/14/22 | Lecture 22.
Randomized Algorithms, part 1.
Reading: Kleinberg-Tardos Section 13.1 and 13.3. |
| 4/19/22 | 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/21/22 | Lecture 24. Matchings in Regular Bipartite Graphs. my lecture notes |
| 4/26/22 | Lecture 25.
SAT Solvers.
Reading: Jeff Erickson's notes on Backtrack Algorithms for 3-SAT. Reading: My notes on Schoening's algorithm |
| 4/28/22 | Lecture 26.
Where it goes from here. my slides
Problem set 8 due. |
| 5/10/22 | Final exam. 10:00 AM - noon in BASS 305. |