Schedule of Lectures
- 8/22:
-
Lecture: Matchings I:
Bipartite maximum matching.
-
Reading: Kozen, Lecture 19.
- 8/24:
-
Lecture: Matchings II:
The Hopcroft-Karp algorithm.
-
Reading: Kozen, Lecture 20.
- 8/27:
- 8/29:
-
Lecture: Matchings IV: Finish bipartite min-cost 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 Max-Flow Min-Cut Theorem.
(Guest lecturer: Dexter Kozen)
-
Reading:
Kozen, Lecture 16. (Alternate: Kleinberg-Tardos, 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: Kleinberg-Tardos, 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) 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.
- 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:
-
In-class 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 many-one reductions, reducing 3SAT to Independent Set.
-
Reading: Kozen, Lecture 22.
- 11/12:
-
Lecture: Complexity II: NP-Completeness of Exact Cover,
Subset Sum, Partition, Knapsack.
-
Reading: Kozen, Lectures 23.3 and 24.
- 11/14:
-
Lecture: Complexity III: NP-Completeness 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 Johnson-Lindenstrauss Lemma.
-
Reading: Nick Harvey's lecture notes on
the
Johnson-Lindenstrauss Lemma.
- 11/30: