Course Websites

CS 574 - Randomized Algorithms

Last offered Spring 2024

Official Description

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. Course Information: 4 graduate hours. No professional credit. Prerequisite: One of CS 473, CSE 414, or MATH 473; one of MATH 461, MATH 463 or STAT 400.

Related Faculty

Randomized AlgorithmsRA60442LEC41530 - 1645 T R  1304 Siebel Center for Comp Sci Sariel Har-Peled