CS60029 Randomized Algorithm Design 2023

CS60029 Randomized Algorithm Design

Instructor:

Palash Dey and Somindu Chaya Ramanna

Teaching Assistants:

Sipra Singh

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-120.
Timings: Wednesday 12-12:55 PM, Thursday 11-11:55 AM, Friday 9-9:55 AM,
Extra slot for class tests and tutorial: Friday 10-10:55 AM.

Grading:
Class test: 10%, Student's presentation: 10%, Mid-term: 30%, Final: 50%

Announcements:

For non-CS students, the cut off is 8.5 cgpa. We will also assume knowledge of Algorihtms I.
First class test is scheduled on September 1, 2023 in CSE-120. Question paper with solution is here.
Mid-semester examination scheduled on September 22, 2023. Seating arrangement is here. Question paper is here.
Topics for students' presentation is here. Form groups of size at most two and submit your choice here by Oct 13.

Lectures:
Lecture notes: here

Week 1	Aug 2	Review of Basic Probability Polynomial Identity Testing, Schwartz-Zippel Lemma
	Aug 3
	Aug 4
Week 2	Aug 9	Perfect Bipartite Matching Karger's Min-cut Algorithm Randomized Quick sort Markov, Chebyshev, and Chernoff Bounds
	Aug 10
	Aug 11
Week 3	Aug 16	Coupon Collector Problem Birthday Paradox Balls and Bins
	Aug 17
	Aug 18	No Class (Institute Foundation Day)
Week 4	Aug 23	Two Point Sampling Markov Chain
	Aug 24
	Aug 25
Week 5	Aug 30	Random Walk Mixing Time Coupling
	Aug 31
	Sep 1
Week 6	Sep 6	Markov Chain Monte Carlo (MCMC) Simulation Counting Solutions of DNF Counting independent sets
	Sep 8
	Sep 7	No Class (Janmashtami)
Week 7	Sep 13	Probabilistic Method Lovasz Local Lemma Derandomization
	Sep 14
	Sep 15
Week 8	Sep 27	Perfect Hashing, Cuckoo Hashing, Bloom Filter
	Sep 28	No Class (Prophet's birthday)
	Sep 29	Count Min Sketch
Week 9	Oct 4	Universal Hashing Sub-Gaussian Random Variables Martingales
	Oct 5
	Oct 6
Week 10	Oct 11	Stopping Time Theorem Azuma-Hoeffding Inequality McDiarmid's Inequality, Applications
	Oct 12
	Oct 13

Practice Problems:

Practice problem set on contentration bounds and their applications: here; solution sketch: here
Practice problem set on Markov chain: here
Practice problem set on martingales: 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