Academics / Courses / DescriptionsCOMP_SCI 396, 496: Randomized Algorithms
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
336 or Permission of the instructor, shravas@northwestern.eduDescription
The power of randomness is one of the most enduring mysteries of computation. In the last 30+ years, several algorithms have been designed which crucially use randomness and beat their deterministic counterparts in terms of efficiency, simplicity and nearly every other computational resource (with the obvious exception of "randomness"). In this course, we start with simple examples such as pattern matching, primality and go on to explore topics such as the power of Markov chains, hashing of high dimensional data and Martingales.
GENERAL GUIDELINES: Students must have taken either COMP_SCI 336 or have strong math background such as 300 level math courses. The knowledge of probability and mathematical maturity is an absolute must.
A ROUGH OUTLINE OF TOPICS IS:
- Introduction and elementary examples
- Linearity of expectation, Markov's inequality, and the probabilistic method
- Variance, Chebyshev's inequality, and threshold phenomena in graphs
- Chernoff bounds, Low-congestion routing, randomized rounding
- Geometric concentration, random projections, dimension reduction
- More geometry: High-dimensional search and compressed sensing
- The Lovasz Local Lemma
- Power of Markov chain Monte Carlo methods.
REQUIRED TEXTBOOK: Randomized Algorithms by Rajeev Motwani and Prabhaker Raghavan (https://www.amazon.com/Randomized-Algorithms-Rajeev-Motwani/dp/0521474655).
COURSE COORDINATORS: Prof. Shravas Rao
COURSE INSTRUCTOR : Prof. Shravas Rao