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

First class will be held on the 22nd of July.
Approval for joining the course will be based on CGPA. Those who are not familiar with the course prerequisites (mentioned below) are strongly discouraged from joining this course.

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

References

Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan.

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

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