Invariant
A fact that stays true at every step of an algorithm. The right invariant is the proof of correctness: establish it at the start, show each step preserves it, and read the result off at termination. Most classic entries — insertion sort, binary search, quicksort — are organized around theirs.
Guarantee
The atlas's generalization of "invariant" for randomized and approximate algorithms: instead of a fact that's always exactly true, a probabilistic or approximation bound — an unbiased estimate, a one-sided error, a "within (1±ε) with high probability." Shown empirically by running many trials. See the modern wing: Morris counter, Count–Min, Johnson–Lindenstrauss.
Amortized cost
The average cost per operation over a worst-case sequence, even if individual operations occasionally cost more. KMP's text pointer never backs up, so its n characters cost O(n) total even though a single step may do several failure jumps.
In place / stable
In place = uses only O(1) extra memory beyond the input. Stable = equal keys keep their original relative order. Merge sort is stable but not in place; quicksort is in place but not stable.
Divide and conquer
Split a problem into smaller independent subproblems, solve each, and combine. Merge sort (the combine is the merge) and quicksort (the divide is the partition) are the archetypes.
Dynamic programming
Solve a problem by building up answers to overlapping subproblems and reusing them — turning exponential recursion into a polynomial table. Requires optimal substructure (the best whole is built from best parts). See edit distance.
Greedy + exchange argument
A greedy algorithm makes the locally-best choice at each step; an exchange argument proves it's globally optimal by showing any other solution can be transformed into the greedy one without getting worse. Huffman coding is the classic example.
Admissible heuristic
In A*, an estimate of the remaining cost that never over-estimates. Admissibility is exactly the condition that keeps A* optimal while letting it explore far fewer states than Dijkstra.
Entropy
The information content of a distribution, H = Σ pᵢ log₂(1/pᵢ) bits. No prefix code can use fewer than H bits per symbol on average; Huffman comes within one bit of it.
Unbiased estimator / concentration
An estimator is unbiased if its expected value equals the true quantity (the Morris counter's E[2^X−1] = n). Concentration is how tightly it clusters around that mean — usually improving like 1/√(number of repetitions), which is why sketches average many independent estimates.
Prefix-free code
A set of binary codewords where none is a prefix of another, so a concatenated stream decodes unambiguously without separators. The output of Huffman coding.
Locality-sensitive / min-wise independent
A hash family is locality-sensitive if similar inputs collide more often than dissimilar ones — the basis of LSH. Min-wise independence is the stronger property MinHash needs: every element is equally likely to hash to the minimum (a cheap linear hash isn't, and biases the estimate).
Laplacian / Fiedler vector / algebraic connectivity
The graph Laplacian is L = D − A (degrees minus adjacency). Its second-smallest eigenvalue λ₂ is the algebraic connectivity (how hard the graph is to disconnect), and the corresponding eigenvector — the Fiedler vector — gives each node a coordinate that draws the graph and cuts it.
Conductance / Cheeger's inequality
Conductance measures how bottlenecked a cut is — edges crossing it relative to the smaller side's volume. Cheeger's inequality bounds the best possible conductance by the spectrum: λ₂/2 ≤ φ ≤ √(2λ₂), which makes the spectral cut provably near-optimal.
Stationary distribution
For a random walk on a graph, the long-run fraction of time spent at each node — a probability vector unchanged by one more step (P·r = r), i.e. the dominant eigenvector of the transition matrix. PageRank is exactly this for the web's link graph.
Power iteration
Find a matrix's dominant eigenvector by repeatedly multiplying a vector by the matrix and renormalizing; it converges geometrically. The engine behind spectral layout and PageRank.