Site menu:

Lecture notes

Notes will usually be posted before lecture.

All notes typeset in one file by Felix Zhou for CS 466/666 Spring 2020 [pdf]
Some notes for linear algebra background (read Section 2.1) [pdf]
Lecture 1 (May 2): Introduction [pdf] [one]
  • course introduction
  • minimum cut
Lecture 2 (May 4,9): Tail Inequalities [pdf] [one]
  • Markov, Chebyshev, Chernoff inequalities
Lecture 3 (May 11): Applications of Tail Inequalities [pdf] [one]
  • graph sparsification, (minimum cut), dimension reduction
Lecture 4 (May 16,18): Balls and Bins [pdf] [one]
  • maximum load, coupon collector
  • heuristic arguments (Poisson approximation), power of two choices
Lecture 5 (May 25,30): Hashing [pdf] [one]
  • k-wise independence, universal hash functions, perfect hashing
Lecture 6 (June 1): Data Streaming [pdf] [one]
  • heavy hitter, distinct elements, frequency moments
Lecture 7 (June 6): Polynomial Identity Testing [pdf] [one]
  • string equality, Schwartz-Zippel, parallel matching
Lecture 8 (June 8,13): Network Coding [pdf] [one]
  • max-information-flow min-cut theorem, distributed algorithm
Lecture 9 (June 15,20): Probabilistic Methods [pdf] [one]
  • Ramsey graphs, superconcentrators
  • second moment method, threshold phenomenon
Lecture 10 (June 20,22): Local Lemma [pdf] [one]
  • applications, constructive algorithm
Lecture 11 (June 27,29): Random Walks [pdf] [one]
  • fundamental theorem, pagerank
  • perfect matching in regular bipartite graphs
Lecture 12 (July 4, 6): Spectral Graph Theory [pdf] [one]
  • background, adjacency matrix, bipartiteness
  • Laplacian matrix, connectedness, Rayleigh quotient
Lecture 13 (July 11): Cheeger's Inequality [pdf] [one]
  • spectral partitioning algorithm
Lecture 14 (July 13): Mixing time [pdf] [one]
  • spectral analysis, random sampling
Lecture 15 (July 18,20): Electrical Networks [pdf] [one]
  • electrical flows, effective resistances, hitting time, cover time
Lecture 16 (July 25): Bonus
  • spectral sparsification, Laplacian solver
  • multiplicative weight update, maximum flow