Pre-requisites : CS204, MA203
Random numbers: Properties of a random sequence. Generating uniform random numbers: the linear congruential method and others. Statistical tests for random numbers: Chi-square test, Kolmogorov-Smirnov test, empirical / theoretical / spectral tests. Non-uniform random sequences. Tools and techniques of randomized algorithmics: game theoretic techniques, moments and deviations, tail inequalities, the probabilistic method: Lovasz Local Lemma, Markov chains and random walks, algebraic techniques. Applications: Data structures, hashing, linear programming, computational geometry problems, graph problems, approximate algorithms, parallel and distributed algorithms, cryptography, online algorithms. Derandomization techniques.
1. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
2. D. E. Knuth, The Art of Computer Programming, 3rd Ed, Vol 2, Seminumerical Algorithms, Addison-Wesley, 1998.
3. W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968.