Randomised Algorithm Design

CS60029, Autumn 2026, LTP: 3-0-0

Instructors Abhranil Chatterjee and Somindu Chaya Ramanna
Teaching assistant Shashank Mittal
Classes WED: 10:00 - 10:55; THUR: 09:00-09:55; FRI: 11:00-11:55 at CSE-119
Tutorials on Saturdays

Notices and Announcements

Prerequisites

Any student registering for this course must have done Algorithms I. In addition, we assume rudimentary knowledge of probability theory and a strong inclination for theoretical computer science. Note that this is an advanced course in algorithms.

Evaluation Plan (tentative)

Teachers' Assessment     40%   [30% Class Tests/Quizzes + 5% Scribe + 5% Attendance]
Mid-Semester Examination     30%
End Semester Examination     30%

Scribing Notes: Each lecture will be assigned to a student (or a group of students) chosen by us. Lecture notes must be typeset using LaTeX. When scribing notes, you should use a template that we will share here soon. A first draft of the scribed notes must be submitted to us (both the instructors) as a tex file (without compilation errors) via email, within one week of the lecture. The scribed notes should not be an expository article on the topic covered in class. Instead, like any hand-written lecture notes, it should convey exactly the material covered in class, in the way it is covered in class.

Lectures

Week Date Topics Covered
1 22 July Introduction, Computational Complexity Perspective, Review of Basic Probability, Isolation Lemma
23 July Review of Basic Probability, Proof of Isolation Lemma
24 July Application of Isolation Lemma: Bipartite Perfect Matching, Karger's Min-Cut Theorem
2 29 July Polynomial Identity Lemma
30 July Longest Path Problem, Color Coding
31 July Randomized Quick Sort, Markov and Chebyshev's Inequalities
3 5 August Analysis of Randomized Quick Sort, Sampling based Median Finding Algorithm
6 August Sampling based Median Finding Algorithm (continued)
7 August Chernoff Bounds
4 12 August Revisiting the Important Probability Bounds, Unbiased estimator: Median trick
13 August Unbiased estimator: Median trick, Birthday Paradox, Balls and Bins
14 August Balls and Bins: Expected Maximum Load, Coupon Collector Problem

Tutorial on Problem Set 1
5 19 August Two Point Sampling
20 August Monte Carlo Method, Estimating Pi, FPRAS for DNF Counting
21 August FPRAS for DNF Counting, Universal Hashing

Class Test 1
6 26 August Institute Holiday (Milad-Un-Nabi)
27 August Application to dynamic data structures: Collision resolution by chaining
Construction of a 2-universal hash family
28 August Perfect Hashing, Bloom Filters
7 2 September Application to Data Streaming: Count-Min Sketch
3 September Cuckoo Hashing, Dimensionality Reduction
4 September Institute Holiday (Janmashtami)
8 9 September Proof of Johnson-Lindenstrauss Lemma
10 September Probabilistic method - method of expectation, alteration
11 September Lovász Local Lemma and its applications
9 16 September Method of Conditional Probabilities - Derandomization
17 September Sub-Gaussian Random Variables, Hoeffding Bounds
18 September Tutorial on Problem Sets 2 and 3
21 September - 1 October Mid-Semester Examination

References

  1. Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan.

  2. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by by Eli Upfal and Michael Mitzenmacher.

  3. Lecture Notes on Randomised Algorithm Design (CS60029) by Palash Dey (available here).

Practice Problems

Problem Set 1

Problem Set 2

Problem Set 3