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 and Fridays: 11:30–13:00.

• Room no: 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)

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

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

Grading Policy: TBD

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

Lecture #2 and #3: Random variable, expectation and its properties, Quick Sort, Selection, Geometric random variable, Coupon collector problem, Markov inequality, Las Vegas and Monte Carlo algorithms.

Lecture #4 and #5: Approximate Max-Cut algorithm, Approximate Max-3-Sat algorithm, Algorithm for large independent set, Connection to probabilistic method, Overview of Karger's Min-Cut algorithm.

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

Lecture #7 and #8: Jensen's Inequality, Conditional expectation and its properties, Analysis of Quicksort and Selection using conditional expectation, High probability bound for Quicksort. Variance and Chebyshev inequality.