CS 6820 (Fall 2014)
Index · Schedule and Syllabus · Handouts and Problem Sets · CMS · Piazza

Lecture Schedule and Syllabus

List of lectures

  • 8/27:
    • Single linkage clustering and min-cost spanning trees
    • See Kleinberg-Tardos section 4.7.
  • 8/29:
  • 9/1: Labor day - no class.
  • 9/3:
    • Matroids and the greedy algorithm.
  • 9/5:
    • Arborescences in directed graphs
    • Kleinberg-T Sec 4.9.

    • Also: L. Lovasz. On two minimax theorems in graph theory, J. Combin. Theory B 21(1976), 96-103.

  • 9/8:
    • Correctness of the min-cost 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 Hopcroft-Karp algorithm for maximum matching.
    • See the lecture notes or Kozen, Lecture 19.
  • 9/15:
    • Min-cost perfect matching.
    • See Kleinberg-Tardos, 7.13 or Kozen, Lecture 20.
  • 9/17:
    • Min-cost perfect matching with prices.
    • See Kleinberg-Tardos, 7.13.
  • 9/19:
    • Max flow (lecture by David Shmoys).
    • See Kleinberg-Tardos, 7.1-2.
  • 9/22:
    • Max flow continued (lecture by David Shmoys).
    • See Kleinberg-Tardos, 7.2-3.
  • 9/24:
    • The preflow/push algorithm
    • See Kleinberg-Tardos, 7.4.
  • 9/26:
    • The preflow/push algorithm continued
    • See Kleinberg-Tardos, 7.4.
  • 9/28:
    • Application of min-cut: immage segmentation, and vertex cover in bipartite graphs.
    • See Kleinberg-Tardos, 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 Kleinberg-Tardos 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 Kleinberg-Tardos 13.3-4 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.
    • Kleinberg-Tardos Sec 13.9-13.10
  • 10/24:
    • Balls and Bins: bounding the maximum congestion in a bin.
    • Kleinberg-Tardos Sec 13.9-13.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:
    • Metropolis-Hastings 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.1-5.2 of the book by Hopcroft and Kannan.
  • 11/10:
    • reductions between problems (Vertex Cover > SAT), and the class NP
  • 11/12:
    • NP-completeness of Circuit Satisfiability, SAT, and 0/1 integer programming.
    • Kleinberg-Tardos Sec. 8.3-8.4
  • 11/14:
    • NP-completeness of 3D Matching
    • Kleinberg-Tardos Sec. 8.6
  • 11/17:
    • spectral method intuition (lecture by Jon Kleinberg).
  • 11/19:
    • spectral method : Laplasian matrix and expansion.
    • See sections 1-3 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/26-28: Thanksgiving break
  • 12/1:
    • Immage segmentation via local search
    • See Kleinberg-Tardos, Section 12.6.
  • 12/3:
    • Approximation algorithms via local search
    • See Kleinberg-Tardos, Section 12.6.
  • 12/5:
    • Games, Best response, and local search
    • See Kleinberg-Tardos, Section 12.7.

    Tentative outline of the remainder of the semester

    Part 1: Fundamental Algorithms

    1. Spanning Trees and Related Structures
    2. Network Flows and their Applications
      • Linear Programming
      • Randomized Algorithms

    Part 2: Dealing with Computational Intractability

    1. NP-completeness
    2. Approximation algorithms

    Part 3: Further Algorithmic Techniques

    1. Spectral Methods
    2. Online Algorithms and Games