CS60029 Randomized Algorithm Design 2024

CS60029 Randomized Algorithm Design

Instructor:

Palash Dey and Somindu Chaya Ramanna

Teaching Assistants:

Shivam Sourav

Course overview:
Randomization has been serving as a central idea in algorithm design in particular and theoretical computer science in general. Indeed, randomized algorithms are often tend to be simple and thus practically useful than their deterministic counter parts yet provides matching guarantees. This is the case, for example, for randomized quick sort algorithm, randomized minimum cut algorithm, etc. Other than algorithm design, randomization has also been used to come up with path breaking proof techniques, for example, probabilistic methods, probabilistically checkable proof, etc. in theoretical computer science. In this course, we will introduce these probabilistic techniques with state of the art applications to the students so that they can apply it in their research whenever needed.

Classes:
Venue: CSE-108
Timings: Wednesday (10:00-10:55) , Thursday (09:00-09:55) , Friday (11:00-11:55)

Grading:
TBD

Announcements:

We will also assume knowledge of Algorihtms I and strong inclination for theoretical computer science. Note that is an advanced subject in algorithms.
First class will be on July 23 at 10 AM in CSE-108.
First class test will be on August 21 during class hours. Seating plan is here. Question paper: this, solution sketch: this

Lectures:
Running lecture notes: here

Week 1	Jul 23	Review of Basic Probability
	Jul 24
	Jul 25	Institute Class Suspension
Week 2	Jul 30	Polynomial Identity Testing Schwartz-Zippel Lemma Perfect Bipartite Matching Randomized Quick Sort
	Jul 31
	Aug 1
Week 3	Aug 6	Color Coding Markov and Chebyshev's Inequalities Chernoff's Bound and its Application Coupon Collector Problem Birthday Paradox Balls and Bins
	Aug 7
	Aug 8
Week 4	Aug 13	Balls and Bins Two Point Sampling
	Aug 14
	Aug 15	Institute Holiday
Week 5	Aug 20	Integer Multi-Commodity Flow
	Aug 21	First Class Test

Practice Problems:

Practice problem set on basic probability and PIT: here
Practice problem set on color coding, contentration bounds, and coupon collector problem: here

References:

Randomized Algorithms: Rajeev Motwani, Prabhakar Raghavan
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Eli Upfal and Michael Mitzenmacher