Algorithms · Cluster
Randomized Algorithms
Probability in algorithm design and analysis.
- 01 Unbiased Random Integers from a Finite Random Source How taking a remainder from a random word introduces measurable bias, and how rejection sampling and multiply-and-reject produce exact uniformity at a bounded cost.
- 02 Uniform Random Permutations and the Fisher-Yates Shuffle Why swapping each element with a random position from the whole array produces biased permutations, and how the inside-out variant shuffles a stream without knowing its length.
- 03 Randomized Quicksort and the Expected Comparison Count How choosing the pivot uniformly at random makes the 2n ln n comparison bound hold for every input, and where the expectation stops describing a single run.
- 04 Randomized Recurrences and the Indicator Variable Method How expected cost is derived from indicator variables and conditional expectations, and why a recurrence over the random split point needs a different treatment from a deterministic one.
- 05 The Probabilistic Method: Proving That a Good Object Exists How a random construction with nonzero success probability establishes existence without producing an example, and how the Lovász local lemma weakens the independence the argument needs.
- 06 Universal Hashing and Guarantees That Hold for Every Input How choosing a hash function at random from a pairwise-independent family removes the adversary s advantage, and what a family costs to evaluate and to build.
- 07 Randomized Incremental Construction and Backward Analysis How building a structure by inserting elements in random order turns a quadratic insertion cost into an expected linear one, and why the analysis runs the process backwards.
- 08 The Probabilistic Method in Derandomized Form: Conditional Expectations and Small-Bias Spaces How to remove randomness from an algorithm without losing its guarantee, using conditional expectations, pairwise-independent sample spaces, and epsilon-biased distributions.
- 09 Concentration Inequalities for Algorithm Analysis: Chernoff, Azuma, and Their Assumptions How to turn an expected cost into a probability of exceeding a threshold, which inequality applies to which dependency structure, and what each one silently assumes.
- 10 Randomized Rounding of Linear Programs into Integer Solutions How solving a linear relaxation and rounding each variable by its own probability produces integer solutions whose expected cost is within the relaxation bound, and where the argument needs repair.