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 17th 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

We assume knowledge of Algorithms I and a strong inclination for theoretical computer science. Note that this is an advanced course in algorithms.

Evaluation Plan (tentative)

Teacher's Assessment	40% [30% Class Tests/Quizzes + 10% Attendance]
Mid-Semester Examination	30%
End Semester Examination	30%

Lectures

[Details of lectures will be posted here on a weekly basis.]

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).