Lecture Schedule and Syllabus
List of lectures
 8/27:
 Single linkage clustering and mincost spanning trees
 See KleinbergTardos section 4.7.
 8/29:
 9/1: Labor day  no class.
 9/3:
 Matroids and the greedy algorithm.
 9/5:
 9/8:
 Correctness of the mincost arborescence algorithm.
 Bipartite maximum matching, max value matching and the greedy algorithm.
 See the first section of the lecture notes .
 9/10:
 Maximum matching algorithm and augmenting path.
 See the lecture notes or Kozen, Lecture 19.
 9/12:
 The HopcroftKarp algorithm for maximum matching.
 See the lecture notes or Kozen, Lecture 19.
 9/15:
 Mincost perfect matching.
 See KleinbergTardos, 7.13 or Kozen, Lecture 20.
 9/17:
 Mincost perfect matching with prices.
 See KleinbergTardos, 7.13.
 9/19:
 Max flow (lecture by David Shmoys).
 See KleinbergTardos, 7.12.
 9/22:
 Max flow continued (lecture by David Shmoys).
 See KleinbergTardos, 7.23.
 9/24:
 The preflow/push algorithm
 See KleinbergTardos, 7.4.
 9/26:
 The preflow/push algorithm continued
 See KleinbergTardos, 7.4.
 9/28:
 Application of mincut: immage segmentation, and vertex cover in bipartite graphs.
 See KleinbergTardos, 7.10.
 See section 4 of the notes by Bobby Kleinberg for the vertex cover problem.
 10/1:
 10/3:
 Matching, fractional matring (as a linear program), and vertex cover.
 Lecture notes for this and the next couple of lectures see the notes.
 See also the first two pages of KleinbergTardos section 11.6.
 10/6:
 Fractional vertex cover, linear programs, their duals, and weak duality.
 See the lecture notes .
 10/8:
 Strong duality (with a physical proof), and complementary slackness.
 See the following lecture notes .
 10/10:
 10/13: Fall break
 10/15:
 Applications of linear programs to matchings and flows.
 See the lecture notes .
 10/17:
 Disjoint path, multicommodity flow, randomization, linearity of expectation.
 See the last section of the lecture notes .
 See KleinbergTardos 13.34 basics of probability.
 10/20:
 Disjoint path, multicommodity flow, and randomization, union bound.
 See the last section of the lecture notes .
 10/22:
 Chernoff bound for concentration of random variables.
 KleinbergTardos Sec 13.913.10
 10/24:
 Balls and Bins: bounding the maximum congestion in a bin.
 KleinbergTardos Sec 13.913.10
 10/27:
 Path routing and randomized roundling of linear programs.
 See the last section of the lecture notes .
 10/29:
 Power of random ordering: secretary problem
 See also the wiki page for the problem.
 10/29:
 10/31:
 Online matching with random arrival order continued
 11/3:
 Online matching with random arrival order.
 11/5:
 MetropolisHastings and Gibbs Sampling algorithms (lecture by John Hopcroft)
 See Sections 5.6 of the
book by Hopcroft and Kannan.
 11/7:
 Mixing time (lecture by John Hopcroft)
 See Sections 5.15.2 of the
book by Hopcroft and Kannan.
 11/10:
 reductions between problems (Vertex Cover > SAT), and the class NP
 11/12:
 NPcompleteness of Circuit Satisfiability, SAT, and 0/1 integer programming.

KleinbergTardos Sec. 8.38.4
 11/14:
 NPcompleteness of 3D Matching
 KleinbergTardos Sec. 8.6
 11/17:
 spectral method intuition (lecture by Jon Kleinberg).
 11/19:
 spectral method : Laplasian matrix and expansion.
 See sections 13 of the lectures notes by Bobby Kleinberg.
 11/21:
 Randomized algorithms: primarity testing.
 11/24:
 Randomized complexity classes, and the randomized primarity testing algorithm.
 11/2628: Thanksgiving break
 12/1:
 Immage segmentation via local search
 See KleinbergTardos, Section 12.6.
 12/3:
 Approximation algorithms via local search
 See KleinbergTardos, Section 12.6.
 12/5:
 Games, Best response, and local search
 See KleinbergTardos, Section 12.7.
Tentative outline of the remainder of the semester
Part 1: Fundamental Algorithms
 Spanning Trees and Related Structures
 Network Flows and their Applications
 Linear Programming
 Randomized Algorithms
Part 2: Dealing with Computational Intractability
 NPcompleteness
 Approximation algorithms
Part 3: Further Algorithmic Techniques
 Spectral Methods
 Online Algorithms and Games
