Las Vegas and Monte Carlo
- Algorithms course
- Expert
- Lesson 11/41
- 4 min
Compare Las Vegas and Monte Carlo.
Las Vegas and Monte Carlo
Las Vegas algorithms always give the correct result; runtime is random. Monte Carlo algorithms finish in fixed time but the result is probabilistic.
Which to use depends on the problem. Las Vegas for exact results; Monte Carlo for fast results.
Approximation ratio
The quality of an approximate solution is measured by the approx / optimal ratio. The closer to 1, the better the solution.
A 2-approximation algorithm can give a solution up to twice the optimum in the worst case. This is acceptable for NP-complete problems.
Practice approx_ratio function
Write approx_ratio(approx, optimal). Return (approx * 10) // optimal (ratio scaled by 10). Print 10 with print(approx_ratio(9, 9)).
Starter code
def approx_ratio(approx, optimal):
# Compute approximation ratioSample solution
def approx_ratio(approx, optimal):
# Compute approximation ratio
return (approx * 10) // optimal
print(approx_ratio(9, 9))Expected output
10
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Las Vegas and Monte Carlo: match the terms
| Term | Meaning |
|---|---|
Las Vegas |
Exact |
Monte Carlo |
Probabilistic |
time |
Non-fixed |
result |
Correct |
2 What does an approximation ratio of 1 mean?
- Worse than optimal
- Twice optimal
- No upper bound
- Optimal Correct answer
Explanation: A ratio of 1 means the solution is optimal.
3 Ratio computation
ratio = (approx * ____) // optimalratio = (approx * 10) // optimalExplanation: 10 is right.