Randomized Algorithms and Probabilistic Analysis
This course applies the key tools of probabilistic analysis to probe the behaviors of random processes and algorithms. Randomness can be leveraged to create algorithms and data structures that often are simpler and more efficient than their deterministic counterparts. With an emphasis on theoretical foundations, this course explores the various applications of randomness, such as in machine learning, data analysis, networking, and systems. It also provides a crash course on coding theory and discussion of pertinent recent research.
CS 161 and STAT 116, or equivalents and instructor consent.
- Moment-generating functions
- Tail bounds, random graphs, and expanders
- Metric embeddings
- Probabilistic method
- Lovasz local lemma
- Random walks and Markov chains
- Mixing times, martingales, and stopping times
- Azuma-Hoeffding inequality
- Many powerful and elegant randomized algorithms whose analyses rely on the above tools.
The course schedule is displayed for planning purposes – courses can be modified, changed, or cancelled. Course availability will be considered finalized on the first day of open enrollment. For quarterly enrollment dates, please refer to our graduate education section.
Thank you for your interest. No sections are available. Please click the button below to receive an email when the course becomes available again.