CMSC 27200: Theory of Algorithms (Spring 2021)
- Section 2
- MWF 11:30–12:20 am Central
- 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.
Class meetings
Lectures for this section are streamed live on Panopto at the scheduled lecture time. A link for the stream will appear on Panopto shortly before the class begins. Students are encouraged to make use of the discussion feature to ask questions or discuss the lecture amongst themselves.
Lectures
- March 29
- Introduction
- Stable Matching (KT 1.1)
- March 31
- Algorithm Analysis (KT 2.1–2.2)
- April 2
- Analyzing Gale–Shapley (KT 1.1, 2.3)
- April 5
- Greedy Algorithms and Interval Scheduling (KT 4.1)
- April 7
- Scheduling to minimize lateness (KT 4.2)
- April 9
- Single-source shortest paths and Dijkstra's algorithm (KT 4.4)
- April 12
- Implementing Dijkstra's algorithm (KT 4.4), Minimum spanning trees (KT 4.5)
- April 14
- Prim's and Kruskal's algorithms (KT 4.5)
- April 16
- Implementing Kruskal's algorithm with union-find (KT 4.6), Divide and Conquer (KT 5.1)
- April 19
- Analyzing Mergesort (KT 5.1), The Master Theorem (KT 5.2)
- April 21
- Closest Pair of Points on a Plane (KT 5.4)
- April 23
- Fast integer and matrix multiplication (KT 5.5, CLRS 4.2)
- April 23
- Weighted interval scheduling via dynamic programming (KT 6.1–2)
- April 25
- Knapsack (KT 6.4)
- April 29
- Edit Distance (KT 6.6)
- May 3
- Shortest Paths, revisited (KT 6.8)
- May 5
- Bellman–Ford (KT 6.8), RNA Secondary Structure (KT 6.5)
- May 7
- RNA Secondary Structure (KT 6.5)
- May 10
- Network Flow (KT 7.1)
- May 12
- Max Flow, Min Cut (KT 7.2)
- May 14
- Bipartite Matching (KT 7.5)
- May 17
- Reduction (KT 8.1)
- May 19
- More reduction, Classification of problems (KT 8.1–8.3)
- May 21
- $\mathbf P$ and $\mathbf{NP}$ (KT 8.3–8.4)
- May 24
- Proving $\mathbf{NP}$-completeness (KT 8.4–8.5)
- May 26
- More $\mathbf{NP}$-completeness (KT 8.5, 8.8)
- May 28
- Ask me anything