This course studies algorithms which, by design, may not be correct 100% of the time, or run within the stipulated resource always, but definitely do so in an overwhelmingly large number of cases. The course will be split into three main logical sections - tools from probability theory, algorithms which are probabilistic and analysis of deterministic algorithms for different input distributions. Some of the topics include Markov chain, random walk, Monte Carlo sampling, Minimax theorem, Randomised algorithms, Probabilistic analysis of Quicksort and Hashing.
Be able to analyse events of probability (in computational problems)
Be able to analyse an algorithm using probability
Be able to design a randomised algorithm with provable bounds
Understand different random processes occurring in problems
Understand sources and usages of randomness for solving problems