Schedule of Lectures
 8/25:

Lecture: General announcements.
Bipartite minimumcost perfect matching.

Reading: Kozen, Lecture 19.
 8/27:
 8/30:
 9/1:

Lecture: The HopcroftKarp algorithm for maximum unweighted bipartite matching.

Reading: Kozen, Lecture 20.
 9/3:
 9/6:

Lecture: No class because of Labor Day.
 9/8:

Lecture: Network flow, the FordFulkerson algorithm,
and the MaxFlow MinCut Theorem.

Reading:
Kozen, Lecture 16. KleinbergTardos, Chapter 7.1 and 7.2.
 9/10:

Lecture: Strongly polynomial maxflow algorithms: EdmondsKarp
and Dinitz.

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/13:

Lecture: The preflowpush algorithm.

Reading:
KleinbergTardos, Chapter 7.4.
 9/15:
 9/17:

Lecture: Introduction to matroids and minimum spanning trees.

Reading:
Kozen, Lectures 2.1 and 3.
 9/2022:
 9/2427:
 9/2910/1:
 10/46:

Lecture: Linear programming, the simplex method, and LP duality.

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

For an alternative treatment
of the algorithm from a much more geometric perspective, see these
notes by Avner Magen.

A helpful mnemonic for remembering how to
form the dual of a linear program is the SOB method, described in
this article by Arthur T. Benjamin.
 10/8:
 10/13:

Lecture: Solving linear programs using multiplicative
weights: the PlotkinShmoysTardos algorithm.
NOTE: The preceding set of lectures actually
ended on October 13, and consequently this topic was skipped.

Reading: Section 2 (at least up to Theorem 2.5) of
Fast approximation algorithms for fractional packing and covering problems.
S. Plotkin, D. Shmoys, and É. Tardos. Math. of Operations Research, 1995.
 10/15:

MIDTERM EXAM: Inclass test covering material up to and including the simplex method and LP duality. This will be an openbook, opennotes exam.
 10/18:

Lecture: The Fast Fourier Transform, part I: Reduction
from convolution to polynomial multiplication, and from polynomial
multiplication to multipoint polynomial evaluation.

Reading: Kozen, Lecture 35. Kleinberg and Tardos, Section 5.6.
 10/20:

Lecture: The Fast Fourier Transform, part II:
Divide and conquer algorithm for evaluating polynomials at
complex roots of unity.

Reading: Kozen, Lecture 35. Kleinberg and Tardos, Section 5.6.
 10/22:
 10/25:

Lecture: Introduction to fast matrix multiplication:
Strassen's algorithm. Fast LU decomposition, matrix inversion, determinant.

Reading: None. The following supplementary reading
is not required, but may be useful for understanding parts of this lecture.
 10/27:

Lecture: Application of fast matrix multiplication to
perfect matchings in graphs. The SchwartzZippel
Lemma.

Reading: Mucha and
Sankowski, Maximum Matchings via Gaussian Elimination, FOCS 2004.
The following additional materials are not required, but may be useful
as supplementary material or to aid in understanding some parts of the
lecture.
 Chapter 3 of Marcin Mucha's Ph.D. thesis contains a more leisurely presentation of the preceding algorithm.
is not required, but may be useful for understanding parts of this lecture.
 Motwani and Raghavan, Randomized Algorithms,
Chapters 7.2 and 7.3.
 Harvey, Algebraic Algorithms for Matching and Matroid Problems, FOCS 2006, contains algorithms for nonbipartite matching and for matroid intersection inspired by the MuchaSankowski Gaussian Elimination technique.
 10/29:

Lecture: Introduction to NPCompleteness.
Basic definitions. Reductions from CNFSAT to 3CNFSAT
and from 3CNFSAT to Independent Set.

Reading: Kozen, Lectures 21 and 22.
 11/1:

Lecture: Continuation of NPCompleteness.
More on gadget reductions. NPcompleteness of Hamiltonian
Cycle.

Reading: Kozen, Lectures 23 and 24.
 11/3:

Lecture: NPcompleteness of Hamiltonian
Path, Clique, Vertex Cover, Set Cover, Set Packing,
Triple Matroid Intersection, Independent Set in
BoundedDegree Graphs.

Reading: None.
 11/5:

Lecture: NPcomplete numerical problems.
Subset Sum, Partition, Load Balancing.

Reading: None.
 11/8:

Lecture: Approximation Algorithms I:
Polynomialtime approximation schemes. Approximation
algorithms for the Knapsack problem.

Reading: KleinbergTardos Chapters 11.1, 11.8.
 11/10:

Lecture: Linear programming and approximation
algorithm design. LProunding and primaldual approximation
algorithms for vertex cover.

Reading: Lecture
notes on approximation algorithms, Sections 1.1 and 1.2.
 11/12:
 11/15:
 11/17:
 11/19:

Lecture: Dynamic programming in graphs
of bounded treewidth.

Reading: KleinbergTardos, Chapter 10.4.
 11/22,29:

Lecture: Markov chains and stationary distributions.

Reading: Alistair Sinclair's lecture notes on
Markov chains and random walks,
Lecture 2 and
Lecture 3.
 12/1:
 12/3:

Lecture: Bounding the mixing time of Markov chains
using coupling.

Reading: Sinclair,
Lecture 4 and
Lecture 5.