Foundations

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.

Microstate probabilities quantify statistical entropy.

A density operator represents quantum statistical states.

A joint pure state can fail to factor into subsystem states.

Sample the joint input model to approximate the output distribution.

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.

A DFA consists of finite states Q, finite alphabet Σ, total transition δ:Q×Σ→Q, start q₀ and accepting states F.

Regular expressions built from letters, the empty word and empty language using union, concatenation and star describe exactly the DFA/NFA-recognizable languages.

A context-free grammar has finite variables, terminal alphabet, rules A→w with one variable on the left, and a start variable.

A nondeterministic pushdown automaton augments finite control with one unbounded last-in-first-out stack.

A recognizer accepts every member of its language but may run forever on a nonmember.

Every nontrivial property of the language recognized by a Turing machine is undecidable from its machine description.

For finite X,Y, H(X|Y)=Σy p(y)H(X|Y=y) and H(X,Y)=H(Y)+H(X|Y).

For finite distributions p,q, D(p‖q)=Σx p(x)log₂[p(x)/q(x)]≥0, with equality exactly when p=q.

If finite X→Y→Z form a Markov chain, meaning Z is conditionally independent of X given Y, then I(X;Z)≤I(X;Y).

A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding.

Repeatedly merge the two least-probable source symbols or accumulated nodes, then label the two branches 0 and 1; root-to-leaf labels are codewords.

For iid finite-alphabet X₁,…,Xₙ, −n⁻¹log₂p(X₁,…,Xₙ) converges in probability to H(X₁).

The entropy rate is limₙ H(X₁,…,Xₙ)/n when the limit exists.

For a real density f with defined integral, h(X)=−∫f(x)log₂f(x)dx.