Randomized Algorithms and Probabilistic Analysis
Fee may apply
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.
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.
|Dates:||September 23 - December 6, 2019|
Provides Stanford University credit that may later be applied towards a graduate degree or certificate. Includes access to online course materials and videos for the duration of the academic quarter. Starting Autumn 2016 there is a $100 fee per course for courses dropped before the drop deadline. Click here for more information about our Registration Policies.
NotesEnrollment 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.