Randomized Algorithms

Randomized Algorithms (Fall 2019)

Course description: This course studies the use of randomness in algorithms. Topics include basic probability, the minimax principle, limited independence, concentration inequalities, balls and bins, hashing, fingerprinting, Bloom filters, network coding, graph sparsification, symmetry breaking, randomized approximation, streaming algorithms, and random walks.

Textbooks:  There is no course text. However, about half the material we cover can be found in the following text books.

• Randomized Algorithms by Motwani and Raghavan. Cambridge University Press.

• Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Mitzenmacher and  Upfal. Cambridge University Press.

Prerequisites: Mathematical maturity and comfort with undergraduate algorithms and basic probability.

Schedule

Lectures were held on Tuesdays from 14:00–17:00, with an occasional Wednesday session from 14:00–15:30.

• Lecture 1: Basic notions—verifying polynomial inequalities, probability spaces and functions, inclusion–exclusion, independent events, conditional probability, the law of total probability, randomized min-cut, and stable marriage [Scribe]

• Lecture 2: Random variables and expectation, linearity of expectation, Jensen’s inequality, Bernoulli and binomial random variables, conditional expectation, geometric distribution, coupon collector, stable marriage, and the expected running time of Quicksort [Scribe]

• Lecture 3: Moments and deviations—Markov’s inequality, variance and moments, Chebyshev’s inequality, coupon collector, and a randomized algorithm for computing the median [Scribe]

• Lecture 4: Chernoff bounds and basic applications, including coin flips and hypergraph coloring [Scribe]

• Lecture 5: Routing in hypercube networks [Scribe]

• Lecture 6: Balls and bins—maximum load, Chernoff bounds, and the power of two choices [Scribe]

• Lecture 7: Universal hashing, perfect hash families, and connections to parameterized hash families [Scribe]

• Lecture 8: Constructions of pairwise- and k-wise-independent random variables [Scribe]

• Lecture 9: Cuckoo hashing [Scribe]

• Lecture 10: Consistent hashing and negative binomial random variables [Scribe]

• Lecture 11: Fingerprinting and string matching [Scribe]

• Lecture 12: Bloom filters [Scribe]

• Lecture 13: Polynomial fingerprinting, perfect matching, and network coding [Scribe]

• Lecture 14: Symmetry breaking, parallel algorithms, independent sets, and derandomization [Scribe]

• Lecture 15: The isolation lemma and perfect matching [Scribe]

• Lecture 16: Shortest paths [Scribe]

• Lecture 17: Sampling and polling; streaming algorithms for frequent items, sketches, and distinct items [Scribe]

• Lecture 18: Sampling and transitive closure; DNF counting and rare events [Scribe]

• Lecture 19: Counting versus generation [Scribe]

• Lecture 20: Linear-time minimum spanning trees [Scribe]

• Lecture 21: Min-cuts and the recursive contraction algorithm [Scribe]

Additional material and references will be added as needed.