CS60029 Randomized Algorithm Design

Instructor:

 Palash Dey

Teaching Assistants:

 Pritam Bhattacharya and Subhrangsu Mandal

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-107. Timings: Monday (8:00-9:55), Tuesday (12:00-12:55)

Grading:
 Class test: 20% (best of two), Mid-term: 30%, Final: 50%

Announcements:
Lectures:
Lecture notes: here

Question Papers:
Final examination: here
Midsemester examination: here
First class test: here
Second class test: here

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

7 January 1. Review of Basic Probability
8 January 2. Polynomial Identity Testing, Schwartz-Zippel Lemma
14 January 3. Reduction from Perfect Bipartite Matching to PIT, Randomized Quick sort, Markov, Chebyshev, and Chernoff bounds
15 January 4. Tossing coins, coupon collector problem, birthday paradox
21 January 5. Balls and bins, Two point sampling
22 January 6. Randomized rounding: Multi-commodity flow
28 January 7. Introduction to Markov chain, randomized algorithm for 2SAT, stationary distribution
29 January 8. Irreducible and aperiodic Markov chain, fundamental theorem of Markov chain (statement only), coupling, Random walk
4 February 9. Metropolis Algorithm, Mixing time of Random Walk on Cycles, Proof of the fundamental Theorem of Markov chains
5 February 10. Finishing proof of the fundamental Theorem of Markov chains, hitting time, commute time, cover time
11 February 11. Monte Carlo Method, FPRAS for DNF Counting
12 February 12. FPRAS for Independent Set Counting using Monte Carlo Method
18 February No class (Mid-semester examinationy)
19 February No class (Mid-semester examination)
25 February No class (Mid-semester examination)
26 February No class (Mid-semester examination)
4 March No class (Institute holiday)
5 March 13. Overview of Path Coupling, Introduction to Probabilistic Methods
11 March 14. Probabilistic method -- method of expectation, alteration; Lovasz Local Lemma and its application
12 March 14. Method of Conditional Expectation for Derandomization, Introduction to Universal Hash Family
18 March 15. Perfect Hashing, Cuckoo Hashing, Bloom Filter, Count Min Sketch, Construction of Universal Hash Family
19 March 16. Nearest Neighbor Search (NNS), Point Location in Equal Balls (PLEB)
25 March 17. Locality Sensitive Hashing (LSH)
26 March 18. Johnson Lindenstrauss Lemma
1 April 19. Sub-Gaussian Random Variables, Introduction to Probabilistic Tree Embedding
2 April No class
8 April 20. Probabilistic Tree Embedding, Buy at Bulk Network Design
9 April 21. Martingale: Definition, Doob's Martingale, Stopping Time Theorem (without proof), Wald's equation
15 April 22. Azuma-Hoeffding Inequality, McDiarmid's Inequality, Applications
16 April 23. Problem Solving Session


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