CS60029 Randomized Algorithm Design 2024

CS60029 Randomized Algorithm Design

Instructor:

Palash Dey and Somindu Chaya Ramanna

Teaching Assistants:

Pranav Nyati and Atishay Jain

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-10:55, Thursday 9-9:55 AM, Friday 11-11:55 AM,

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

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 24 at 10 AM in CSE-108
First class test will be on August 23 during class hours.
Mid-semester examination will be held on September 24, 2-4 PM in CSE-107.
Presentation topics: here. Topic allocation: here. Presentation schedule: here.

Lectures:
Running lecture notes: here

Week 1	Jul 24	Review of Basic Probability Polynomial Identity Testing, Schwartz-Zippel Lemma Perfect Bipartite Matching
	Jul 25
	Jul 26
Week 2	Jul 31	Karger's Min-cut Algorithm Karger-Stein Algorithm Randomized Quick Sort Markov and Chebyshev's Inequalities
	Aug 1
	Aug 2
Week 3	Aug 7	Chernoff's Bound and its Application Coupon Collector Problem Birthday Paradox Balls and Bins Two Point Sampling
	Aug 8
	Aug 9
Week 4	Aug 14	Introduction to Markov Chain Randomized Algorithm for 2SAT Random Walk on Graphs
	Aug 16
Week 5	Aug 21	Metropolis Algorithm Mixing Time Coupling
	Aug 22
	Aug 23	First Class Test
Week 6	Aug 28	Monte Carlo Method Estimating the value of pi Estimator Theorem Counting Solutions of DNF Counting independent sets
	Aug 29
	Aug 30
Week 7	Sep 4	Probabilistic Method Lovasz Local Lemma Derandomization: Method of Conditional Expectation
	Sep 5
	Sep 6

Practice Problems:

Practice problem set on basic probability, PIT, and min cut: here
Practice problem set on contentration bounds and their applications: here
Practice problem set on Markov chain: here
Practice problem set on probabilistic method: here
Practice problem set on hash functions, sub-Guassian random variables, Heoffding bound: 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