Schedule of Lectures
 8/22:

Lecture: Matchings I:
Bipartite maximum matching.

Reading: Kozen, Lecture 19.
 8/24:

Lecture: Matchings II:
The HopcroftKarp algorithm.

Reading: Kozen, Lecture 20.
 8/27:
 8/29:

Lecture: Matchings IV: Finish bipartite mincost perfect matching.

Reading: None.
 8/31:
 9/3:

No class because of Labor Day.
 9/5:
 9/7:
 9/10:

Lecture: Network Flow I:
Network flow and the MaxFlow MinCut Theorem.
(Guest lecturer: Dexter Kozen)

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

Lecture: Network Flow II: The push/relabel algorithm. (Guest lecturer: David Williamson)

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

Lecture: Network Flow III: Dinitz's algorithm.

Reading: Kozen, Lectures 17 and 18. A very interesting historical account of how these (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/17:

No class because of Rosh Hashanah.
 9/19:
 9/21:

Lecture: Linear programming I: The simplex method.

Reading:
The lectures will primarily follow these
notes by Vince Conitzer.
 9/24:

Lecture: Linear programming II: LP duality.

Reading: None.
 9/26:

No class because of Yom Kippur.
 9/28:

Lecture: Linear programming III: The ellipsoid method.

Reading: The lectures will follow these
notes by Santosh Vempala.
 10/1:
 10/3:
 10/5:
 10/10:
 10/12:
 10/15:
 10/17:
 10/19:

Lecture: Approximation Algorithms V: Polynomial time
approximation schemes.

Reading: Section 11.8 of Kleinberg & Tardos.
 10/22:

Lecture: Spectral Methods I: Review of spectral
theory of positive semidefinite matrices.

Reading: Spectral methods handout, section 1.
 10/24:

Inclass midterm exam.

Reading: None.
 10/26:

Lecture: Spectral Methods II: The graph Laplacian;
normalization and basic properties.

Reading: Spectral methods handout, section 2.
 10/29:
 10/31:
 11/2:
 11/5:
 11/7:
 11/9:

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

Reading: Kozen, Lecture 22.
 11/12:

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

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

Lecture: Complexity III: NPCompleteness of Hamiltonian
Circuit.

Reading: Kozen, Lecture 24.
 11/16:

Lecture: Complexity IV: Complexity of counting problems; the complexity class #P; the permanent of a matrix.

Reading: Kozen, Lecture 26. (Optional: Lecture 27.)
 11/19:

Lecture: Tree decompositions and treewidth. Dynamic programming
algorithms on graphs of low treewidth.

Reading: Kleinberg & Tardos, Section 10.4.
 11/26:

Lecture: Massive data algorithms I: the streaming model,
frequency estimation algorithms.

Reading: Amit Chakrabarty's lecture notes on data stream algorithms (Dartmouth, Fall 2009), Chapters 0 and 3.
 11/28:

Lecture: Massive data algorithms II: Random projections and
the JohnsonLindenstrauss Lemma.

Reading: Nick Harvey's lecture notes on
the
JohnsonLindenstrauss Lemma.
 11/30: