Site menu:

Lecture notes

Notes will usually be posted before lecture.

Lecture 1 (May 2): Introduction [pdf] [one]
  • course introduction
  • minimum cut
Lecture 2 (May 7): Tail inequalities [pdf] [one]
  • Markov, Chebyshev, Chernoff
  • graph sparsification
Lecture 3 (May 9)
  • finishing tail inequalities
Lecture 4 (May 14): Balls and bins [pdf] [one] (updated May 15)
  • maximum load, coupon collector
  • heuristic argument
Lecture 5 (May 16)
  • finishing balls and bins
Lecture 6 (May 22): Hashing [pdf] [one]
  • pairwise independence
  • universal hash functions, perfect hashing
Lecture 7 (May 23)
  • finishing hashing
Lecture 8 (May 28): Data streaming [pdf] [one]
  • heavy hitters, distinct elements, frequency moments
Lecture 9 (May 30): Polynomial identity testing [pdf] [one]
  • string equality, Schwartz-Zippel lemma, parallel matching
Lecture 10 (Jun 4)
  • finishing parallel matching
Lecture 11 (Jun 11): Network coding [pdf] [one]
  • distributed algorithm
Lecture 12 (Jun 13): Probabilistic methods [pdf] [one]
  • first moment method, second moment method
Lecture 13 (Jun 18): Local lemma [pdf] [one]
  • applications, algorithmic proof
Lecture 14 (Jun 20)
  • finishing local lemma, midterm review
Lecture 15 (Jun 25): Random walks [pdf] [one]
  • stationary distribution, pagerank, regular bipartite matching
Lecture 16 (Jun 27): Spectral graph theory [pdf] [one]
  • background, graph spectrum, Laplacian matrix, Rayleigh quotient
Lecture 17 (July 4)
  • finishing basic spectral graph theory
Lecture 18 (July 9)
  • finishing basic spectral graph theory
Lecture 19 (July 11): Cheeger's inequality [pdf] [one]
  • spectral partitioning algorithm
Lecture 20 (July 16): Mixing time [pdf] [one]
  • spectral analysis
Lecture 21 (July 18): Electrical networks [pdf] [one]
  • effective resistance, hitting time
Lecture 22 (July 23): Multiplicative weight update method [pdf] [one]
  • online experts, solving linear programs
Lecture 23 (July 25): Review and preview [pdf] [one]
  • preview: maximum flow, spectral sparsification, Laplacian solver.