نظرة عامة على البرنامج

CS60029 Randomized Algorithm Design

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.

Instructor and Teaching Assistants

• Instructor: Palash Dey and Somindu Chaya Ramanna
• Teaching Assistants: Sipra Singh

Classes

• Venue: CSE-120
• Timings:
  • Wednesday 12-12:55 PM
  • Thursday 11-11:55 AM
  • Friday 9-9:55 AM
• Extra slot for class tests and tutorial: Friday 10-10:55 AM

Grading

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

Announcements

• For non-CS students, the cut off is 8.5 cgpa. We will also assume knowledge of Algorithms I.
• First class test is scheduled on September 1, 2023 in CSE-120.
• Mid-semester examination scheduled on September 22, 2023.
• Topics for students' presentation. Form groups of size at most two.

Lectures

• Lecture notes: Week 1 | Aug 2 | Review of Basic Probability, Polynomial Identity Testing, Schwartz-Zippel Lemma Week 2 | Aug 9 | Perfect Bipartite Matching, Karger's Min-cut Algorithm, Randomized Quick sort, Markov, Chebyshev, and Chernoff Bounds Week 3 | Aug 16 | Coupon Collector Problem, Birthday Paradox, Balls and Bins Week 4 | Aug 23 | Two Point Sampling, Markov Chain Week 5 | Aug 30 | Random Walk, Mixing Time, Coupling Week 6 | Sep 6 | Markov Chain Monte Carlo (MCMC) Simulation, Counting Solutions of DNF, Counting independent sets Week 7 | Sep 13 | Probabilistic Method, Lovasz Local Lemma, Derandomization Week 8 | Sep 27 | Perfect Hashing, Cuckoo Hashing, Bloom Filter Week 9 | Oct 4 | Universal Hashing, Sub-Gaussian Random Variables, Martingales Week 10 | Oct 11 | Stopping Time Theorem, Azuma-Hoeffding Inequality, McDiarmid's Inequality, Applications

Practice Problems

• Practice problem set on concentration bounds and their applications
• Practice problem set on Markov chain
• Practice problem set on martingales

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