Foundations

Graphs represent pairwise connections; trees impose acyclicity.

An interface defines operations; an implementation determines costs.

An invariant establishes correctness only with its proof obligations.

Distinct-key comparisons need enough branches to distinguish orders.

Graph searches visit reachable vertices using different orders.

Edge weights determine which shortest-path method applies.

Finite instructions can act on an unbounded writable tape.

A relation is a set of tuples from declared domains.

A hash table maps keys to buckets and stores colliding keys in a chain.

An AVL binary search tree maintains subtree heights differing by at most one at every node.

A binary max heap stores a complete binary tree in an array with every parent key at least its children's keys.

Build a max heap, exchange its root with the last active element, shrink the active heap and restore heap order; repeat.

Dynamic programming states subproblems and recurrences, checks an acyclic dependency order and base cases, and evaluates each needed subproblem once by memoization or bottom-up order.

For positive integers a₁,…,aₙ and target T≥0, D(i,t)=D(i−1,t) or [t≥aᵢ and D(i−1,t−aᵢ)], with D(0,0)=true and other initial states false.

Initialize d(s)=0 and other distances to infinity, then relax every directed edge for |V|−1 rounds.

On a sorted random-access array, compare the target with the middle key and discard the half that cannot contain it; repeat until a matching key is found or the remaining interval is empty.

Split an array into two nearly equal halves, sort each recursively, and merge sorted halves by repeatedly choosing the next ordered key.

To maximize the number of compatible intervals, repeatedly take the available interval finishing earliest and discard overlapping intervals.

In a connected undirected weighted graph, if a set of chosen edges lies within some minimum spanning tree and a cut crosses none of them, a lightest edge crossing that cut can be added while preserving this invariant.

Process edges in nondecreasing weight order, adding an edge exactly when its endpoints belong to different current components, then merge those components.

Append to an array with spare capacity; when full, allocate twice the capacity and copy existing entries.

A directed network flow respects nonnegative capacities and conserves flow at vertices other than source s and sink t.

Starting with zero flow, find a shortest residual s–t path by breadth-first search and augment by its minimum residual capacity, updating forward and reverse capacities.

For N complex coefficients aⱼ define yₖ=Σ_(j=0)^(N−1)aⱼωᴶᴷ, with ω=e²πⁱ⁄ᴺ.

For N a power of two, split polynomial coefficients into even and odd indices, recursively transform each half, and combine values using p(z)=p_even(z²)+zp_odd(z²).

For n records with integer keys 0≤k<U, append records to U insertion-ordered buckets by key, then concatenate buckets in increasing key order.

Represent nonnegative integer keys with d base-B digits and stably sort each digit from least to most significant.

A finite directed graph admits an order placing u before v for every edge u→v exactly when it is acyclic.

In a finite integer-weighted DAG set d(s)=0 and other d(v)=∞, process vertices in topological order, and relax each outgoing u→v by d(v)←min(d(v),d(u)+w(u,v)).

For string suffixes A[i:],B[j:], let L(i,j) be their longest common subsequence length.