Schedule of Lectures
-
8/29:
-
Lecture: Depth-first search and its applications.
-
Reading: Kozen, Lectures 1, 2, 4. For a linear-time
algorithm that computes strongly connected components, see
these notes by Umesh Vazirani.
-
9/1-5:
-
9/8-19:
-
Lectures: Minimum spanning trees, binomial and
Fibonacci heaps, and matroids.
-
Reading: Kozen, Lectures 2,3,8,9.
-
9/22-24:
-
9/24-26:
-
9/29:
-
Lecture: Network flow.
-
Reading: Kozen, lecture 16.
-
10/1:
-
Lecture: The Ford-Fulkerson algorithm and the
max-flow min-cut theorem.
-
Reading: Kozen, lecture 16.
-
10/3:
-
Lecture: The Edmonds-Karp 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: NP-completeness: basic definitions
and the Cook-Levin theorem.
-
Reading: Kozen, lectures 21 and 22.
-
10/10:
-
Lecture: NP-completeness 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: NP-completeness of
set packing, independent set in degree-3
graphs, trichromatic set packing, matroid intersection.
-
Reading: None.
-
10/17:
-
Lecture: NP-completeness 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 k-Center 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:
Primal-dual approximation
algorithm for weighted vertex cover.
-
Reading: Kleinberg & Tardos, Section 11.4.
-
11/10:
-
Lecture: Fully polynomial-time 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 move-to-front algorithm
for List Update.
-
Reading: See
these lecture notes
from Avrim Blum's class on approximation and
online algorithms at CMU.
-
11/17-19:
-
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 3-6, and Week 2, Sections 3-4 and Appendix A.
-
11/21:
-
Lecture: The minimax theorem implies a special
case of LP duality. Applying the multiplicative-weights
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):37-57, 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):51-55, 2003.
-
12/3:
-
12/5: