Randomized quicksort picks a pivot uniformly at random. Its expected number of comparisons on any input of size n is O(n log n). What probability technique most directly yields this result?
AUnion bound over all possible pivot sequences
BLinearity of expectation — define indicator variables for each pair of elements being compared, then sum their expectations
CMarkov's inequality applied to the total comparison count
DChernoff bounds on the depth of the recursion tree
For each pair (i, j) of elements in sorted order, define X_ij = 1 if element i is ever compared to element j. The total comparisons = sum of all X_ij. By linearity of expectation, E[total] = sum of E[X_ij] = sum of Pr[i compared to j]. Two elements are compared exactly when one of them is the first pivot chosen from the range [i..j], giving Pr = 2/(j-i+1). Summing this over all pairs yields O(n log n) via the harmonic series. The beauty is that linearity of expectation requires no independence — the indicator variables can be arbitrarily correlated.
Question 2 True / False
A randomized algorithm always produces the correct answer but its running time is a random variable. This describes a Las Vegas algorithm.
TTrue
FFalse
Answer: True
Las Vegas algorithms guarantee correctness but have random running time. Randomized quicksort is the canonical example: it always sorts correctly, but the number of comparisons depends on the random pivot choices. The complementary class — Monte Carlo algorithms — have deterministic running time but may produce incorrect results with bounded probability. This Las Vegas / Monte Carlo distinction is fundamental to the classification of randomized algorithms.
Question 3 True / False
Every Las Vegas algorithm can be converted to a Monte Carlo algorithm with the same expected resource usage.
TTrue
FFalse
Answer: True
Run the Las Vegas algorithm for a fixed time budget (e.g., twice its expected running time). If it finishes, output the (guaranteed correct) result. If not, output an arbitrary answer or 'fail.' By Markov's inequality, the probability of not finishing within 2E[T] time is at most 1/2. This gives a Monte Carlo algorithm with deterministic time bound 2E[T] and error probability at most 1/2. The reverse conversion — Monte Carlo to Las Vegas — is not always possible without additional structure (you need a way to verify correctness).
Question 4 Short Answer
Karger's randomized min-cut algorithm contracts a randomly chosen edge at each step until two vertices remain. Why does repeating the algorithm O(n^2 log n) times and taking the minimum cut found yield the true minimum cut with high probability?
Think about your answer, then reveal below.
Model answer: A single run of Karger's algorithm preserves a specific minimum cut with probability at least 2/n(n-1) = Omega(1/n^2), because at each contraction step the probability of not cutting a min-cut edge is at least (n-i-2)/(n-i), and the product telescopes to 2/n(n-1). The probability that a single run FAILS to find a specific min-cut is therefore at most 1 - 2/n(n-1). Running O(n^2 log n) independent trials, the probability that ALL trials miss the min-cut is at most (1 - 2/n(n-1))^(cn^2 ln n) <= e^(-2c ln n) = n^(-2c), which is polynomially small. Taking the minimum over all trials gives the true min-cut with high probability.
This is a foundational example of probability amplification: a weak success probability (1/n^2) becomes overwhelming certainty through independent repetition. The key insight is that even a crude per-trial success probability, when amplified by O(n^2 log n) repetitions, drives the failure probability below any desired polynomial threshold.