main page — CS 627 Advanced Algorithms
Unit 7: Randomization Basics
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
This unit covers
- probability theory recap
- models of computation with randomization
- Las Vegas and Monte Carlo algorithms
Material
- slides
- Video 7-1 · transcript (2025-06-10, 17:34):
Randomization motivation
- Video 7-2 · transcript (2025-06-10, 29:55):
Randomized selection by rank (deterministic adversary lower bound, Floyd-Rivest algorithm)
- Video 7-3 · transcript (2025-06-11, 36:46):
Probability theory recap
- Video 7-4 · transcript (2025-06-11, 39:50):
Probabilistic Turing machines
- Video 7-5 · transcript (2025-06-17, 11:10):
Las Vegas and Monte Carlo algorithms
- Video 7-6 · transcript (2025-06-17, 1:07:11):
Contrenration Bounds: Markov, Chebyshev, Chernoff
- Video 7-7 · transcript (2025-06-18, 1:01:20):
Concentration Bounds in Action
Further reading and sources
Many examples are taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.
The exposition on probability theory and probabilistic Turing machines is my own, based on various sources.