CodeBlanks Logo Icon CodeBlanks
Login Register

Randomized algorithms

Algorithms using random choices.

Randomized algorithms

A randomized algorithm uses random choices to reach a solution. In some cases it is faster than deterministic algorithms.

Randomized algorithms come in two flavors: Las Vegas that always gives correct results, and Monte Carlo that gives correct results with high probability.

Sampling for maximum

We can find the maximum of an array by checking randomly selected indices. This shows the basis of randomized algorithms.

If all indices are selected, the result is exact. If a subset is selected, the result is probabilistic. This is Monte Carlo style.

Practice sample_max function

Write sample_max(arr, indices). Return the maximum among arr values at indices. Print 9 with print(sample_max([3, 5, 7, 1, 9], [0, 2, 4])).

Starter code

solution.py
def sample_max(arr, indices):
    # Find max among sampled indices

Sample solution

solution.py
def sample_max(arr, indices):
    # Find max among sampled indices
    best = arr[indices[0]]
    for i in indices:
        if arr[i] > best:
            best = arr[i]
    return best
print(sample_max([3, 5, 7, 1, 9], [0, 2, 4]))

Expected output

9

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Sampling

Question 
for i in ____:
Answer 
for i in indices:

Explanation: indices is right.

2 What does a Monte Carlo algorithm provide?

  • No result
  • Constant time
  • Correct result with high probability Correct answer
  • Always correct result

Explanation: Monte Carlo gives a correct result with high probability.

3 Randomized algorithms: match the terms

Term Meaning
random Random
Monte Carlo Probabilistic
Las Vegas Exact
sample Subset

All lessons in Expert

1 Amortized analysis

  1. What is amortized?
  2. Aggregate method
  3. Dynamic array example
  4. Summary - Amortized

2 NP-completeness

  1. P and NP
  2. NP-complete
  3. Reduction
  4. Summary - NP-completeness

3 Approximation and randomized

  1. Approximation algorithms
  2. Randomized algorithms
  3. Las Vegas and Monte Carlo
  4. Summary - Approximation and randomized

4 String matching

  1. KMP algorithm
  2. Rabin-Karp
  3. Boyer-Moore
  4. Z-algorithm
  5. Suffix array
  6. Summary - String matching

5 Computational geometry

  1. Vector cross product
  2. Convex hull
  3. Line intersection
  4. Closest pair
  5. Point in polygon
  6. Summary - Geometry

6 Network flow

  1. Flow network
  2. Ford-Fulkerson
  3. Edmonds-Karp
  4. Max-flow min-cut
  5. Bipartite matching
  6. Summary - Network flow

7 Game theory and parallel

  1. Minimax
  2. Alpha-beta pruning
  3. Nash equilibrium
  4. Parallel algorithms
  5. MapReduce
  6. Summary - Game theory and parallel

8 Expert final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4
  5. Challenge 5