Schedule of Lectures
 8/28:

Lecture: Course overview.
Matchings I:
Bipartite maximum matching. Augmenting paths.

Reading: Kozen, Lecture 19.
 8/30:

Lecture: Matchings II: The HopcroftKarp algorithm.

Reading: Kozen, Lecture 20.
 9/2:
 No class because of Labor Day
 9/4:
 9/6:
 9/9:
 9/11:
 9/13:
 9/16:
 Lecture: Network Flow I:
Network flow and the MaxFlow MinCut Theorem.

Reading:
Kozen, Lecture 16. (Alternate: KleinbergTardos, Chapter 7.1 and 7.2.)
 9/18:

Lecture: Network Flow II: FordFulkerson and EdmondsKarp.

Reading: Kozen, Lecture 17.
 9/20:
 9/23:

Lecture: Network Flow IV: Dinitz's algorithm.

Reading: Kozen, Lecture 18.
A very interesting historical account of how this and other maxflow 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.
 9/25:

Lecture: Network Flow V: PreflowPush.

Reading: KleinbergTardos, Chapter 7.4.
 9/27:

Lecture: Linear programming I: Introduction to linear programming.

Reading: None.
 9/30:

Lecture: Linear programming II: The simplex method.
 Reading:
The lectures will primarily follow these
notes by Vince Conitzer.
 10/4:

Lecture: Linear programming III: LP duality.

Reading: None.
 10/7:
 10/9:
 10/11:
 10/16:
 10/18:
 10/21:
 10/23:
 10/25:
 10/28:
 10/30:

Lecture: Spectral Methods III: The planted clique problem.

Guest lecturer: David Steurer

Reading:
N. Alon, M. Krivelevich, and B. Sudakov,
Finding a large hidden clique in a random graph,
Rand. Struct. Algorithms 13 (1998), 457466.
The lecture will cover Sections 1 and 2 of the paper only.
 11/1:

Lecture: Spectral Methods IV: Clustering mixtures of Gaussians.

Guest lecturer: John Hopcroft

Reading: None.
 11/4:

Lecture: Complexity I: The complexity classes P and NP,
polynomial time manyone reductions, reducing 3SAT to Independent Set.

Reading: Kozen, Lecture 22.
 11/6:

Lecture: Complexity II: NPCompleteness of Exact Cover,
Subset Sum, Partition, Knapsack.

Reading: Kozen, Lectures 23.3 and 24.
 11/8:

Lecture: Complexity III: NPCompleteness of Hamiltonian
Circuit.

Reading: Kozen, Lecture 24.
 11/11:
 11/13:
 11/15:
 11/18:
 11/20:

Lecture: Approximation Algorithms V: Polynomial time
approximation schemes.

Reading: Section 11.8 of Kleinberg & Tardos.