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
Mid-semester question paper is here.
Second class test will be on October 31 during class hours. Seating plan is here.

Lectures:
Running lecture notes: here

Week 1	Jul 23	Review of Basic Probability	Palash
	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
	Aug 22	Yao's Lemma Lower Bound on Randomised Sorting	Somindu
Week 6	Aug 27	Introduction to Markov Chains
	Aug 28	Randomized Algorithm for 2SAT
	Aug 29	Fundamental Theorem of Markov Chain Random Walks on Graphs
Week 7	Sep 3	Hitting Time, Commute Time, Cover Time Coupling, Mixing Time of Random Walk
	Sep 4
	Sep 5	Institute Class Suspension
Week 8	Sep 10	Metropolis Algorithm Mixing Time and Coupling - Applications
	Sep 11
	Sep 12
Week 9	Oct 8	Monte Carlo Method, FPRAS for DNF Counting PRAS for Independent Set Counting using Monte Carlo Method Probabilistic Method -- Method of Expectation, Alteration
	Oct 9
	Oct 10
Week 10	Oct 15	Lovasz Local Lemma and Its Application Method of Conditional Expectation for Derandomization
	Oct 16		Palash
	Oct 17
Week 11	Oct 22	Universal Hashing Perfect Hashing Count-Min Sketch Cuckoo Hashing Bloom Filter
	Oct 23
	Oct 24

Practice Problems:

Practice problem set on basic probability and PIT: here
Practice problem set on color coding, contentration bounds, and coupon collector problem: here
Practice problem set on Markov chain: here
Practice problem set on probabilistic method: here
Practice problem set on hash functions: 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