Site menu:

Lecture notes

Notes will usually be posted before lecture.

Lecture 1 (May 6): Introduction [pdf] [one]
  • course introduction
  • string equality, randomized quicksort
Lecture 2 (May 8): Tail inequalities [pdf] [one]
  • Markov, Chebyshev, Chernoff
Lecture 3 (May 13): Graph algorithms [pdf] [one]
  • color coding, minimum cut, minimum spanning tree
Lecture 4 (May 15): Approximation algorithms [pdf] [one]
  • graph sparsification, congestion minimization
Lecture 5 (May 22)
  • continuing on lecture 3 and 4
Lecture 6 (May 27): Balls and bins [pdf] [one]
  • maximum load, coupon collector, heuristic argument
Lecture 7 (May 29): Hashing [pdf] [one]
  • pairwise independence, universal hash functions, perfect hashing
Lecture 8 (June 3)
  • continuing on lecture 7
Lecture 9 (June 5): Data streaming [pdf] [one]
  • heavy hitters, distinct elements, frequency moments
Lecture 10 (June 10)
  • continuing on data streaming
Lecture 11 (June 12)
  • continuing on data streaming
Lecture 12 (June 17): Polynomial identity testing [pdf] [one]
  • Schwartz-Zippel lemma, parallel matching, isolation lemma
Lecture 13 (June 19): Network coding [pdf] [one]
  • max-information-flow min-cut, random linear code
Lecture 14 (June 24)
  • continuing on network coding
Lecture 15 (June 26): Probabilistic methods [pdf] [one]
  • first moment method, second moment method
Lecture 16 (July 2)
  • continuing on probabilistic methods
Lecture 17 (July 3): Local lemma [pdf] [one]
  • simple applications, algorithmic proof
Lecture 18 (July 8): Random walks [pdf] [one]
  • fundamental theorem of Markov chain
  • pagerank, perfect matching in regular bipartite graphs
Lecture 19 (July 10): Random walks on undirected graphs [pdf] [one]
  • 2-SAT, 3-SAT
  • electrical networks, hitting times, cover time
Lecture 20 (July 15)
  • continuing on random walks on undirected graphs
Lecture 21 (July 17): Markov chain Monte Carlo method [pdf] [one]
  • Monte Carlo method, DNF counting, network reliability
  • Markov chain Monte Carlo method, approximate counting
Lecture 22 (July 22)
  • continuing on Markov chain Monte Carlo method
Lecture 23 (July 24): Coupling [pdf] [one]
  • coupling lemma, card shuffling, random spanning tree
Lecture 24 (July 29): Coupling
  • continuing on coupling
  • course review