Randomized Algorithms and Probabilistic Analysis

Description

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.

Prerequisites

CS 161 and STAT 116, or equivalents and instructor consent.

Topics include

• 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.

Course Availability

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.