Schedule of Lectures

8/29:

Lecture: Depthfirst search and its applications.

Reading: Kozen, Lectures 1, 2, 4. For a lineartime
algorithm that computes strongly connected components, see
these notes by Umesh Vazirani.

9/15:

9/819:

Lectures: Minimum spanning trees, binomial and
Fibonacci heaps, and matroids.

Reading: Kozen, Lectures 2,3,8,9.

9/2224:

9/2426:

9/29:

Lecture: Network flow.

Reading: Kozen, lecture 16.

10/1:

Lecture: The FordFulkerson algorithm and the
maxflow mincut theorem.

Reading: Kozen, lecture 16.

10/3:

Lecture: The EdmondsKarp algorithms.

Reading: Kozen, lecture 17.

10/6:

Lecture: Network flow applications:
Menger's, König's, Hall's, and Dilworth's theorems.

Reading: None.

10/8:

Lecture: NPcompleteness: basic definitions
and the CookLevin theorem.

Reading: Kozen, lectures 21 and 22.

10/10:

Lecture: NPcompleteness of independent set,
clique, vertex cover, and set cover.

Reading: Kozen, lectures 21 and 22.

10/13: FALL BREAK

10/15:

Lecture: Reductions from independent set
and its special cases: NPcompleteness of
set packing, independent set in degree3
graphs, trichromatic set packing, matroid intersection.

Reading: None.

10/17:

Lecture: NPcompleteness of exact cover,
subset sum, partition, knapsack, bin packing.
Dynamic programming algorithm for subset sum
with small numbers.

Reading: Kozen, lectures 23 and 24 (first 3 pages).
Kleinberg & Tardos, Sections 6.4 and 8.8.

10/20:

Lecture: Independent set in trees. Tree
decompositions and treewidth.

Reading: Kleinberg & Tardos, Sections 10.3 and 10.4.

10/22:

Lecture: Dynamic programming in graphs of
bounded treewidth. Computing a tree
decomposition.

Reading: Kleinberg & Tardos, Sections 10.4 and 10.5.

10/24:

Lecture: Computing a tree decomposition.

Reading: Kleinberg & Tardos, Section 10.5.

10/27: Class cancelled.

10/29:

Lecture: Introduction to approximation algorithms.
Metric Traveling Salesman Problem and Christofides' algorithm.

Reading: None.

10/31:

Lecture: The Metric kCenter Problem, and
two approximation algorithms for Unweighted Vertex Cover.

Reading: Kleinberg & Tardos, Section 11.2.

11/3:

Lecture: Linear programming and its use in approximation
algorithms. Weighted vertex cover via LP rounding.

Reading: Kleinberg & Tardos, Section 11.6.

11/5:

Lecture: Linear programming duality.

Reading: For some notes on LP duality, see Lecture 21 from
this course on approximation algorithms, by Anupam Gupta and
R. Ravi at Carnegie Mellon University.

11/7:

Lecture:
Primaldual approximation
algorithm for weighted vertex cover.

Reading: Kleinberg & Tardos, Section 11.4.

11/10:

Lecture: Fully polynomialtime approximation scheme
for the knapsack problem.

Reading: None.

11/12:

Lecture: Introduction to online algorithms
and competitive analysis. Ski rental and list update.

Reading: See
these lecture notes
from Avrim Blum's class on approximation and
online algorithms at CMU.

11/14:

Lecture: Analysis of movetofront algorithm
for List Update.

Reading: See
these lecture notes
from Avrim Blum's class on approximation and
online algorithms at CMU.

11/1719:

Lecture: Randomized prediction algorithms:
Weighted majority, Hedge.
Application to game theory: von Neumann's
minimax theorem.

Reading: See
these lecture notes
from my class "Learning, Games, and Electronic Markets"
(Cornell, 2007). The material that
was taught in CS 6820 this fall corresponds
to Week 1, Sections 36, and Week 2, Sections 34 and Appendix A.

11/21:

Lecture: The minimax theorem implies a special
case of LP duality. Applying the multiplicativeweights
algorithm (via the minimax theorem)
to approximately solve network flow and
multicommodity flow problems.

Reading: None.

11/24:

12/1:

Lecture: Introduction to streaming
algorithms. Two simple algorithms: reservoir
sampling and finding a majority element.

Reading:

J. S. Vitter,
Random sampling with a reservoir
,
ACM Trans. Mathematical Software, 11 (1):3757, 1985.

R. M. Karp, S. Shanker, and C. H. Papadimitriou,
A simple algorithm for finding frequent elements in streams and bags
,
ACM Trans. Database Systems, 28 (1):5155, 2003.

12/3:

12/5: