Site menu:

Course notes

Lecture 1 (May 1): Introduction [pdf, one]
  • string equality
  • course overview
  • linearity expectation: quicksort
Lecture 2 (May 3): Tail inequalities [pdf, one]
  • Markov inequality
  • Chebyshev inequality
  • Chernoff bounds
Lecture 3 (May 8): Graph algorithms [pdf, one]
  • color coding
  • minimum cut
  • minimum spanning tree
Lecture 4 (May 10): Approximation algorithms [pdf, one]
  • graph sparsification
  • LP rounding: congestion minimization
  • SDP rounding: maximum cut
Lecture 5 (May 15): Balls and bins [pdf, one] (updated May 15)
  • maximum load, coupon collector
  • heuristic argument, power of two choices
Lecture 6 (May 17): Hashing [pdf, one]
  • pairwise independence, universal hash functions
  • perfect hashing, derandomization
Lecture 7 (May 24)
  • finishing hashing
Lecture 8 (May 29): Data streaming [pdf, one]
  • heavy hitters, distinct elements, frequency moments
Lecture 9 (May 31): Polynomial identity testing [pdf, one]
  • Schwartz-Zippel lemma, parallel matching
Lecture 10 (Jun 12): Network coding [pdf, one]
  • distributed algorithm, matrix rank
Lecture 11 (Jun 14): Interactive proofs [pdf, one]
  • graph non-isomorphism, number of satisfying assignments
Lecture 12 (Jun 19): Probabilistic methods [pdf, one]
  • first moment method, second moment method
Lecture 13 (Jun 21): Entropy [pdf, one]
  • extraction, compression, error correcting codes
Lecture 14 (Jun 26)
  • finishing entropy
Lecture 15 (Jun 28): Local lemma [pdf, one]
  • k-SAT, packet routing, algorithmic proof
Lecture 16 (July 3): Random walks on directed graphs [pdf, one]
  • Markov chains, pagerank, regular bipartite matching
Lecture 17 (July 5): Random walks on undirected graphs [pdf, one]
  • 2-SAT, 3-SAT
  • electrical networks, commute time, cover time
Lecture 18 (July 10): Mixing time [pdf, one]
  • Lovasz-Simonovits curve, graph partitioning
Lecture 19 (July 12)
  • finishing mixing time
Lecture 20 (July 17): Markov chain Monte Carlo [pdf, one]
  • Monte Carlo method: DNF counting, network reliability
  • Markov chain Monte Carlo method, approximate counting
Lecture 21 (July 19): Coupling [pdf, one]
  • stationary distribution, card shuffling, radnom spanning tree, independent set
Lecture 22 (July 24): Metric embedding [pdf, one]
  • dimension reduction, Bourgain's theorem, sparsest cut
Lecture 23 (July 26): Randomized linear algebra [pdf, one]
  • spectral sparsification, fast linear regression