Randomized Algorithms (CS425/CSE625)

Course description: Suppose a computing machine gets access to some randomness, possibly in the form of the ability to toss coins. How does it help to design algorithms with better guarantees? In this course we will primarily focus on how one can exploit access to randomness to design algorithms for numerous problems and its analysis. We will see examples of randomized algorithms being in action in different use cases, often covering scenarios from our daily lives.

Pre-requisites: Algorithms (CS301). Since this course will be primarily theoretical (mathematical) in nature and we will make heavy use of probability to analyse randomized algorithms, some mathematical maturity is a must for this course. We will cover some basics of probability, but having some prior exposure to probabilistic ideas will be useful.

Textbooks: The primary references for this course will be the following books. I will provide references for any additional material I teach in the class.

• Randomized algorithms by Rajeev Motwani and Prabhakar Raghavan (MR)

• Probability and computing (2nd Edition) by Michael Mitzenmacher and Eli Ufpal (MU) 

For a more introductory reference on probability in computer science, you may refer to this book (Introduction to Probability in for Computing).

Similar courses elsewhere:

• Introduction to Probability (OCW of MIT): Course page, Youtube videos

• Course by Greg Valiant and Mary Wooters: Course page, Youtube videos

• Course by Lap Chi Lau: Course page

• Course by C Seshadri: Course page, Youtube videos

Grading:  Class tests and Quizzes (25%), Midsem (30%), Endsem (40%), Class participation (5%).

Lecture 1 (01/08/2024): Introduction, Randomized quicksort (Section 1 in MR, Section 2.5 in MU)

Lecture 2 (07/08/2024): Complete the analysis of randomized quicksort (Section 1 in MR, Section 2.5 in MU)

Lecture 3 (08/08/2024): Randomized algorithms for min-cut (Section 1.1 of MR, Section 1.5 in MU), Extra material (Section 10.2 in MR)

Lecture 4 (12/08/2024): Balls in bins, birthday paradox (Section 3.1 in MR, Section 5.1 in MU)

Lecture 5 (13/08/2024): Probability analysis of coupon collector, max loaded bin, Introduced concentration inequalities (Markov Chebeshev) (Chap 3 and Section 5.2 in MU)

Tutorial 1 (14/08/2024 by Pinki)

Lecture 6 (20/08/2024): Applications of Markov and Chebyshev inequalities. Introduce Chernoff bounds. (Section 3.1, 3.2, 3.3, 4.2.3 in MU)

Tutorial 2 (21/08/2024 by Pinki)

Lecture 7 (22/08/2024):  Chernoff bounds and applications (Section 4.1,4.2,4.3,4.4 in MU)

Lecture 8 (27/08/2024): Poisson approximation and the power of two choices (Sections 5.4, 17.1 in MU)

Test 1 (28/08/2024): Class test 1

Lecture 9 (29/08/2024): Probabilistic method (Section 6.1, 6.2 in MU)

Lecture 10 (03/09/2024): Probabilistic method (Section 6.3,6.5 in MU)

Tutorial 3 (04/09/2024): Discussed solutions of the class test 1

Lecture 11 (04/09/2024): Finished discussion on the first and second moment methods and Lovasz Local Lemma (Section 6.5,6.7 in MU). The application of first and second moment methods to show bounds for the balls into biis problem can be found here.

Lecture 12 (10/09/2024): Markov chains, 2-SAT algorithm (Section 7.1 in MU)

Tutorial 4 (11/09/2024): 

Lecture 13 (12/09/2024): Finish analysis for 2-SAT, Fundamental theorem of Markov chains (Section 7.1, 7.2 in MU, 6.1,6.2 in MR)

Lecture  14 (17/09/2024): Random walks, stationary probabilities, hitting time, commute time, s-t connectitivity in logspace (Section 7.4 in MU)

Tutorial 5 (18/09/2024 by Pinki)

Lecture 15 (19/09/2024): Finish s-t connectivity in logspace, Randomized algorithm for perfect matching in regular bipartite graphs (Section 7.4 in MU, Lap Chi Lau's notes)

Lecture 16 (15/10/2024): Streaming algorithms, Majority and Frequent elements (Unit 1 of this note)

Tutorial 6 (16/10/2024): Discussed solutions of midsem

Lecture 17( 17/10/2024):  Number of distinct elements in streaming (Unit 2 of this note)

Lecture 18 (22/10/2024): Hashing, k-wise independent hash functions (Chapter 15 in MU: Section 15.1, 15.2, 15.3, 15.3.1)

Lecture 19 (23/10/2024): AMS Sketch, streaming lower bounds using communication complexity (Chapter 1 in this draft)

Lecture 20 (29/10/2024): JL Lemma (Section 2.1, 2.2 in this note)

Lecture 21 (30/10/2024):  Locality sensitive hashing (Section 2.9 in the above note)

Lecture 22 (05/11/2024): Martingales, Azuma's inequality (Section 13.1, 13,4 , 13.5 in MU)

Tutorial 7 (06/11/2024 by Pinki)

Lecture 23 (07/11/2024): Stopping times, Martingale stopping theorem (Section 13.2, 13.3 in MU)

Lecture 24 (12/11/2024): Monte-Carlo method, DNF counting (11.1, 11.2 in MU)

Tutorial 8 (13/11/2024 by Pinki)

Lecture 25 (14/11/2024): Monte-Carlo Method, MCMC (Section 11.3, 11.4 in MU)

Lecture 26 (19/11/2024): Total variation distance, mixing time, Coupling (MU 12.1, 12.2 in MU)

Tutorial 9 (20/11/2024): Tutorial by Pinki

Lecture 27 (21/11/2024): Doubt clearning, discussions on last day of class

Practice problems: Please find a set of practice problems here. More problems will be added as the semester progresses.