Expert · Module 22 · Lesson 3 of 4
Randomized algorithms
Randomized algorithms flip coins to escape bad inputs, sample fairly, or answer quickly with a small chance of error. Analyzing them means computing expected costs and error probabilities that hold for every input.
By the end you can
- Distinguish Las Vegas algorithms, always correct with random running time, from Monte Carlo algorithms, fast with a bounded error probability
- Shuffle and sample uniformly with Fisher-Yates and reservoir sampling, and prove they are uniform
- Use linearity of expectation and repetition to analyze and strengthen randomized algorithms
Builds on Accounting and potential methods, Quick sort and partitioning.
01 · A question first
Quicksort with a fixed pivot rule is quadratic on some input, and an attacker who knows your rule can send exactly that input. Choose the pivot at random, and no input is bad anymore, only some unlucky coin flips, which are astronomically rare. How can adding randomness make an algorithm more reliable?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Why flip coins?
- Las Vegas and Monte Carlo
- Shuffling correctly
- Sampling a stream
- Tools for analysis
- Practical randomness
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem