DSA Notes
Explore randomized algorithms and probabilistic approaches.
What are Randomized Algorithms?
A randomized algorithm is one that uses random numbers to make decisions during its execution. Instead of following a fixed, deterministic path, it introduces randomness to achieve better average performance, simpler implementation, or solutions to problems that are hard to solve deterministically.
Here is the key insight: sometimes making random choices leads to algorithms that are faster, simpler, or more robust than their deterministic counterparts. Quicksort with random pivot selection, for example, avoids worst-case O(n²) behavior that affects deterministic pivot strategies on sorted inputs.
Comparison Table
| Property | Las Vegas | Monte Carlo |
|---|---|---|
| Correctness | Always correct | May have errors |
| Running time | Random (expected bound) | Fixed/deterministic |
| Error control | Run longer for guarantee | Repeat to reduce error |
| Example | Randomized Quicksort | Miller-Rabin test |
| Guarantee | Correct answer, eventually | Fast answer, probably correct |
Randomized Select (QuickSelect)
Finding the k-th smallest element in O(n) expected time:
Expected time: O(n). Worst case: O(n²) but extremely unlikely with random pivots.
Random Sampling and Estimation
Monte Carlo methods can estimate quantities that are hard to compute exactly:
import random
def estimate_pi(num_samples):
"""Estimate π using random sampling"""
inside_circle = 0
for _ in range(num_samples):
x = random.uniform(-1, 1)
y = random.uniform(-1, 1)
if x*x + y*y <= 1:
inside_circle += 1
# Area of circle / Area of square = π/4
return 4 * inside_circle / num_samples
# More samples = better estimate
print(f"π ≈ {estimate_pi(100000):.4f}") # ~3.1416
print(f"π ≈ {estimate_pi(10000000):.6f}") # ~3.141593The accuracy improves with the square root of the number of samples — to double the accuracy, you need 4x more samples.
Randomized Hashing (Universal Hashing)
Universal hash functions use randomness to guarantee low collision probability for any input:
import random
class UniversalHashFamily:
"""Universal hashing: h(x) = ((ax + b) mod p) mod m"""
def __init__(self, table_size, prime=104729):
self.m = table_size
self.p = prime
self.a = random.randint(1, prime - 1)
self.b = random.randint(0, prime - 1)
def hash(self, key):
return ((self.a * key + self.b) % self.p) % self.m
# For any two distinct keys, collision probability ≤ 1/m
h = UniversalHashFamily(100)
print(h.hash(42)) # Random but deterministic for this instance
print(h.hash(43)) # Different hash with high probabilitySkip Lists — Randomized Data Structure
Skip lists use random coin flips to build a balanced search structure without explicit rebalancing:
| Level 3 | head ---------> 6 ------------------> None |
| Level 2 | head ----> 3 -> 6 ---------> 9 -----> None |
| Level 1 | head -> 1 -> 3 -> 6 -> 7 -> 9 -> 12 -> None |
Each element is promoted to higher levels with probability 1/2. This gives O(log n) expected search time with a much simpler implementation than balanced BSTs.
When to Use Randomized Algorithms
Use randomized algorithms when:
- Deterministic algorithms have bad worst cases triggered by adversarial inputs
- The problem has a simple randomized solution but complex deterministic one
- You need a practical implementation more than a theoretical guarantee
- Approximate answers are acceptable (Monte Carlo estimation)
- You are dealing with competitive adversaries (cryptography, game theory)
Avoid when:
- Correctness must be guaranteed with 100% certainty (safety-critical systems)
- Reproducibility is required (use seeded PRNG if you must)
- The overhead of random number generation exceeds the benefit
Real-World Applications
- Cryptography — key generation, primality testing, random nonces
- Machine learning — stochastic gradient descent, random forests, dropout
- Databases — random sampling for query optimization and statistics
- Networking — randomized load balancing, backoff algorithms
- Streaming algorithms — Count-Min Sketch, HyperLogLog for approximate counting
- Computational biology — MCMC for phylogenetic tree inference
Interview Questions
Q1: What is the difference between Las Vegas and Monte Carlo algorithms? A: Las Vegas always gives the correct answer but has random running time. Monte Carlo has fixed running time but may give incorrect answers with bounded probability.
Q2: Why is randomized quicksort better than deterministic quicksort? A: Random pivot selection makes the expected running time O(n log n) for ALL inputs, including already-sorted arrays. Deterministic pivot strategies (like always choosing the first element) degrade to O(n²) on sorted inputs.
Q3: How do you reduce error probability in Monte Carlo algorithms? A: Run the algorithm multiple times independently. If error probability per run is p, running k times and taking the majority answer gives error probability that decreases exponentially with k.
Q4: Give an example of a problem easier to solve with randomization. A: Finding the median. Deterministic median-finding (median of medians) is O(n) but has a large constant. Randomized QuickSelect is also expected O(n) but is much faster in practice due to simpler operations.
Q5: Is random number generation truly random in computers? A: No — computers use pseudorandom number generators (PRNGs) that produce deterministic sequences from a seed. For algorithms, PRNGs are sufficient. For cryptography, hardware random number generators or cryptographically secure PRNGs are needed.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Randomized Algorithms - Probabilistic Computing.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, randomized
Related Data Structures & Algorithms Topics