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:

• Wednesdays: 9:45–11:15 and Fridays: 11:30–13:00.
  
  

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.

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, Approximate max-cut algorithm.