Schedule of Lectures
-
1/24:
-
Lecture: Welcome and introduction.
-
Reading:
Chapter 1.2.
-
1/26:
-
Lecture: The stable matching problem.
-
Reading:
Chapter 1.1.
-
1/28:
-
Lecture: Greedy algorithms I: Interval scheduling
and the “greedy stays ahead” analysis technique.
-
Reading:
Chapter 4.1.
-
1/31:
-
Lecture: Greedy algorithms II: Scheduling to
minimize lateness and
the “exchange argument” analysis technique.
-
Reading:
Chapter 4.2, 4.3.
-
2/2:
-
Cornell University closed on account of weather. Class canceled.
-
2/4:
-
Lecture:
Greedy algorithms III: Minimum spanning tree algorithms.
-
Reading:
Chapter 4.5.
-
2/7:
-
Lecture:
Greedy algorithms IV: Data structures for fast
minimum spanning tree implementations.
-
Reading:
Chapter 4.6.
-
2/9:
-
Lecture:
Divide-and-conquer I: Fast multiplication of polynomials and integers.
-
Reading:
Chapter 5.5.
-
2/11:
-
Lecture:
Divide-and-conquer II: Finding the closest pair of points.
Counting inversions.
-
Reading:
Chapters 5.3, 5.4.
-
2/14:
-
Lecture:
Dynamic programming I: Weighted interval scheduling.
-
Reading:
Chapters 6.1, 6.2, 6.3.
-
2/16:
-
Lecture:
Dynamic programming II: Edit distance, a.k.a. sequence alignment.
-
Reading:
Chapter 6.6.
-
2/18:
-
Lecture:
Shortest-path problems: Dijkstra's algorithm,
introducing the shortest-path problem in graphs
with positive and negative edge costs.
-
Reading:
Chapter 6.8.
-
2/21:
-
Lecture:
Dynamic Programming III: Bellman-Ford shortest path algorithm.
-
Reading:
Chapter 6.8.
-
2/23:
-
Lecture:
Dynamic programming IV: RNA secondary structure
-
Reading:
Chapter 6.5.
-
2/25:
-
Lecture:
Network Flow I: Introduction, basic definitions, decomposition of flow into
weighted sum of paths and cycles.
-
Reading:
Chapter 7.1
-
2/28:
-
Lecture:
Network Flow II: The Ford-Fulkerson Algorithm.
-
Reading:
Chapter 7.2
-
3/2:
-
Lecture:
Network Flow III: The max-flow min-cut theorem, and
correctness of Ford-Fulkerson.
-
Reading:
Chapter 7.2.
-
3/4:
-
3/7:
-
Cornell University closed on account of weather. Class canceled.
-
3/9:
-
Lecture:
Network flow V: Introduction to flow reductions: maximum matching
in bipartite graphs.
-
Reading:
Chapter 7.5, 7.8.
-
3/11:
-
Lecture:
Network flow VI: More flow reductions using bipartite graphs:
baseball elimination.
-
Reading:
Chapter 7.12.
-
3/14:
-
Lecture:
Network flow VII: Reducing to the min-cut problem:
minimum-cost vertex separator, image segmentation.
-
Reading:
Chapter 7.10.
-
3/16:
-
Lecture:
NP-Completeness I: Reductions between SAT and Vertex Cover.
-
Reading:
Chapter 8.2.
-
3/18:
-
Lecture:
NP-Completeness II: More NP-complete graph-theoretic
problems. Independent Set, Clique.
-
Reading:
Chapter 8.2.
-
3/28:
-
Lecture:
NP-Completeness III: The complexity class NP, efficient
verifiers, Karp and Turing reductions, definition of
NP-completeness.
-
Reading:
Chapters 8.1, 8.3.
-
3/30:
-
Lecture:
NP-Completeness IV: NP-complete partitioning problems.
Exact Cover, 3-Coloring.
-
Reading:
Chapters 8.6, 8.7.
-
4/1:
-
Lecture:
NP-Completeness V: NP-complete numerical problems.
Subset Sum, Knapsack.
-
Reading:
Chapter 8.8.
-
4/6:
-
Lecture:
NP-Completeness VI: NP-complete sequencing problems.
Hamiltonian Cycle, Traveling Salesman Problem
-
Reading:
Chapter 8.5.
-
4/8:
-
Lecture:
Other complexity classes: L, #P, and PSPACE.
-
Reading:
None.
-
4/11:
-
4/13:
-
4/15:
-
4/18:
-
4/20:
-
4/22:
-
Lecture:
Non-determinism and the Cook-Levin Theorem.
-
Reading:
Chapter 8.2.
-
4/25:
-
Lecture:
Approximation Algorithms I: The Knapsack Problem.
-
Reading:
Chapter 11.8.
-
4/27:
-
Lecture:
Approximation Algorithms II: Linear Programming and Vertex Cover.
-
Reading:
Chapter 11.6.
-
4/29:
-
Lecture:
Approximation Algorithms III: Greedy Methods.
-
Reading:
Chapters 11.1-11.3.
-
5/2: