Randomized Algorithms

Prerequisites: Basic algorithms and elementary probability.

Objective: To understand how fundamental probabilistic tools can be applied to the design and analysis of algorithms.

Class Timings and Venue:
Wednesdays: 9:45 – 11:15
Fridays: 11:30 – 13:00
Room: NB 327

Textbooks:

[MR] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[MU] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2005.

Other References (to be updated over time):

[DP] Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomised Algorithms. Cambridge University Press, 2009.

[HP] Sariel Har-Peled. Randomized Algorithms: Class Notes. University of Illinois at Urbana–Champaign, 2024.
https://sarielhp.org/teach/notes/algos/files/book.pdf

[KT] Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson Education, 2006.

Grading Policy: TBD

Lecture 1: Introduction to the course. Polynomial identity testing and the distinct elements problem in streaming as motivating examples.

Lectures 2–3: Random variables, expectation and its properties, analysis of Quicksort and Selection, geometric random variables, the coupon collector problem, Markov's inequality, and Las Vegas vs. Monte Carlo algorithms.

Lectures 4–5: Approximation algorithms for Max-Cut and Max-3-SAT, algorithms for large independent sets, connections to the probabilistic method, and an overview of Karger’s Min-Cut algorithm.

Lecture 6: Karger’s Min-Cut algorithm, counting the number of minimum cuts, the Galton–Watson branching process, and the Fast-Cut algorithm.

Lectures 7–8: Jensen’s inequality, conditional expectation and its properties, analysis of Quicksort and Selection using conditional expectation, high-probability bounds for Quicksort, variance and its properties, and Chebyshev's inequality.

Lecture 9: Binomial random variables, the parameter estimation problem, and the power of sampling for finding an element in a given range.

Lectures 10–11: Selection algorithms with high success probability, pairwise independence, approximation algorithm for Max-Cut, moment generating functions, and an introduction to Chernoff bounds.

Lecture 12: Chernoff bounds and applications to the parameter estimation problem and discrepancy minimization.

Lecture 13: Hoeffding’s bound with proof, applications to sum estimation, and Janson’s inequality with applications to counting triangles in random graphs.

Lecture 14: The Johnson–Lindenstrauss Lemma and dimensionality reduction, including the proof using Rademacher (±1) random variables and applications.

Lectures 15–16: Balls and bins, the birthday paradox, load balancing under random allocation, and the power of two choices with full analysis.

Lecture 17: Dictionary Data Structures and Hashing, Universal Hash Families, and Perfect Hashing. 

Lecture 18: Derandomization of 1/2-approximate algorithm for MAX-CUT using 2-universal hash families, Derandomization using the method of conditional expectation, An application of universal hash family in the streaming model.

Lecture 19 and 20: The Lovász Local Lemma: Existence, Applications, and Algorithmic Version.