Schedule of Lectures
-
1/21:
-
Lecture: Stable matching, part 1.
-
Reading: Chapter 1.1; Chapters 2,3.
-
1/23:
-
Lecture: Stable matching, part 2.
-
1/25:
-
Lecture:
Greedy scheduling algorithms.
-
Reading: Chapter 4.1, 4.2.
-
1/28:
-
Lecture:
Five representative problems.
-
Reading:
Chapter 1.2.
-
1/30:
-
Lecture:
Minimum spanning tree; Kruskal's algorithm.
-
Reading:
Chapter 4.5.
-
2/1:
-
Lecture:
Implementing Kruskal's algorithm using union-find.
-
Reading:
Chapter 4.6.
-
2/4:
-
Lecture:
Divide and conquer algoithms: Multiplying polynomials
and integers (Karatsuba's algorithm).
-
Reading:
Chapter 5.1, 5.2, 5.5.
-
2/6:
-
Lecture:
The Fast Fourier Transform
-
Reading:
Chapter 5.6.
-
2/8:
-
Lecture:
Divide and conquer algorithms in computational geometry:
finding the closest pair of points.
-
Reading:
Chapter 5.4.
-
2/11:
-
Guest lecturer: Jon Kleinberg.
-
Lecture:
Introduction to dynamic programming; weighted interval scheduling.
-
Reading:
Chapter 6.1.
-
2/13:
-
Lecture:
Computing RNA secondary structure.
-
Reading:
Chapter 6.5.
-
2/15:
-
Lecture:
Edit distance.
-
Reading:
Chapter 6.6.
-
2/18:
-
Lecture:
Bellman-Ford shortest path algorithm.
-
Reading:
Chapter 6.8-6.10.
-
2/20:
-
Lecture:
Review of dynamic programming.
-
Reading:
Chapter 6.1-6.2, 6.5-6.6, 6.8-6.10.
-
2/22:
-
Lecture:
Introduction to network flow.
-
Reading:
Chapter 7.1.
-
2/25:
-
Lecture:
The Ford-Fulkerson algorithm for maximum flow.
-
Reading:
Chapter 7.1-7.3.
-
2/27:
-
Lecture:
The max-flow/min-cut theorem, flow integrality.
-
Reading:
Chapter 7.1-7.3.
-
2/29:
-
Lecture:
The preflow-push algorithm for maximum flow.
-
Reading:
Chapter 7.4.
-
3/3:
-
Lecture:
Baseball elimination
-
Reading:
This lecture is based on Chapter 7.12.
The week's reading is Chapter 7, Sections 5 through 13.
-
3/5:
-
Lecture:
Image segmentation
-
Reading:
Chapter 7.10
-
3/7:
-
Lecture:
Maximum matching
-
Reading:
Chapters 7.5, 7.13.
-
3/10:
-
Lecture:
Introduction to NP-completeness
-
Reading:
Chapter 8.1
-
3/12:
-
Lecture:
Some basic reductions: 3SAT, clique, vertex cover, independent set
-
Reading:
Chapters 8.1, 8.2.
-
3/14:
-
Lecture:
The Cook-Levin Theorem
-
Reading:
Chapters 8.3, 8.4.
-
3/24:
-
Lecture:
NP-complete sequencing problems: Hamiltonian cycle.
-
Reading:
Chapter 8.5
-
3/26:
-
Lecture:
NP-complete sequencing problems: Hamiltonian cycle and path, traveling salesman problem.
-
Reading:
Chapter 8.5
-
3/28:
-
Lecture:
NP-complete covering and packing problems:
set cover, set packing, independent set in degree-3 graphs.
-
Reading:
Chapter 8.1
-
3/31:
-
Lecture:
NP-complete partitioning problems: 3-dimensional matching.
NP-complete numerical problems: subset sum.
-
Reading:
Chapters 8.6, 8.8
-
4/2:
-
Lecture:
Pseudo-polynomial time algorithms. Fixed-parameter tractability.
-
Reading:
Chapter 6.4, Chapter 10.1.
-
4/4:
-
Lecture:
Solving NP-Complete problems on trees.
-
Reading:
Chapter 10.2.
-
4/7:
-
Lecture:
Review session for Prelim 2.
-
Reading:
None.
-
4/9:
-
Lecture:
Intro to approximation algorithms; greedy approximation
algorithm for load balancing.
-
Reading:
Chapter 11.1
-
4/11:
-
Lecture:
The greedy set cover algorithm.
-
Reading:
Chapter 11.3
-
4/14:
-
Lecture:
The pricing method: weighted vertex cover.
-
Reading:
Chapter 11.4
-
4/16:
-
Lecture:
Introduction to linear programming; LP rounding approximation
algorithm for weighted vertex cover.
-
Reading:
Chapter 11.6
-
4/18:
-
Lecture:
More LP rounding: scheduling on unrelated parallel machines
-
Reading:
Chapter 11.7
-
4/21:
-
Lecture: Randomized algorithms I: Karger's randomized contraction
algorithm for min-cut
-
Reading: Chapter 13.1-13.2
-
4/23:
-
Lecture: Randomized algorithms II: Hashing
-
Reading: Chapter 13.3-13.6
-
4/25:
-
4/28:
-
Lecture: Online algorithms I: Caching algorithms
-
Reading:
Chapter 13.8
-
4/30:
-
5/2:
-
Lecture:
Packet switching
-
Reading:
Epilogue of Kleinberg-Tardos.