Algorithms are required to be “correct” and “fast”. In a wide variety of applications, these twin objectives are in conflict with each other. Fortunately, neither of these ideals is sacrosanct. Therefore we can often try to optimize one of these goals by incurring a small penalty on the other. This takes us to the field of Randomized Algorithms. Often, the randomized variants, in addition to being faster than their deterministic counterpart, are simpler to understand and implement. In this course, we will study the tradeoff between correctness and speed. We will be learning a number of methods to design and analyze randomized algorithms.
INTENDED AUDIENCE: Senior UG students, PG students, and Ph.D. candidates interested in computer science, combinatorics, etc.
What Will I Learn?
- Week 1 : Introduction to Randomized Algorithms
- Week 2 : Probability Review
- Week 3 : Moments and Deviation
- Week 4 : The Probabilistic Method
- Week 5 : Markov Chains - I
- Week 6 : Markov Chain - II
- Week 7 : Number Theoretic Algorithms
- Week 8 : Graph Algorithms
- Week 9 : Approximate Counting
- Week 10: Data Structures
- Week 11: Computational Complexity
- Week 12: Review of the course