Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

Lecture 1 (Jan 20): Introduction [pdf] [one]
  • course introduction and administration
  • randomized min-cut
Lecture 2 (Jan 22): Tail inequalities [pdf] [one]
  • Markov, Chebyshev, Chernoff
  • graph sparsification
Lecture 3 (Jan 27): Balls and bins [pdf] [one]
  • maximum load, coupon collector
  • power of two choices
Lecture 4 (Jan 29): Hashing [pdf] [one]
  • pairwise independence, universal hash functions
  • perfect hashing
Lecture 5 (Feb 3): Data streaming [pdf] [one]
  • heavy hitters
  • distinct elements
  • frequency moments
Lecture 6 (Feb 5): no new notes
  • finish lecture 5
Lecture 7 (Feb 10): Polynomial identity testing [pdf] [one]
  • string matching, Schwartz-Zippel lemma
  • graph matching, isolation lemma, parallel algorithm
Lecture 8 (Feb 12): Network coding [pdf] [one]
  • random linear coding
  • matrix rank
Lecture 9 (Feb 17): Probabilistic methods [pdf] [one]
  • first moment method
  • second moment method
Lecture 10 (Feb 19): Local lemma [pdf] [one]
  • k-SAT, algorithmic proof
  • packet routing
Lecture 11 (Feb 24): Random walks [pdf] [one]
  • fundamental theorem, pagerank
  • perfect matching in regular bipartite graphs
Lecture 12 (Feb 26): Linear programming [pdf] [one]
  • basic, vertex, extreme point solutions
  • algorithms, separation oracle
Lecture 13 (Mar 3): Matching polytopes [pdf] [one]
  • 3-dimensional matching
  • general assignment problem
Lecture 14 (Mar 5): Spanning tree polytopes [pdf] [one]
  • uncrossing technique
  • degree bounded spanning trees
Lecture 15 (Mar 10): LP duality [pdf] [one]
  • complementary slackness, strong duality
  • min-max theorems, minimax principle
Lecture 16 (Mar 12): no new notes
  • finish lecture 15
Lecture 17 (Mar 17): Multiplicative update method [pdf] [one]
  • online decision with expert advice
  • solving linear programs
Lecture 18 (Mar 19): Semidefinite programming [pdf] [one](updated)
  • vector programming, Cholesky factorization
  • Lovasz Theta function, perfect graphs
  • maximum cut, graph coloring
Lecture 19 (Mar 31): SDP duality [pdf] [one]
  • weak duality, limit value, strong duality
Lecture 20 (Apr 2): Matrix multiplicative update [pdf] [one]
  • setup, matrix exponential
  • solving semidefinite programs
Lecture 21 (Apr 7): Spectral graph theory [pdf] [one]
  • spectral theorem, graph spectrum
  • Laplacian matrix, Rayleigh quotient
Lecture 22 (Apr 9): Cheeger's inequality [pdf] [one]
  • spectral partitioning algorithm
  • recent generalizations
Lecture 23 (Apr 14): Mixing time [pdf] [one]
  • convergence rate
  • algorithmic applications
Lecture 24 (Apr 16): Small-set expansion [pdf] [one]
  • higher eigenvalues
  • random walks approximation algorithm
Lecture 25 (Apr 21): Electrical networks [pdf] [one]
  • effective resistance
  • hitting time
Lecture 26 (Apr 23): Spectral sparsification [pdf] [one]
  • sampling by effective resistance
  • matrix concentration
Lecture 27 (Apr 28): Laplacian solver [pdf] [one]
  • simple near linear-time algorithm
Lecture 28 (Apr 30): Maximum flow [pdf] [one]
  • electrical flow
  • course summary