Failure Modes
l Monte Carlo algorithms always run fast
and probably give you the right answer
l Las Vegas algorithms probably run fast
and always give you the right answer
l To make a Monte Carlo algorithm Las
Vegas, need a way to check answer
» repeat till answer is right
l No fast min-cut check known (flow slow!)