| Course Code: CS503 Course Name: Randomized Algorithms 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: 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. 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. |