Randomized Algorithms credit:

4 Hours

Basic and advanced concepts in the design and analysis of randomized algorithms. Sampling; concentration inequalities such as Chernoff-Hoeffding bounds; probabilistic method; random walks, dimension reduction; entropy; martingales and Azuma's inequality; derandomization. Randomized algorithms for sorting and searching; graphs; geometric problems. Basics of pseudorandomness and randomized complexity classes. Prerequisite: One of CS 473 , CSE 414 , or MATH 473 ; one of MATH 461 , MATH 463 or STAT 400 .