Site menu:

Lecture notes

Notes will usually be posted before lecture.

All notes typeset in one file by Felix Zhou! [pdf]
Lecture 1 (May 12): Introduction [pdf] [one] [pptx]
  • course introduction
  • minimum cut
Lecture 2 (May 14): Tail inequalities [pdf] [one] [pptx]
  • Markov, Chebyshev, Chernoff
Lecture 3 (May 19): Applications of tail inequalities [pdf] [one] [pptx]
  • graph sparsification
  • dimension reduction
Lecture 4 (May 21): Balls and bins [pdf] [one] [pptx]
  • maximum load, coupon collector, heuristic argument
Lecture 5 (May 26): Hashing [pdf] [one] [pptx]
  • k-wise independence, universal hash functions, perfect hashing
Lecture 6 (May 28): Data streaming [pdf] [one] [pptx]
  • heavy hitters, distinct elements, frequency moments
Lecture 7 (June 2) [pptx]
  • continuing on data streaming
Lecture 8 (June 4): Polynomial identity testing [pdf] [one] [pptx]
  • string equality, Schwartz-Zippel lemma
  • isolation lemma, parallel matching
Lecture 9 (June 9): Network coding [pdf] [one] [pptx]
  • max-information-flow min-cut, distributed algorithm
Lecture 10 (June 11): Probabilistic methods [pdf] [one] [pptx]
  • first moment method, superconcentrator
  • second moment method, threshold phenomenon
Lecture 11 (June 16): Local lemma [pdf] [one] [pptx]
  • standard examples, algorithmic proof
Lecture 12 (June 18): Random walks [pdf] [one] [pptx]
  • fundamental theorem of Markov chains
  • pagerank, perfect matching in regular bipartite graph
Lecture 13 (June 23): Spectral graph theory [pdf] [one] [pptx]
  • background, adjacency matrix, bipartiteness
  • Laplacian matrix, connectedness, Rayleigh quotient
Lecture 14 (June 25): Cheeger's inequality [pdf] [one] [pptx]
  • spectral partitioning algorithm
Lecture 15 (June 30) [pptx]
  • continuing on Cheeger's inequality
Lecture 16 (July 2): Mixing time [pdf] [one] [pptx]
  • spectral analysis, random sampling
Lecture 17 (July 7): Electrical networks [pdf] [one] [pptx]
  • electrical flow, effective resistance
  • hitting time, cover time
Lecture 18 (July 9): Spectral sparsification [pdf] [one] [pptx]
  • random sampling by effective resistance
Lecture 19 (July 14): Linear programming [pdf] [one] [pptx]
  • basic, vertex, extreme point solutions
  • algorithms, separation oracles
Lecture 20 (July 16): Matching polytopes [pdf] [one] [pptx]
  • bipartite matching, 3-dimensional matching, general assignment problem
Lecture 21 (July 21): Spanning tree polytopes [pdf] [one] [pptx]
  • uncrossing technique, bounded degree spanning trees
Lecture 22 (July 23): Linear programming duality [pdf] [one] [pptx]
  • separation theorem, strong duality, min-max theorems
Lecture 23 (July 28): Multiplicative weight update method [pdf] [one] [pptx]
  • online experts model, solving linear program
Lecture 24 (July 30): Maximum flow and Laplacian solvers [pdf] [one] [pptx]
  • maximum flow via electrical flow, fast Laplacian solvers
  • course review