Homework assignments are due at 12:15pm on the day indicated. Assignments are posted to Moodle. The reading assigned each day relates to the next class's material, and is to be done before the next class meeting. For more details on class policies, please see the syllabus.
Date  Due  Class Topic and Materials  Out  Reading  

Week 1: Intro; Stable Matching  
1. M 9/16  Welcome Being Bad At Math 
PS1  Preface, §1.1, §2.1–2  
2. W 9/18  PS1.I  State healthcare emulation; Solving stable matching: bruteforce and the Gale–Shapley proposal algorithm  PS2  §2.3–5  
3. F 9/20  PS1.II  Gale–Shapley; stablematching variants that better model the NRMP  §3.1 Optionally (but skim pages 1–3), read Jack Edmonds, Paths, Trees, and Flowers. Canadian Journal of Mathematics, 1965 

Week 2: Asymptotics, Proofs of Correctness, and Graphs  
4. M 9/23  PS2.I  Stable matching wrapup; data structures; asymptotics  Posted asymptotics notes; §1.2; §3.2–3  
5. W 9/25  PS2.II  Asymptotics (O, Ω, Θ)  PS3  §3.4–6  
6. F 9/27  PS2.III  Graph representations; sample problems  §4.4  
Week 3: Greedy Algorithms  
7. M 9/30  PS3.I  DFS; BFS; "edge explosion"; Dijkstra's algorithm  §4.1  
8. W 10/2  PS3.II  Dijkstra implementation; greedy algorithms; interval scheduling  PS4  §4.2  
9. F 10/4  PS3.III  Interval scheduling; deadline scheduling; exchange arguments  §4.5–6  
Week 4: More Greedy Algorithms; Dynamic Programming  
10. M 10/7  PS4.I  MSTs: ReverseDelete, Kruskal's, and Prim's Algorithms; MST properties  
11. W 10/9  PS4.II  Implementing Kruskal's; Disjoint Set / UnionFind data structures; Intro to Dynamic Programming  Optional: Jeff Erickson's notes on Disjoint Sets data structures  
12. F 10/11  PS4.III  Borůvka's MST algorithm; D.P.: word segmentation  PS5  §6.1–2 Optional: David Karger, Philip Klein, and Robert Tarjan. A Randomized LinearTime Algorithm to Find Minimum Spanning Trees. JACM, 1995. 

Week 5: Dynamic Programming  
13. M 10/14  Word segmentation, weighted interval scheduling; course evals  
14. W 10/16  Exam 1  PS6  §6.6–8  
15. F 10/18  PS5.I  D.P. smörgåsbord: sequence alignment, seam carving, shortest paths with negative edges  Optional: the rest of chapter 6 (D.P.)  
Week 6: Dynamic Programming Redux  
XX. M 10/21  No class (like a Marxist utopia)  
16. W 10/23  PS6.I  Sequence alignment, seam carving  PS7  §5.1–2, The original demo video for Seam Carving, from SIGGRAPH 2007  
17. F 10/25  PS6.II  D.P. Shortestpath algorithms: Bellman–Ford and Floyd–Warshall  §5.3  
Week 7: DivideandConquer  
18. M 10/28  PS7.I  DivideandConquer intro; recurrence relations  §5.4; handouts on inversions and order statistics (on Moodle)  
19. W 10/30  PS7.II  Counting inversions; order statistics  The Wikipedia article on selection algorithms, handouts on Magic Five and ClosestPoints (on Moodle)  
20. F 11/1  PS7.III  Selection algorithms (Quickselect, randomized, "Magic Five"); Closest points in the plane  PS8  §7.1  
Week 8: Network Flow  
21. M 11/4  D&C wrapup; Network flow and cuts  §7.2–3  
22. W 11/6  PS8.I  Max flow; Ford–Fulkerson  §7.5  
23. F 11/8  PS8.II  Max flow / min cut  PS9  
Week 9: More Network Flow, Etc.  
24. M 11/11  PS8.III  Max flow / min cut; Edmonds–Karp  
25. W 11/13  Exam 2  §8.0, §8.3, §9.1, P vs. NP on Wikipedia  
26. F 11/15  PS9.I  Bipartite Matching; looking forward to CS 254  
Week 10: Etc., Etc.  
27. M 11/18  PS9.II  Mystery class; review  
28. W 11/20  Ask me anything; course evals 