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 are 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. - Dr Benny George K, IIT Guwahati.

COURSE LAYOUT

- Introduction to Randomized Algorithms
- Probability Review
- Moments and Deviation
- The Probabilistic Method
- Markov Chains - I
- Markov Chain - II
- Number Theoretic Algorithms
- Graph Algorithms
- Approximate Counting
- Data Structures
- Computational Complexity
- Review of the course

### Recommended Books

- Rajeev Motwani and Prabhakar Raghavan,Randomized Algorithms
- Michael Mitzenmacher and Eli Upfal Probability and Computing