Schedule of Lectures
Lecture: Course overview.
Bipartite maximum matching. Augmenting paths.
Reading: Kozen, Lecture 19.
Lecture: Matchings II: The Hopcroft-Karp algorithm.
Reading: Kozen, Lecture 20.
- No class because of Labor Day
- Lecture: Network Flow I:
Network flow and the Max-Flow Min-Cut Theorem.
Kozen, Lecture 16. (Alternate: Kleinberg-Tardos, Chapter 7.1 and 7.2.)
Lecture: Network Flow II: Ford-Fulkerson and Edmonds-Karp.
Reading: Kozen, Lecture 17.
Lecture: Network Flow IV: Dinitz's algorithm.
Reading: Kozen, Lecture 18.
A very interesting historical account of how this and other max-flow algorithms were discovered is contained in this paper by Yefim Dinitz. The paper also contains a technical exposition of Dinitz's algorithm, but the exposition in Kozen's book is easier to follow.
Lecture: Network Flow V: Preflow-Push.
Reading: Kleinberg-Tardos, Chapter 7.4.
Lecture: Linear programming I: Introduction to linear programming.
Lecture: Linear programming II: The simplex method.
The lectures will primarily follow these
notes by Vince Conitzer.
Lecture: Linear programming III: LP duality.
Lecture: Spectral Methods III: The planted clique problem.
Guest lecturer: David Steurer
N. Alon, M. Krivelevich, and B. Sudakov,
Finding a large hidden clique in a random graph,
Rand. Struct. Algorithms 13 (1998), 457-466.
The lecture will cover Sections 1 and 2 of the paper only.
Lecture: Spectral Methods IV: Clustering mixtures of Gaussians.
Guest lecturer: John Hopcroft
Lecture: Complexity I: The complexity classes P and NP,
polynomial time many-one reductions, reducing 3SAT to Independent Set.
Reading: Kozen, Lecture 22.
Lecture: Complexity II: NP-Completeness of Exact Cover,
Subset Sum, Partition, Knapsack.
Reading: Kozen, Lectures 23.3 and 24.
Lecture: Complexity III: NP-Completeness of Hamiltonian
Reading: Kozen, Lecture 24.
Lecture: Approximation Algorithms V: Polynomial time
Reading: Section 11.8 of Kleinberg & Tardos.