CS503  RANDOMIZED ALGORITHMS  3006 
Prerequisites : 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: Chisquare test, KolmogorovSmirnov test, empirical / theoretical / spectral tests. Nonuniform 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, AddisonWesley, 1998. 3. W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968. 