Lesson 247
Randomized Algorithms
Las Vegas + Monte Carlo
1:00How flipping a coin inside an algorithm defeats adversarial inputs and drives error probabilities to negligible levels — Las Vegas, Monte Carlo, and probability amplification.
By the end, you can
- Explain why a fixed deterministic pivot rule is exploitable by an adversary.
- Describe how a random pivot gives randomized quicksort an expected O(n log n) bound on every input.
- Define Las Vegas and Monte Carlo algorithms and state what each trades randomness for.
- Classify randomized quicksort, quickselect, Miller-Rabin, and Karger's min-cut into the correct family.
- Compute the error probability of k independent Miller-Rabin rounds given a per-round error of 1/4.
- Explain why probability amplification requires independent rounds.
- Explain what "one-sided error" means in the context of Miller-Rabin.
- Describe how Karger's min-cut is used in practice to find a minimum cut with high probability.
- Refute the misconception that randomized algorithms are inherently unreliable.
Up next in Advanced Algorithms, Math & PL Theory
