Lecture Topics (will be updated as the semester progresses)
8/25 — Stable matching I: Gale–Shapley algorithm
Reading: §1.1
8/27 — Stable matching II: Analysis of Gale–Shapley
Reading: §1.1
8/29 — More on Stable Matching, Greedy algorithms I: Interval Scheduling
Reading: §4.1
9/1 — No class (Labor Day)
9/3 — Greedy algorithms I: Interval Scheduling (continued)
Reading: §4.1
9/5 — Greedy algorithms II: Minimum Spanning Tree
Reading: §4.5
9/8 — Dynamic programming I: Weighted Interval Scheduling
Reading: §6.1
9/10 — Dynamic programming II: Subset Sums and Knapsacks
Reading: §6.4
9/12 — Dynamic programming III: Shortest Paths in a Graph
Reading: §6.8
9/15 — Dynamic programming IV: RNA Secondary Structure
Reading: §6.5
9/17 — Divide and Conquer I: Multiplying Integers
Reading: §5.5
9/19 — Divide and Conquer II: Fast Fourier Transform I
Reading: §5.6
9/22 — Divide and Conquer II: Fast Fourier Transform II
Reading: §5.6
9/24 — Divide and Conquer III: Closest Pair of Points in the Plane
Reading: §5.4
9/26 — Network Flow I: Definition and Ford-Fulkerson Algorithm
Reading: §7.1
9/29 — Network Flow II: Max-Flow running time and Cut capacities
Reading: §7.2
10/1 — Review lecture for Prelim 1
Reading:
10/3 — Network Flow III: Max-Flow Min-Cut theorem
Reading: §7.2
10/6 — Network Flow IV: Max-flow Min-cut theorem
Reading: §7.2
10/8 — Network Flow V: Reductions to Max-flow problem
Reading: §7.5
10/10 — Network Flow VI: Reductions to Max-flow problem
Reading: §7.12
10/13 — No Class (Fall Break)
10/15 — NP-Completeness I: Introduction to hardness reductions, P and NP
Reading: §8.1, 8.3
10/17 — NP-Completeness II: NP-complete problems
Reading: §8.2, 8.4
10/17 — NP-Completeness III: SAT as an NP-complete problem
Reading: §8.2, 8.4
10/22 — NP-Completeness IV: Independent Set
Reading: §8.2
10/24 — NP-Completeness V: Graph Coloring
Reading: §8.7
10/27 — NP-Completeness VI: Hamiltonian Cycle, Traveling Salesman
Reading: §8.5
10/29 — NP-Completeness VII: Subset Sum
Reading: §8.8