Randomized Algorithms and Probabilistic Analysis


Stanford School of Engineering

  • Fee:
    Fee may apply

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.

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.


Note on Course Availability

This course is typically offered Autumn quarter.

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 certificate homepage.

005 Autumn 2019-20 Online

Enroll Now

Dates:September 23 - December 6, 2019
Days: Mon
Units: 3.00
Instructors: Greg Valiant
Delivery Option:
For Credit $3,900.00 ?


Enrollment Dates: August 1 to September 9, 2019

Computer Science Department Requirement
Students taking graduate courses in Computer Science must enroll for the maximum number of units and maintain a B or better in each course in order to continue taking courses under the Non Degree Option.

This course may not currently be available to learners in some states and territories.