Part 9 · 1 chapters · ~8 min

Randomised Algorithms

Why randomness helps (expected performance, avoiding adversarial inputs), quickselect and randomised quicksort, reservoir sampling, shuffling correctly (Fisher-Yates), Monte Carlo versus Las Vegas algorithms, probabilistic data structures (Bloom filters, HyperLogLog, count-min sketch, skip lists), and seeding for reproducibility.

Randomness as a tool

code

// Fisher-Yates shuffle: every permutation equally likely (sort(() => Math.random() - 0.5) is biased)
function shuffle<T>(a: T[]): T[] { for (let i = a.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [a[i], a[j]] = [a[j], a[i]]; } return a; }

// reservoir sampling: a uniform sample of k items from a stream of unknown length, O(k) memory
function reservoir<T>(stream: Iterable<T>, k: number): T[] {
  const r: T[] = []; let n = 0;
  for (const x of stream) { n++; if (r.length < k) r.push(x); else { const j = Math.floor(Math.random() * n); if (j < k) r[j] = x; } }
  return r;
}
// quickselect: the k-th smallest in O(n) expected (median latency without full sorting)

kind	guarantee	example
Las Vegas	always correct, running time is random	randomised quicksort, quickselect
Monte Carlo	fixed time, answer correct with high probability	Miller-Rabin primality test, Bloom filters (false positives)
probabilistic structures	small memory, bounded error	HyperLogLog (count distinct users in 12 KB), count-min sketch (heavy hitters), skip lists (Redis sorted sets)

Use a seeded generator in tests and simulations so failures replay (Distributed Systems part 13). Use crypto.getRandomValues, never Math.random, for anything security-related (tokens, OTPs).