CS60029 Randomized Algorithm Design

Instructor:

 Palash Dey

Teaching Assistants:

 Souradip Guha, Karwa Prachi Mukesh Kiran

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: Monday 12-12:55 PM, Tuesday 10-11:55 AM

Grading:
Assignment:10%, Class test: 5%, Mid-term: 30%, Final: 55%

Announcements:

Lectures:
Lecture notes: here

Question Papers:


Assignments:
First assignment: here
Second assignment: here
Third assignment: here
Fourth assignment: here


6 January 1. Review of Basic Probability
7 January 2. Review of Basic Probability cont., Polynomial Identity Testing and its Application
13 January 3. Randomized Quick Sort
14 January 4. Color Coding Technique, Concentration Inequalities -- Markov, Chebbyshev, and Chernoff Bounds
20 January 5. Flipping Coin, Coupon Collector Problem
21 January 6. Balls and Bins
27 January Class Test 1
28 January 7. Two Points Sampling, Randomized Algorithm for 2SAT
3 Febuary 8. Introduction to Markov Chain
4 February 9. Fundamental Theorem of Markov Chain, Metropolis Algorithm
10 February 10. Markov Chain on Independent Sets of a Graph
11 February 11. Random Walk on Cycles, Shuffling Cards, Hitting Time, Commute Time, Cover Time
17 February Mid-semester Examination
18 February
24 February
25 February
2 March Tutorial
3 March Monte Carlo Method: DNF Counting, Independent Sets Counting
9 March No Class -- Institute Holiday
10 March Probabilistic Method


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