Randomized Algorithms (expected time, seeds)

Randomization trades certainty for expected performance—QuickSort pivots, Monte Carlo primality, reservoir sampling. Always bound failure probability and fix seeds in tests for determinism.

Why this shows up in the real world

Load balancers randomize shard placement. Robotics samples configuration space.

Core idea (explained for students)

Use random.randint or secrets for crypto-grade needs. Analyze expected value: E[T] = sum p_i * cost_i.

Try this in Python

import random


def random_pivot_partition(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    p = random.choice(a)
    low = [x for x in a if x < p]
    eq = [x for x in a if x == p]
    high = [x for x in a if x > p]
    return random_pivot_partition(low) + eq + random_pivot_partition(high)


random.seed(0)
print(random_pivot_partition([3, 1, 4, 1, 5])[:5])

Common mistakes

• Tiny modulo bias when drawing from ranges not dividing evenly.
• Flaky CI from unseeded randomness.

Key takeaways

• Document Las Vegas vs Monte Carlo (always correct vs probably fast).
• For interviews, know when random pivot avoids adversarial inputs.