MIT
2
Randomized Algorithms
lFlip
coins to decide what to do next
lAvoid
hard work of making “right” choice
lOften
faster and simpler than deterministic
algorithms
lDifferent
from average-case analysis
»Input
is worst case
»Algorithm
adds randomness