CMSC 27200: Theory of Algorithms (Winter 2022)
- Section 3
- MWF 1:30–2:20 pm, RO 015
- Instructor
- Timothy Ng (timng@uchicago.edu)
- Course website
- Canvas
This is where I'll put my lecture notes and other materials for my section. For information about the course, please visit the course website on Canvas.
Lectures
KT is short for Jon Kleinberg and Éva Tardos. Algorithm Design (2005). CLRS is short for Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3e (2009).
- January 10
- Introduction (KT 2.1)
- January 12
- Asymptotics, stable matchings (KT 2.2, 1.1)
- January 14
- The Gale–Shapley algorithm (KT 1.1)
- January 19
- Analyzing Gale–Shapley (KT 1.1, 2.3)
- January 21
- Greedy algorithms and interval scheduling (KT 4.1)
- January 24
- Scheduling to minimize lateness (KT 4.2)
- January 26
- Single-source shortest paths and Dijkstra's algorithm (KT 4.4, 3.1)
- January 28
- Implementing Dijkstra's algorithm (KT 4.4, 2.5, 3.3)
- January 30
- Minimum spanning trees and Prim's algorithm (KT 4.5)
- February 2
- Kruskal's algorithm (KT 4.5-4.6)
- February 4
- Divide and conquer algorithms, Mergesort, Recurrences (KT 5.1-5.2)
- February 7
- Maximum subarray sum (CLRS 4.1, KT Ch. 5 Solved Ex. 2)
- February 9
- Multiplication (KT 5.5, CLRS 4.2)
- February 11
- Closest pair of points on a plane (KT 5.4)
- February 14
- Midterm Q&A
- February 16
- Dynamic programming (KT 6.1–6.2)
- February 18
- Knapsack (KT 6.4)
- February 21
- Shortest paths revisited (KT 6.8)
- February 23
- Bellman–Ford (KT 6.8), Network flow (KT 7.1)
- February 25
- Ford–Fulkerson (KT 7.1)
- February 28
- Max flow, min cut (KT 7.2)
- March 2
- Bipartite matching (KT 7.5)
- March 4
- Polynomial-time reduction, independent set, and vertex cover (KT 8.1)
- March 7
- Satisfiability, $\mathbf{P}$ and $\mathbf{NP}$ (KT 8.2–8.3)
- March 9
- $\mathbf{NP}$-completeness (KT 8.4)
- March 11
- Hamiltonian cycle, Subset sum (KT 8.5, 8.8)