NPTEL Randomized Algorithms

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

  1. Introduction to Randomized Algorithms
  2. Probability Review
  3. Moments and Deviation
  4. The Probabilistic Method
  5. Markov Chains - I
  6. Markov Chain - II
  7. Number Theoretic Algorithms
  8. Graph Algorithms
  9. Approximate Counting
  10. Data Structures
  11. Computational Complexity
  12. Review of the course
  1. Rajeev Motwani and Prabhakar Raghavan,Randomized Algorithms
  2. Michael Mitzenmacher and Eli Upfal Probability and Computing