Real World: Randomized Algorithms

Math for CS · Axiom Academy

Las Vegas, Monte Carlo, and the power of coin flips Deterministic algorithms have a fixed behavior on every input. An adversary who knows your algorithm can craft a worst-case input. Randomized algorithms use random coin flips during execution, making worst-case behavior depend on luck rather than the input. Eliminate adversarial worst cases — no single input is always bad Often simpler and faster than deterministic alternatives Enable algorithms for problems where deterministic solutions are unknown or complex Two Flavors of Randomized Algorithms Example: Randomized quicksort — always sorts correctly, but the number of comparisons varies. Example: Miller-Rabin primality test — runs in polynomial time, but may incorrectly call a composite number "probably prime." The classic Las Vegas algorithm. Instead of choosing a fixed pivot (e.g., first element), choose a random pivot: Expected comparisons: No matter what the input is, the expected number of comparisons is: Expected vs. Worst-Case Analysis There's an important distinction between three types of "average": Average-case (deterministic): Average over all inputs , assuming a distribution on inputs. Problem: real inputs may not follow your assumed distribution. Expected time (randomized): Average over the algorithm's random choices , for the worst-case input. Much stronger — holds for every input.

This is the written version of the interactive lesson above. See the full Math for CS course.