CS503RANDOMIZED ALGORITHMS3-0-0-6

Pre-requisites : CS204, MA203

Syllabus :
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.

Texts :

References :
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.