22902 Randomized Algorithms
Credits: 4 graduate credits in Computer Science
Prerequisite: Admission to the graduate program in Computer Science 1
Required: Computability and Introduction to Complexity (or another course in complexity)
The course is based on Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by M. Mitzenmacher & E. Upfal (Cambridge University Press, 2005).
The course discusses algorithms that make random choices as they proceed. It provides basic tools for the design and analysis of such algorithms. It examines the role of randomness in computation and algorithmic design. The role of randomness in computation is central to computer science and familiarity with the field is necessary for dealing with areas such as computational complexity, data structures, computational geometry, and approximation algorithms. The course deals with classic problems such as median-finding, hashing (especially Bloom filters) and threshold behavior in random graphs. The course is theoretical in nature, requiring a background in probability theory and linear algebra.
1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.