Schedule

Homework assignments are due at noon on the day indicated. Reading assignments are listed on the day they are assigned, and generally prepare you for the next class. Optional reading assignments are in brackets.

Note that this schedule is an aspirational approximation of what we'll do; it may be updated as the term goes on.

Week 1: Intro; Stable Matching
Date Due Class Topic Out Reading
1. M 9/15 Welcome; Course overview; Notation review; Intro to stable matching PS0; PS1 Preface, §1.1, §2.1–2
2. W 9/17 PS1 Solving stable matching: brute force and the Gale–Shapley proposal algorithm PS2 §2.3–5
3. F 9/19 PS0; PS1 Gale–Shapley §3.1
Week 2: Aymptotics, Proofs of Correctness, and Graphs
4. M 9/22 PS2 Stable-matching variants that better model the NRMP; Proofs and problem-solving Posted asymptotics notes; §1.2; §3.2–3
5. W 9/24 PS2 More proofs; Data structures; Asymptotics (O, Ω, Θ) PS3 §3.4–6
6. F 9/26 PS2 Graphs and some sample problems; Graph implementation Q1 §4.4
Week 3: Greedy Algorithms
7. M 9/29 Q1 Graph traversal (BFS and DFS); Shortest paths in weighted graphs §4.1
8. W 10/1 PS3 Dijkstra's algorithm PS4 §4.2
9. F 10/3 PS3 Dijkstra's redux; Problem writeup critique Q2 §4.5–6
Week 4: More Greedy Algorithms
Date Due Class Topic Out Reading
10. M 10/6 Q2 Greedy algorithms; Interval scheduling; Deadline Scheduling & exchange arguments
11. W 10/8 PS4 Minimum Spanning Trees; MST algorithms: Reverse-Delete, Kruskal's, Prim's, and Borůvka's PS5; Q3 Jeff Erickson's notes on Disjoint Sets data structures
12. F 10/10 PS4 Implementing Kruskal's and Borůvka's; The Union-Find / Disjoint Sets data structure Optional: David Karger, Philip Klein, and Robert Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM, 1995.
Week 5: Dynamic Programming Basics
13. M 10/13 Q3 Exam 1 §6.1–3
14. W 10/15 PS5 Intro to Dynamic Programming: Weighted Interval Scheduling, Recurrence Relations, and Memoization PS6
15. F 10/17 PS5 Sequence Alignment; Mid-Term evals
Week 6: Dynamic Programming
XX. M 10/20 No class (like a Marxist utopia)
16. W 10/22 PS6 Sequence Alignment; Seam Carving PS7 §6.6
17. F 10/24 PS6 Seam Carving; Shortest Paths with negative weights: Bellman–Ford Q4 §6.8
Week 7: DP Finale; Divide-and-Conquer
Date Due Class Topic Out Reading
18. M 10/27 Q4 DP shortest paths: Floyd–Warshall; Divide-and-Conquer: Return of the Recurrence Relations!
19. W 10/29 PS7 Counting Inversions PS8
20. F 10/31 PS7 Order statistics / Selection algorithms (Randomized, Quickselect, "Magic Five") Q5
Week 8: More Divide-and-Conquer; Network Flow
21. M 11/3 Q5 Closest points in the plane
22. W 11/5 PS8 D&C wrap-up; Network flow, max flow, and applications PS9
23. F 11/7 PS8 Max-flow applications; Residual graphs; Ford–Fulkerson
Week 9: Network Flow
24. M 11/10 F–F complexity; Cuts in Flow Networks; Max Flow / Min Cut
25. W 11/12 PS9 Max Flow / Min Cut redux; Edmonds–Karp PS10
26. F 11/14 PS9 Image Segmentation via Max Flow
 
Week 10: Wrap-Up
27. M 11/17 PS10 Local Search
28. W 11/19 PS10, Exam Notes Gradient Descent & Simulated Annealing; Review; Ask Me Anything; Course evals
Exam Period
Mon. 11/24 3a Exam Period: 8:30am–11am (though the final is self-scheduled)