CS60029 Randomized Algorithm Design
Instructor:
Palash Dey and Somindu Chaya Ramanna
Teaching Assistants:
TBD
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:
TBD
Timings: TBD
Grading:
TBD
Announcements:
- We will also assume knowledge of Algorihtms I and strong inclination for theoretical computer science. Note that is an advanced subject in algorithms.
Lectures:
Running lecture notes: 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