Randomized Algorithms

Randomized Algorithms (Spring 2019)

Course Description: The course will focus on the use of randomness in algorithms. Over the past few decades, randomization has become an increasingly important part of theoretical computer science. The tentative outline for the course is as follows: Basic probability; the minimax principle; limited independenc, advanced concentration of measure, balls in bins; negatively associated random variables, hashing: universal, perfect, cuckoo, fingerprinting; Bloom filters, Network coding; edge connectivity, graph sparsification, parallel algorithms; symmetry breaking, Randomized approximation algorithms, streaming algorithms, random walks: cover times, markov chains, mixing rates.

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.

Lectures Timing and Schedule:

• Lecture will be held every Tuesday 2 to 5 with break for 15 minutes in between and on some Wednesdays 2 to 3:30 PM.

1. Lecture 1: Collect all the basic notions: Verifying Polynomial Inequalities, Definitions of Probability Space and function, Inclusion-Exclusion Principle, Independent Events, Conditional Probability, Law of Total Probability, Randomized Min-Cut Algorithm [Scribe]
2. Lecture 2: Random Variable and Expectation, Linearity of Expectation, Jensens Inequality, Bernoulli and Binomial Random variables, expectation of these, Conditional Expectation, Geometric Distribution, Coupons Collector Problem and application to Stable Marriage, Expected Run-time of Quicksort [Scribe]
3. Lecture 3: Moments and Deviations: Markov Inequality, Variance and Moments of random Variable, Chebyshevs Inequality, Coupons Collector Problem and Randomized Algorithm for Computing the Median [Scribe]
4. Lecture 4: Chernoff Bounds and its basic applications. Examples: Coin Flip, Coloring the Hypergraph [Scribe]
5. Lecture 5: Routing in Hypercube Networks [Scribe]
6. Lecture 6: Balls and Bins: maximum load shown to be O( log n) direct application of Chernoff and then using direct calculation log n/ log log n; Power of Two (proof using random graphs) [Scribe]
7. Lecture 7: Hashing: Universal hashing and Perfect hash families: Connection to Parameterized hash families [Scribe]
8. Lecture 8: Constructions of pairwise and k-wise independent random variables [Scribe]
9. Lecture 9: Cuckoo hashing [Scribe]
10. Lecture 10: Consistent Hashing and Negative Binomial Random variables [Scribe]
11. Lecture 11: Fingerprinting, string matching [Scribe]
12. Lecture 12: Bloom Filters [Scribe]
13. Lecture 13: Fingerprinting by polynomials, perfect matching, network coding [Scribe]
14. Lecture 14: Symmetry breaking. Parallel algorithms. Independent set and Derandomization [Scribe]
15. Lecture 15: Isolating Lemma. Perfect Matching [Scribe]
16. Lecture 16: Shortest paths [Scribe]
17. Lecture 17: Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items [Scribe]
18. Lecture 18: Sampling: transitive closure. DNF counting, rare events [Scribe]
19. Lecture 19: Counting versus generation [Scribe]
20. Lecture 20: Linear Time MST [Scribe]
21. Lecture 21: Min-cuts: recursive contraction algorithm 1 [Scribe]
22. More lectures to be added as and when we complete. (Scribes are coming)