Glossary
Every key term, with the chapter that first defines it. Terms are listed alphabetically.
$k$-colorable — describing a graph for which a proper coloring using $k$ colors exists.
3-SAT — SAT restricted to formulas in conjunctive normal form (an AND of clauses, each an OR of literals) with exactly three literals per clause; still NP-complete, and the standard source problem for reductions. (Contrast 2-SAT, which is in P.)
A
abelian — a property of a group whose operation is also commutative: $a\ast b = b\ast a$ for all $a,b$. (Named after Niels Henrik Abel; commutativity is not one of the four group axioms.)
adjacency list — A representation of a graph that stores, for each vertex $v$, a list of the vertices adjacent to $v$ (typically a dictionary mapping each vertex to its neighbor list). It uses $\Theta(n+m)$ space and is the default representation for sparse, traversal-heavy graphs.
adjacency matrix — For a graph $G=(V,E)$ with vertices labeled $0,\dots,n-1$, the $n\times n$ matrix $A$ in which $A[i][j]=1$ when $\{i,j\}\in E$ (or $(i,j)\in E$ for a directed graph) and $A[i][j]=0$ otherwise. It is symmetric for an undirected graph, uses $\Theta(n^2)$ space, and answers "is $\{i,j\}$ an edge?" in $O(1)$.
aleph-null (Ch. 10) — Written $\aleph_0$; the cardinality of any countably infinite set, and the smallest infinite cardinal. $\lvert\mathbb{N}\rvert = \lvert\mathbb{Z}\rvert = \lvert\mathbb{Q}\rvert = \aleph_0$.
algorithm (Ch. 14) — A finite sequence of precise, unambiguous instructions for solving a problem or computing a function, satisfying definiteness (each step exactly specified), finiteness (halts on every valid input), effectiveness (each step is basic and exact), and a specified input/output relation. Distinct from any single implementation (the program in a particular language).
alphabet (Ch. 35) — A finite, non-empty set $\Sigma$ of symbols. A string (or word) over $\Sigma$ is a finite sequence of its symbols; $\varepsilon$ denotes the empty string (length 0), and $\Sigma^{*}$ denotes the set of all strings over $\Sigma$ (including $\varepsilon$), which is infinite.
antichain — A subset of a poset in which every two distinct elements are incomparable (a set of mutually unrelated elements).
antisymmetric (Ch. 12) — A relation $R$ on $A$ is antisymmetric if $(a,b) \in R$ and $(b,a) \in R$ together force $a = b$. Equivalently, distinct elements are never related in both directions. (Not the negation of "symmetric.")
argument (Ch. 3) — A finite list of statements called premises, followed by a single statement called the conclusion; the argument asserts that the premises support the conclusion (written with the $\therefore$ symbol).
arithmetic series (Ch. 11) — The sum of consecutive terms of an arithmetic sequence (one with a constant common difference $d$): $\sum_{i=0}^{n-1}(a+id) = n\cdot\frac{\text{first}+\text{last}}{2} = \frac{n(2a+(n-1)d)}{2}$.
asymptotic (Ch. 14) — Describing the behavior of a function as its argument grows without bound ($n \to \infty$); asymptotic analysis deliberately ignores constant factors and behavior on small inputs, keeping only the growth's shape.
augmenting path (Ch. 34) — A directed path from the source $s$ to the sink $t$ in the residual network $G_f$, using forward edges (with spare capacity) and/or back edges (which cancel existing flow), each with positive residual capacity. Its bottleneck is the minimum residual capacity along it; pushing the bottleneck amount increases the flow value by exactly that amount.
average case (Ch. 14) — For inputs of size $n$, the expected running time over a stated probability distribution on size-$n$ inputs; its value depends entirely on the assumed distribution.
B
base case (Ch. 6) — The starting instance of an induction proof, proved directly (often $n=0$ or $n=1$, but in general wherever the claim begins).
base rate (Ch. 21) — The unconditional (prior) probability of an event in the population, e.g. $P(D)$ for a disease, before any test or evidence is considered. The base-rate fallacy is the error of neglecting this prior — typically treating the posterior $P(D \mid T)$ as if it equaled the test's likelihood $P(T \mid D)$.
Bayes' theorem (Ch. 21) — The rule for reversing a conditional probability: $P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}$ for $P(B) > 0$. Expanding the denominator by the law of total probability gives $P(A \mid B) = \frac{P(B\mid A)P(A)}{P(B\mid A)P(A) + P(B\mid\overline{A}) P(\overline{A})}$. It maps a prior belief plus evidence to a posterior belief.
Bellman-Ford (Ch. 29) — A single-source shortest-path algorithm that tolerates negative edge weights. It relaxes every edge of the graph $|V| - 1$ times; one additional relaxation pass that still improves some distance certifies a reachable negative cycle (shortest paths then undefined). Runs in $O(VE)$.
best case (Ch. 14) — For inputs of size $n$, the minimum running time over all such inputs, $\min_{|x|=n} T(x)$ (usually the least informative measure).
Big-O (Ch. 14) — An asymptotic upper bound. $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$ ("$f$ grows no faster than $g$").
Big-Omega (Ch. 14) — An asymptotic lower bound. $f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $f(n) \ge c\,g(n)$ for all $n \ge n_0$ ("$f$ grows at least as fast as $g$"); the natural tool for stating lower bounds on problems.
Big-Theta (Ch. 14) — A tight asymptotic bound. $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ — equivalently, $c_1 g(n) \le f(n) \le c_2 g(n)$ for some constants and all large $n$ ("$f$ grows exactly like $g$ up to constant factors"). An equivalence relation on growth rates.
bijection (Ch. 9) — A bijective function (one-to-one correspondence): one that is both injective and surjective, pairing the domain and codomain perfectly. A function is invertible iff it is a bijection.
binary search tree (Ch. 31) — A binary tree satisfying the BST property: at every node, all keys in the left subtree are less than the node's key and all keys in the right subtree are greater. An inorder traversal of a BST visits its keys in sorted order; search, insertion, and deletion each cost $O(h)$ for tree height $h$.
binary tree (Ch. 31) — A rooted tree in which every vertex has at most two children, each distinguished as the left or right child. It is full if every internal node has exactly two children, and complete if every level is filled except possibly the last, which is filled left to right.
binomial coefficient (Ch. 16) — The number $\binom{n}{r}$ ("$n$ choose $r$") of $r$-element subsets of an $n$-element set, equal to $\frac{n!}{r!\,(n-r)!}$ for $0 \le r \le n$ (and $0$ otherwise). It is the coefficient of $x^{n-r}y^{r}$ in the expansion of $(x+y)^n$.
binomial theorem (Ch. 16) — The identity $(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}$ for any $x, y$ and integer $n \ge 0$; the coefficient of $x^{n-k}y^{k}$ counts the ways to choose which $k$ of the $n$ factors contribute a $y$.
bipartite graph (Ch. 27) — A graph whose vertex set partitions into two disjoint sets $X$ and $Y$ (the bipartition) such that every edge joins a vertex in $X$ to one in $Y$ — no edge lies within a part. A graph is bipartite if and only if it contains no cycle of odd length.
bipartite matching (Ch. 34) — A matching (a set of edges no two of which share a vertex) in a bipartite graph with parts $X$ and $Y$. A maximum bipartite matching has the most edges; it is computed by reducing to max flow (source $\to X \to Y \to$ sink, all unit capacities), where the maximum integer flow value equals the maximum matching size.
block length (Ch. 38) — The fixed length $n$ of every codeword in a block code. (Supporting term; not in the §1 ledger.)
Boolean algebra — A bounded, distributive, complemented lattice: a set with operations join ($\vee$, OR), meet ($\wedge$, AND), and complement ($\overline{\phantom{a}}$, NOT), and elements $0$ and $1$, satisfying the identity, domination, idempotent, commutative, associative, distributive, De Morgan, and complement laws. The two-element Boolean algebra $\{0,1\}$ models propositional logic and digital logic gates.
bound variable (Ch. 2) — An occurrence of a variable that falls within the scope of a quantifier over that variable; it is local to the quantifier, freely renameable, and not substitutable from outside (the analogue of a loop variable). A formula whose every variable is bound is a proposition.
breadth-first search (BFS) — A graph traversal from a source $s$ that visits vertices in order of increasing distance from $s$ (rings of distance $0, 1, 2, \dots$), using a FIFO queue and marking each vertex visited at the moment it is enqueued. On an unweighted graph it computes shortest-path distances (in edges) from $s$ to every reachable vertex.
Bézout's identity (Ch. 22) — The theorem that for any integers $a, b$ not both zero, there exist integers $x, y$ (the Bézout coefficients) with $ax + by = \gcd(a, b)$; equivalently, $\gcd(a, b)$ is the smallest positive integer expressible as an integer combination of $a$ and $b$. It is the basis of modular inverses.
C
capacity (of an edge) (Ch. 34) — The nonnegative number $c(u,v)$ giving the maximum amount of flow an edge $u\to v$ may carry. An edge with $f(u,v)=c(u,v)$ is saturated.
capstone project — an open-ended, integrative piece of work that combines many ideas from a course into a single deliverable with real design decisions and no single correct answer; distinguished from a homework problem, which tests one idea against a known answer.
cardinality (finite) (Ch. 8) — The number of distinct elements in a finite set $S$, written $\lvert S \rvert$; for example $\lvert \{1,2,3\} \rvert = 3$ and $\lvert \emptyset \rvert = 0$.
cardinality (infinite) (Ch. 10) — The size of a set, extended to infinite sets by matching: $\lvert A\rvert = \lvert B\rvert$ means a bijection $A \to B$ exists, $\lvert A\rvert \le \lvert B\rvert$ means an injection $A \to B$ exists, and $\lvert A\rvert < \lvert B\rvert$ means an injection exists but no bijection. Agrees with the finite count of Chapter 8 when the sets are finite.
Cartesian product (Ch. 8) — The set of all ordered pairs with first coordinate from $A$ and second from $B$, $A \times B = \{(a, b) \mid a \in A, b \in B\}$; its cardinality is $\lvert A \rvert \cdot \lvert B \rvert$.
category theory — the branch of mathematics that studies mathematical structures through the structure-preserving maps (morphisms, drawn as arrows) between them rather than through the internal elements of the structures. A category consists of objects, arrows between objects, an associative rule for composing arrows, and an identity arrow on each object.
ceiling (Ch. 9) — The function $\lceil x \rceil\colon \mathbb{R} \to \mathbb{Z}$ giving the least integer greater than or equal to $x$ (rounds toward $+\infty$).
certificate (witness) — A polynomial-size string of evidence that, supplied alongside a yes-instance of an NP problem, lets a verifier confirm the answer in polynomial time (e.g., a satisfying assignment for SAT, a tour for TSP, a vertex set for CLIQUE).
chain — A subset of a poset in which every two elements are comparable (a totally ordered piece of the poset).
channel capacity — the maximum rate, in bits per channel use, at which information can be sent over a noisy channel with error probability approaching zero (the maximum mutual information over input distributions). For a binary symmetric channel that flips each bit with probability $p$, $C = 1 - H(p)$ where $H(p)$ is the binary entropy function. Shannon's noisy-channel theorem proves reliable communication is possible below $C$ and impossible above it.
characteristic equation (Ch. 18) — The polynomial equation obtained from a linear homogeneous recurrence with constant coefficients by substituting the geometric guess $a_n = r^n$ and dividing out the lowest power: for $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ it is $r^k - c_1 r^{k-1} - \cdots - c_k = 0$. Its roots (the characteristic roots), with their multiplicities, build the general solution: each root $r$ of multiplicity $m$ contributes $r^n, n r^n, \dots, n^{m-1} r^n$.
checksum (Ch. 26) — A small, fixed-size value computed from a block of data and transmitted or stored alongside it, so the receiver can recompute it and compare; a mismatch reveals that the data changed. A checksum detects errors but, on its own, neither locates nor corrects them.
Chinese Remainder Theorem (Ch. 23) — The theorem that a system of congruences $x \equiv a_i \pmod{n_i}$ with pairwise-coprime moduli $n_i$ has a solution that is unique modulo $N = \prod_i n_i$; constructively, $x = \sum_i a_i N_i M_i \bmod N$ where $N_i = N/n_i$ and $M_i = N_i^{-1} \bmod n_i$. Equivalently, it establishes the isomorphism $\mathbb{Z}N \cong \mathbb{Z} \times \cdots \times \mathbb{Z}_{n_k}$.
Chomsky hierarchy (Ch. 35) — The nested classification of formal languages by grammar restriction, each level matched to a recognizing machine and an amount of memory: Type 3 regular (finite automaton), Type 2 context-free (pushdown automaton = finite automaton + a stack), Type 1 context-sensitive (linear-bounded automaton), and Type 0 recursively enumerable (Turing machine). The containments Regular $\subsetneq$ Context-free $\subsetneq$ Context-sensitive $\subsetneq$ Recursively enumerable are all strict.
Chromatic number ($\chi(G)$) — the smallest number of colors $k$ for which a graph $G$ has a proper $k$-coloring.
Church–Turing thesis — The claim (not a theorem) that every function computable by any effective/mechanical procedure is computable by a Turing machine; equivalently, "computable by an algorithm" and "Turing-computable" denote the same functions. Supported by the convergence of all proposed models of computation (Turing machines, lambda calculus, general recursive functions, etc.) but not provable, since it equates a precise notion with an informal one.
cipher — A pair of algorithms (one to encrypt, one to decrypt) parameterized by a secret key, such that decrypting an encrypted message with the matching key recovers the original. The encryption input is the plaintext; its output is the ciphertext.
Clique number ($\omega(G)$) — the number of vertices in the largest clique (set of pairwise-adjacent vertices) in a graph $G$; a lower bound on the chromatic number, $\chi(G) \ge \omega(G)$.
code (Ch. 38) — A chosen subset $C$ of all strings of a fixed length $n$ over an alphabet (binary unless stated); its members are the legal codewords, and the strings outside $C$ are illegal patterns that make error detection and correction possible. A code with $M$ codewords of length $n$ is an $(n,M)$ code; a linear one of dimension $k$ is an $[n,k]$ code.
code rate (Ch. 38) — For a code with $M=2^k$ codewords of block length $n$, the rate $R=k/n=(\log_2 M)/n$ is the fraction of each transmitted block that is genuine message (the rest is redundancy). $R=1$ means no protection; lower rates buy more error protection at the cost of throughput.
codeword (Ch. 38) — A string belonging to a code $C$ (a "legal" message). Encoding maps each message to a distinct codeword; decoding maps a received (possibly corrupted) string back to a codeword/message.
coefficient extraction — The operation $[x^n]A(x)$, meaning "the coefficient of $x^n$ in the (formal) power series $A(x)$"; how a numerical answer is read off a generating function. (Notation introduced in Ch.17.)
collision (Ch. 26) — The event that two distinct keys hash to the same slot: $k_1 \ne k_2$ but $h(k_1) = h(k_2)$. By the pigeonhole principle, collisions are unavoidable whenever $\lvert U\rvert > m$; hash tables must therefore include a collision-resolution policy (chaining or probing).
combination (Ch. 16) — An unordered selection of objects — equivalently, a subset. An $r$-combination of an $n$-element set is an $r$-element subset; the number of them is the binomial coefficient $\binom{n}{r} = \frac{P(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}$.
combinations with repetition — The number of ways to choose $n$ items from $k$ types, with repetition allowed and order irrelevant (i.e., a multiset of size $n$ from $k$ types), equal to $\binom{n+k-1}{n}$; the same count as stars and bars. (Introduced in Ch.17 as the sibling of Ch.16's repetition-free combinations.)
combinatorial optimization — the study of finding an optimal object (one that maximizes or minimizes a value) from a finite set of feasible objects defined by combinatorial constraints, where the set is far too large to enumerate by hand. Minimum spanning tree, maximum flow, maximum matching, and the Traveling Salesman Problem are the canonical examples.
combinatorial proof (Ch. 16) — A proof that two expressions are equal by showing they count the same finite set — either by counting one set in two ways (a double-counting argument) or by exhibiting a bijection between two sets whose sizes are the two expressions. It is rigorous because a finite set has exactly one size.
complement (Ch. 8) — The set of all elements of the universe $U$ not in $A$, written $\overline{A} = {x \in U \mid x \notin A} = U \setminus A$.
complete graph (Ch. 27) — The simple graph $K_n$ on $n$ vertices in which every pair of distinct vertices is joined by an edge. It has $\binom{n}{2} = \frac{n(n-1)}{2}$ edges, and every vertex has degree $n - 1$. ($K_{m,n}$ denotes the complete bipartite graph: parts of sizes $m$ and $n$ with all $mn$ cross-edges.)
complexity class — A set of decision problems all solvable within a shared bound on a computational resource (typically time or memory) on a specified model of computation.
composite (Ch. 22) — An integer $n > 1$ that is not prime; equivalently, $n = ab$ for some integers $a, b$ with $1 < a < n$ and $1 < b < n$. Every composite has a prime divisor at most $\sqrt{n}$.
composition (Ch. 9) — Given $f\colon A \to B$ and $g\colon B \to C$, the function $g \circ f\colon A \to C$ defined by $(g \circ f)(a) = g(f(a))$ ("$g$ after $f$"; apply $f$ first). Associative but not in general commutative.
conclusion (Ch. 3) — The final statement of an argument, claimed to follow from the premises.
conditional probability (Ch. 21) — The probability of an event $A$ given that another event $B$ has occurred, written $P(A \mid B)$ and defined as $P(A \mid B) = \frac{P(A \cap B)}{P(B)}$ when $P(B) > 0$; operationally, it restricts ("shrinks") the sample space to the outcomes in $B$ and renormalizes so the probabilities sum to 1 over that smaller space.
congruence (Ch. 23) — A relation between two integers: $a \equiv b \pmod{n}$ holds when the modulus $n$ divides their difference $a - b$, equivalently when $a$ and $b$ leave the same remainder on division by $n$. Congruence modulo $n$ is an equivalence relation whose classes are the residue classes.
conjecture (Ch. 4) — A statement believed to be true but not yet proved; the mathematical analogue of code that passes all tests but has not been verified for all inputs.
conjunctive normal form (CNF) — A Boolean formula written as a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals (a literal is a variable or its negation). (Defined inline in 37.5 to support 3-SAT; flag for ownership if a later chapter needs it.)
connected (Ch. 27) — A graph is connected if there is a path between every pair of its vertices. A graph that is not connected splits into maximal connected pieces called connected components.
connected component — A maximal set of vertices of an undirected graph that are all mutually reachable; equivalently, an equivalence class of the "reachable from one another" relation. The connected components partition the vertex set, and each can be discovered by a single traversal launched from any of its vertices.
connective (Ch. 1) — A logical operator (e.g. $\neg, \land, \lor, \oplus, \rightarrow, \leftrightarrow$) that combines propositions into a compound proposition whose truth value is determined entirely by the truth values of its parts.
constraint satisfaction problem (CSP) — a problem specified by a set of variables, a domain of allowed values for each, and a set of constraints restricting which value combinations are permitted; a solution is an assignment of a domain value to every variable that satisfies every constraint. (Sudoku is the chapter's worked example; graph coloring and $n$-queens are others.)
contingency (Ch. 1) — A compound proposition that is neither a tautology nor a contradiction — true for some assignments and false for others. (Companion term defined inline; not reserved elsewhere — see continuity note.)
continuum (Ch. 10) — The cardinality of the real numbers $\mathbb{R}$, written $\mathfrak{c}$ or $2^{\aleph_0}$; strictly larger than $\aleph_0$.
contradiction (Ch. 1) — A compound proposition that is false for every assignment (output column all $F$); equivalently, an unsatisfiable proposition. Example: $p \land \neg p$.
contrapositive (Ch. 4) — The conditional $\neg Q \rightarrow \neg P$ obtained from $P \rightarrow Q$ by negating both parts and swapping their order; it is logically equivalent to the original ($P \rightarrow Q \equiv \neg Q \rightarrow \neg P$). A proof by contraposition proves the original by giving a direct proof of its contrapositive. (Distinct from the converse $Q \rightarrow P$, which is not equivalent.)
Cook–Levin theorem — The theorem (Stephen Cook and Leonid Levin, 1971) that SAT is NP-complete: SAT is in NP, and every problem in NP reduces to SAT in polynomial time. The keystone that gives the first NP-complete problem, from which all others follow by reduction.
corollary (Ch. 4) — A true statement that follows quickly (with little or no extra work) from a theorem already proved.
countable (Ch. 10) — A set that is finite or countably infinite; equivalently, a set whose elements can be arranged in a (possibly finite) list with no repeats and no omissions.
countably infinite (Ch. 10) — A set equinumerous with $\mathbb{N}$; equivalently, a set whose elements can be enumerated as an infinite list $s_0, s_1, s_2, \dots$ with every element appearing exactly once.
counterexample (Ch. 2) — A specific element $c$ of the domain for which $P(c)$ is false; exhibiting one counterexample disproves the universal statement $\forall x\, P(x)$ (it is a witness to the negation $\exists x\, \neg P(x)$).
counting principle (Ch. 15) — Any of the basic rules of enumeration (product, sum, inclusion-exclusion, division) used to count the size of a finite set without listing its elements; collectively the axioms from which permutation, combination, and probability formulas are derived.
CRC (cyclic redundancy check) (Ch. 26) — An error-detecting checksum equal to the remainder when the message polynomial, shifted up by $x^r$, is divided modulo 2 by a fixed degree-$r$ generator polynomial $G(x)$ over $\mathbb{Z}_2$. An error $E(x)$ goes undetected iff $G(x) \mid E(x)$; suitable choice of $G$ catches all single-bit errors, all bursts of length $\le r$, and (if $(x+1) \mid G$) all odd error counts.
crossing edge (Ch. 32) — An edge with one endpoint in $S$ and the other in $V \setminus S$ for a given cut $(S, V \setminus S)$.
cryptographic hash (cryptographic hash function) (Ch. 26) — A hash function from arbitrary-length
input to a fixed-length digest that additionally provides preimage resistance (cannot invert a
digest), second-preimage resistance (cannot find a different input matching a given one), and
collision resistance (cannot find any colliding pair). Collisions still exist by pigeonhole; the
defining property is that they are computationally infeasible to find. Used in git, password
storage, and digital signatures.
cut (Ch. 32) — A partition of a graph's vertices into two non-empty sets $(S, V \setminus S)$.
cut property (Ch. 32) — The theorem that, for any cut of a connected weighted graph, a light (minimum-weight) crossing edge belongs to some minimum spanning tree; if it is the unique minimum, it belongs to every MST. The basis for the correctness of Kruskal's and Prim's algorithms.
cycle (Ch. 27) — A closed walk of length at least 3 that starts and ends at the same vertex and otherwise repeats no vertex; a "closed path."
cycle property (Ch. 32) — The theorem that the unique heaviest edge on any cycle of a weighted graph belongs to no minimum spanning tree. The basis for the reverse-delete algorithm.
cyclic group — a group $G$ in which every element is a power of a single element $g$, i.e. $G=\{g^k : k\in\mathbb{Z}\}=\langle g\rangle$. Cyclic groups are the simplest groups and the kind most used in cryptography.
D
De Morgan's laws (Ch. 1) — The two equivalences $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$: a negation distributes over a conjunction/disjunction by flipping the connective. Named for Augustus De Morgan.
decidable — A decision problem (language) is decidable, or recursive, if some Turing machine halts on every input and answers correctly — accepting exactly the "yes" instances and rejecting exactly the "no" instances. Such a machine is a decider. (Contrast recognizable, where the machine may loop forever on "no" instances.)
decision problem — A problem whose answer for every instance is either yes or no; equivalently, the task of deciding membership in a set of instances. (Used throughout complexity theory because yes/no is the simplest, most uniform output.)
degree (Ch. 27) — For a vertex $v$ in a simple graph, $\deg(v)$ is the number of edges incident to $v$, equivalently the number of neighbors $\lvert N(v)\rvert$. In a directed graph a vertex has an in-degree $\deg^-(v)$ and an out-degree $\deg^+(v)$. A degree-0 vertex is isolated; a degree-1 vertex is a leaf.
depth-first search (DFS) — A graph traversal from a source $s$ that explores as deeply as possible along each branch before backtracking, using a stack (typically the recursion call stack). Its characteristic by-product is the order in which vertices finish (post-order), which yields topological orderings and cycle detection.
derangement — A permutation of $n$ objects with no fixed point (no object maps to its own position). The number of derangements is $D_n = n!\sum_{t=0}^{n}\frac{(-1)^t}{t!}$, satisfying $D_n = (n-1)(D_{n-1}+D_{n-2})$, with $D_n/n! \to 1/e$.
derivation (Ch. 3) — A finite numbered sequence of statements ending in the conclusion, in which each line is either a premise or is obtained from earlier lines by a single named inference rule; it certifies that the conclusion is a valid consequence of the premises ($\Gamma \vdash C$).
DFA (deterministic finite automaton) (Ch. 35) — A 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ with a finite set of states $Q$, input alphabet $\Sigma$, a total transition function $\delta\colon Q\times\Sigma\to Q$ (exactly one next state per state-and-symbol), a start state $q_0\in Q$, and accepting states $F\subseteq Q$. It accepts $w$ iff reading $w$ from $q_0$ ends in a state of $F$. DFAs recognize exactly the regular languages.
diagonalization (Ch. 10) — Cantor's technique of constructing, from any proposed list of objects, a new object that differs from the $n$-th listed object in its $n$-th component, hence appears nowhere on the list. Used to prove $\mathbb{R}$ uncountable and (in Ch. 36) the halting problem undecidable.
digital signature — (Introduced here, intro only.) A value, produced with a signer's private key and verifiable by anyone with the matching public key, that proves a message's authorship and integrity. In RSA, the signer computes $s \equiv m^d \pmod n$ and any verifier checks $s^e \equiv m \pmod n$ — RSA run "backwards," using secrecy of $d$ to prove authorship rather than to hide content.
Dijkstra (Ch. 29) — Dijkstra's algorithm: a greedy single-source shortest-path algorithm for graphs with non-negative edge weights. It repeatedly finalizes the unfinalized vertex of smallest tentative distance and relaxes that vertex's outgoing edges, using a priority queue. Runs in $O(E \log V)$ with a binary heap. Correct because, when a vertex is finalized, its tentative distance already equals its true shortest-path distance (a loop invariant; the proof uses non-negativity exactly once).
direct proof (Ch. 4) — A proof of a conditional $P \rightarrow Q$ that assumes $P$ is true and derives $Q$ through a chain of valid steps; for a universally quantified conditional, one first fixes an arbitrary instance.
directed graph (Ch. 27) — A graph $G = (V, E)$ whose edges are ordered pairs $(u, v)$ (called arcs or directed edges), drawn as arrows $u \to v$ from tail $u$ to head $v$. Also called a digraph. (A directed graph is exactly a relation on $V$, Ch. 12, treated as a first-class object.)
disjoint-set forest (Ch. 32) — The standard union-find implementation: each set is a rooted tree
of parent pointers whose root is the set's representative; find follows pointers to the root and
union links one root under another.
divide-and-conquer (Ch. 19) — An algorithm-design paradigm that solves a problem of size $n$ by breaking it into $a \ge 1$ subproblems each of size $n/b$ (for a constant shrink factor $b > 1$), solving each subproblem recursively, and doing $f(n)$ additional work to divide the input and combine the subproblem answers. Its running time satisfies the divide-and-conquer recurrence $T(n) = a\,T(n/b) + f(n)$. Examples: merge sort ($a=2,b=2$), binary search ($a=1,b=2$), Karatsuba multiplication ($a=3,b=2$).
divisibility (Ch. 22) — The relation $a \mid b$ ("$a$ divides $b$"), defined for integers with $a \neq 0$, meaning there exists an integer $k$ such that $b = ak$; equivalently $a$ is a divisor (factor) of $b$ and $b$ is a multiple of $a$. The relation is a true/false statement, not a number, and is transitive and closed under integer linear combinations.
division rule (Ch. 15) — If a listing counts every object exactly $d$ times (a uniform over-count), the number of distinct objects is $N / d$, where $N$ is the size of the listing; equivalently, if a $d$-to-one function maps an $N$-element set onto $T$, then $\lvert T \rvert = N / d$.
domain (Ch. 2) — The collection of values a predicate's variables are allowed to take (also domain of discourse or universe). Every quantified statement is made relative to a domain, and the same predicate can be true over one domain and false over another.
E
edge (Ch. 27) — A connection between two vertices. In an undirected graph an edge is an unordered pair $\{u, v\}$; in a directed graph it is an ordered pair $(u, v)$ called an arc. The edge $\{u,v\}$ joins $u$ and $v$, which are its endpoints.
element (Ch. 8) — An object that belongs to a set; written $x \in A$ ("$x$ is an element of $A$"). Also called a member.
equinumerous (Ch. 10) — Having the same cardinality; two sets $A$ and $B$ are equinumerous, written $\lvert A\rvert = \lvert B\rvert$, exactly when there is a bijection between them.
equivalence class (Ch. 12) — For an equivalence relation $R$ on $A$ and $a \in A$, the set $[a] = \{x \in A \mid (a,x) \in R\}$ of all elements related to $a$. Any member of a class is a representative of it.
equivalence relation (Ch. 12) — A relation that is reflexive, symmetric, and transitive; a generalized equality that declares certain elements interchangeable for some purpose.
error detection / error correction (Ch. 38) — Detection is recognizing that a received word is not a codeword (something broke); correction is additionally recovering the original codeword, typically by decoding to the nearest codeword in Hamming distance. Correction is strictly stronger and needs larger minimum distance. (Distinction sharpened from Ch.26, where checksums provided detection only.)
Euclidean algorithm (Ch. 22) — An $O(\log\min(a,b))$ procedure for computing $\gcd(a, b)$ that repeatedly replaces the pair $(a, b)$ by $(b,\, a \bmod b)$ until the second entry is $0$, using the identity $\gcd(a, b) = \gcd(b,\, a \bmod b)$; the last nonzero remainder is the gcd. Its extended form additionally returns Bézout coefficients $(x, y)$ with $ax + by = \gcd(a, b)$.
Euler circuit — An Euler path that starts and ends at the same vertex (also called an Euler tour). Exists in a connected graph (with at least one edge) if and only if every vertex has even degree. Decidable in $O(V+E)$ time by counting odd-degree vertices.
Euler path — A trail (walk that may repeat vertices but uses each edge at most once) that traverses every edge of a graph exactly once. Exists in a connected graph (with at least one edge) if and only if exactly two vertices have odd degree, in which case it must begin at one odd-degree vertex and end at the other.
Euler's formula — for any connected plane graph with $V$ vertices, $E$ edges, and $F$ faces, $V - E + F = 2$. (Distinct from Euler's theorem in number theory, Ch.23.)
Euler's theorem (Ch. 23) — If $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi$ is Euler's totient. It generalizes Fermat's little theorem (the case $n = p$ prime) and is the result that makes RSA decryption invert encryption.
event (Ch. 20) — A subset $E \subseteq S$ of the sample space; the event "occurs" when the experiment's outcome is an element of $E$. The whole space $S$ is the certain event and $\emptyset$ is the impossible event, and set operations on events ($\cup$, $\cap$, complement) mean "or," "and," "not."
existence proof (Ch. 5) — A proof of a statement of the form "there exists an $x$ such that $P(x)$" ($\exists x\, P(x)$). A constructive existence proof exhibits a specific witness $x$ (or an algorithm to find one) and verifies $P(x)$; a non-constructive existence proof shows that some $x$ must exist without producing one (often by contradiction or by cases).
existential quantifier (Ch. 2) — The symbol $\exists$; the statement $\exists x\, P(x)$ ("there exists $x$ such that $P(x)$") is true exactly when $P(x)$ holds for at least one element of the domain. Over a finite domain it is a disjunction of $P$ over all elements; over the empty domain it is false.
expected value (Ch. 20) — The probability-weighted average of a random variable, $E[X] = \sum_{s \in S} X(s)\,p(s) = \sum_a a\,P(X = a)$; also called the expectation or mean. It is the "balance point" of the distribution and need not be an attainable value of $X$.
exponential time (Ch. 14) — A running time that is $\Omega(c^n)$ for some constant $c > 1$ (including factorial growth, since $n! \ge 2^{n-1}$); considered intractable for all but small inputs, and not rescued by constant-factor hardware improvements.
expression tree (Ch. 31) — A binary tree representing an arithmetic expression: internal nodes are binary operators and leaves are operands. The subtree at an operator node denotes the result of applying that operator to its two child subtrees; postorder traversal evaluates it.
F
Face — one of the connected regions into which a plane graph divides the plane; the single unbounded region is the outer face.
factorial (Ch. 11) — For an integer $n\ge0$, $n! = \prod_{i=1}^{n} i = 1\cdot2\cdots n$, with the convention $0! = 1$ (the empty product); equivalently $0!=1$ and $n! = n\,(n-1)!$ for $n\ge1$. It counts the orderings of $n$ distinct objects and grows faster than every fixed-base exponential.
fallacy (Ch. 3) — An invalid argument form that is commonly mistaken for a valid one (here, a formal fallacy — e.g., affirming the consequent or denying the antecedent).
Fermat's little theorem (Ch. 23) — If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$; equivalently, $a^{p} \equiv a \pmod{p}$ for every integer $a$.
field — a commutative ring with unity in which $1\ne 0$ and every nonzero element has a multiplicative inverse (equivalently, the nonzero elements form an abelian group under multiplication). In a field you can add, subtract, multiply, and divide by any nonzero element. Examples: $\mathbb{Q},\mathbb{R},\mathbb{C}$, and the finite fields $\mathrm{GF}(p)$.
finite field — a field with finitely many elements; also called a Galois field and written $\mathrm{GF}(q)$ or $\mathbb{F}_q$. A finite field of order $q$ exists if and only if $q=p^k$ is a prime power, and is essentially unique for each prime power. $\mathrm{GF}(p)=\mathbb{Z}_p$ for prime $p$; $\mathrm{GF}(p^k)$ for $k>1$ is built from polynomials over $\mathrm{GF}(p)$ modulo an irreducible polynomial, and is not $\mathbb{Z}_{p^k}$.
floor (Ch. 9) — The function $\lfloor x \rfloor\colon \mathbb{R} \to \mathbb{Z}$ giving the greatest integer less than or equal to $x$ (rounds toward $-\infty$, not toward zero).
flow (Ch. 34) — A function $f\colon E\to\mathbb{R}_{\ge 0}$ on a flow network satisfying the capacity constraint ($0\le f(u,v)\le c(u,v)$ on every edge) and the conservation constraint (flow in $=$ flow out at every vertex except $s$ and $t$). Its value $\lvert f\rvert$ is the net flow out of the source, which equals the net flow into the sink.
flow network (Ch. 34) — A directed graph $G=(V,E)$ together with a nonnegative capacity function $c\colon E \to \mathbb{R}_{\ge 0}$ and two distinguished vertices, a source $s$ and a sink $t$ ($s\neq t$). Models a system in which a commodity is pushed from $s$ to $t$, each edge limited by its capacity. Non-edges are taken to have capacity 0.
Ford–Fulkerson (Ford–Fulkerson method) (Ch. 34) — The method for computing a maximum flow: start from the zero flow and, while an augmenting path exists in the residual network, push its bottleneck (adding to forward edges, subtracting from the original flow on back edges); stop when no augmenting path remains. Choosing augmenting paths by BFS (shortest path) gives the Edmonds–Karp algorithm, which runs in $O(VE^2)$ time.
forest (Ch. 31) — An acyclic undirected graph; equivalently, a disjoint union of trees. Each connected component of a forest is a tree, and a single tree is a forest with one component.
Four Color Theorem — every planar graph is 4-colorable; equivalently, the regions of any plane map can be colored with four colors so that bordering regions differ. Proved by Appel and Haken (1976) using computer-assisted case analysis.
free variable (Ch. 2) — An occurrence of a variable not within the scope of any quantifier over it; its value comes from outside and the formula's truth still depends on it (the analogue of an enclosing parameter). A formula with at least one free variable is a predicate.
function (Ch. 9) — A relation $f \subseteq A \times B$ that assigns to every element $a$ of the domain $A$ exactly one element $f(a)$ of the codomain $B$ (totality + single-valuedness); written $f\colon A \to B$.
functor — a structure-preserving map $F$ from one category to another that sends each object $A$ to an object $F(A)$ and each arrow $f\colon A\to B$ to an arrow $F(f)\colon F(A)\to F(B)$, while preserving identities ($F(\mathrm{id}_A)=\mathrm{id}_{F(A)}$) and composition ($F(g\circ f)=F(g)\circ F(f)$). Python's map over list is a functor; the composition law justifies the map-fusion compiler optimization.
fundamental theorem of arithmetic (Ch. 22) — (FTA) The theorem that every integer $n > 1$ factors into primes, $n = p_1^{a_1}\cdots p_k^{a_k}$ with $p_1 < \cdots < p_k$, and this factorization is unique up to order. Existence is proved by strong induction; uniqueness follows from Euclid's Lemma. The "prime fingerprint" of an integer.
G
gcd (Ch. 22) — The greatest common divisor $\gcd(a, b)$ of two integers (not both zero): the largest integer $d$ with $d \mid a$ and $d \mid b$; $\gcd(0,0) = 0$ by convention. Computed without factoring by the Euclidean algorithm. Two integers with $\gcd = 1$ are coprime.
generalized pigeonhole principle — If $n$ objects are placed into $m$ boxes, then at least one box contains at least $\lceil n/m \rceil$ objects. The basic pigeonhole principle is the special case $n > m$.
generating function (ordinary generating function, OGF) — For a sequence $a_0, a_1, a_2, \dots$, the formal power series $A(x) = \sum_{n=0}^{\infty} a_n x^n$. Used to count: build $A(x)$ so $a_n$ answers the size-$n$ problem, then read the coefficient $[x^n]A(x)$. The symbol $x$ is formal (no convergence required); $x^n$ labels the $n$-th term.
generator — an element $g$ of a cyclic group whose powers produce the entire group ($G=\langle g\rangle$). A group may have several generators. (In $\mathrm{GF}(q)^*$ a generator is also called a primitive element; in $\mathbb{Z}_p^*$ it is a primitive root.)
generator matrix (Ch. 38) — A $k\times n$ matrix $G$ over $\mathrm{GF}(2)$ whose rows form a basis of an $[n,k]$ linear code; a message row vector $m$ is encoded as $c=mG$ (arithmetic mod 2). (Supporting term; not in the §1 ledger.)
geometric series (Ch. 11) — The sum of consecutive terms of a geometric sequence (one with a constant common ratio $r$): $\sum_{i=0}^{n-1} a r^i = a\,\frac{r^n-1}{r-1}$ for $r\ne1$. For $\lvert r\rvert<1$ the infinite series converges to $\frac{a}{1-r}$.
graph (Ch. 27) — A pair $G = (V, E)$ where $V$ is a finite non-empty set of vertices and $E$ is a set of edges. In a simple graph (the default in this book), each edge is an unordered pair $\{u, v\}$ of distinct vertices. Models "things and the pairwise connections between them."
greedy algorithm (Ch. 29, informal) — An algorithm that builds a solution by repeatedly making the locally optimal choice (and never reconsidering it), in the hope of reaching a globally optimal solution. Dijkstra is the chapter's example; greedy correctness is not automatic and must be proved by an invariant. (Formalized further via the cut property in Chapter 32.)
Greedy coloring — an algorithm that, given an ordering of the vertices, colors each vertex in turn with the smallest color not already used by any of its previously-colored neighbors; always proper, uses at most $\Delta(G)+1$ colors, but not generally optimal.
group — a set $G$ with a binary operation $\ast$ satisfying four axioms: closure ($a\ast b\in G$), associativity ($(a\ast b)\ast c = a\ast(b\ast c)$), an identity element $e$ ($e\ast a = a\ast e = a$), and inverses (every $a$ has $a^{-1}$ with $a\ast a^{-1}=a^{-1}\ast a=e$). The number of elements $\lvert G\rvert$ is the order of the group.
H
Hall's marriage theorem (Ch. 34) — A bipartite graph with parts $X,Y$ has a matching saturating $X$ if and only if $\lvert N(W)\rvert \ge \lvert W\rvert$ for every subset $W\subseteq X$ (no sub-group of $X$ is collectively compatible with fewer vertices than its own size).
halting problem — The decision problem of determining, given a program $P$ and an input $x$, whether $P$ halts (eventually stops) when run on $x$, rather than running forever. As a language, $\mathrm{HALT} = \{\langle P, x\rangle : P \text{ halts on } x\}$. Proven undecidable by Turing (1936) via a diagonalization-and-contradiction argument. It is recognizable but not decidable.
Hamilton circuit — A Hamilton path that returns to its starting vertex; equivalently, a cycle passing through every vertex exactly once (also called a Hamilton cycle). Deciding existence is NP-hard. Dirac's theorem gives a sufficient (not necessary) condition: in a simple graph with $n\ge 3$ vertices, if every vertex has degree $\ge n/2$, a Hamilton circuit exists.
Hamilton path — A path that visits every vertex of a graph exactly once. (Contrast with an Euler path, which visits every edge exactly once.) No efficient characterization of existence is known.
Hamming code (Ch. 38) — A single-error-correcting linear code whose parity-check positions are the powers of two ($1,2,4,8,\dots$) and whose parity-check matrix has column $j$ equal to the binary representation of $j$, so the syndrome names the error position. The $\mathrm{Hamming}(7,4)$ code carries 4 data bits in a 7-bit codeword with $d_{\min}=3$ (corrects one error); in general $r$ parity bits protect $2^r-1$ bits carrying $2^r-1-r$ data bits. Adding one overall parity bit gives the SECDED ($d_{\min}=4$) code used in ECC memory.
Hamming distance (Ch. 38) — The Hamming distance $d(x,y)$ between two equal-length strings is the number of positions at which they differ; equivalently $d(x,y)=\operatorname{wt}(x\oplus y)$ over $\mathrm{GF}(2)$. It equals the number of bit-flips the channel introduced, and is a metric (nonnegative, symmetric, triangle inequality). (Canonical home per Ch.26's deferral; Ch.26 used it operationally only.)
handshaking lemma (Ch. 27) — For any graph $G = (V, E)$, $\sum_{v \in V} \deg(v) = 2\lvert E\rvert$: the sum of all vertex degrees equals twice the number of edges (proved by double-counting vertex–edge incidences). Corollary: the number of odd-degree vertices is always even.
hash function (Ch. 26) — A deterministic, fast-to-compute function $h\colon U \to {0, 1, \dots, m-1}$ from a large key universe $U$ to a finite set of $m$ table slots (indices). Because $\lvert U\rvert$ typically far exceeds $m$, a hash function cannot be injective. The array of $m$ slots it indexes into is a hash table.
Hasse diagram — The drawing of a finite poset that shows only the covering relation: each element is a point placed above the elements it strictly succeeds, with a line segment from $a$ up to $b$ exactly when $b$ covers $a$ (no element lies strictly between). It uses no self-loops and no arrowheads (direction is "up"); it is the transitive reduction of the order.
heap (Ch. 31) — A complete binary tree satisfying the heap property: every node's key is $\le$ (min- heap) or $\ge$ (max-heap) the keys of its children, so the extreme element sits at the root. Backed by a flat array (children of index $i$ at $2i+1$ and $2i+2$, parent at $\lfloor (i-1)/2 \rfloor$), it implements a priority queue with $O(\log n)$ insert and remove-extreme and $O(1)$ peek.
heuristic — An algorithm that trades the guarantee of an optimal (or even correct) solution for speed and practicality — aiming to be good enough, fast enough. Examples for TSP: nearest-neighbor (greedy, $O(n^2)$, no quality guarantee) and 2-opt (local search that removes two tour edges and reconnects to shorten the tour). A heuristic with a proven worst-case bound on how far from optimal it can land is called an approximation algorithm (e.g., Christofides' algorithm: $\le \tfrac{3}{2}\times$ optimal for metric TSP).
Huffman coding (Ch. 31) — A greedy algorithm that builds an optimal prefix-code tree from symbol frequencies by repeatedly merging the two lowest-frequency trees under a new node whose frequency is their sum. The resulting code minimizes the average codeword length $\sum_s f(s)\, d(s)$ over all prefix codes for the given frequencies.
I
image (Ch. 9) — The image of an element $a$ is its output $f(a)$; the image of a set $S \subseteq A$ is $f(S) = {f(a) \mid a \in S}$. The image of the whole domain is the range of $f$.
inclusion-exclusion (Ch. 15) — A method for counting the size of a union of overlapping finite sets by adding individual sizes and correcting for over-counting: $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ (two sets), and for three sets, the sum of singles minus the sum of pairwise intersections plus the triple intersection (the general $n$-set form is Ch. 17).
inclusion–exclusion principle (general) — For finite sets $A_1, \dots, A_n$, $\bigl\lvert \bigcup_i A_i\bigr\rvert = \sum_i \lvert A_i\rvert - \sum_{i independence (Ch. 21) — Two events $A$ and $B$ are independent when $P(A \cap B) = P(A)\,P(B)$;
equivalently (when the conditioning event has positive probability) $P(A \mid B) = P(A)$ — the occurrence
of one event gives no information about the other. Distinct from mutual exclusivity ($P(A\cap B)=0$).
Events are mutually independent if every sub-collection multiplies, which is strictly stronger than
pairwise independence. inductive hypothesis (Ch. 6) — The assumption, made within the inductive step, that $P(k)$ holds
for a fixed arbitrary $k$; used to derive $P(k+1)$. inductive step (Ch. 6) — The general argument that the truth of $P(k)$ implies the truth of
$P(k+1)$, for an arbitrary $k$ at or above the base case. information theory — the field, founded by Claude Shannon (1948), that quantifies information and establishes the fundamental limits of data compression (source coding) and reliable communication over noisy channels (channel coding). initial condition (Ch. 18) — An explicitly given value of one of the earliest terms of a sequence,
supplied to get a recurrence started. A recurrence of order $k$ (one that reaches back $k$ terms)
requires exactly $k$ initial conditions to determine a unique sequence. injection (Ch. 9) — An injective (one-to-one) function: distinct inputs always give distinct
outputs, i.e. $f(a_1) = f(a_2) \rightarrow a_1 = a_2$. Has no collisions. inorder (Ch. 31) — The traversal that recursively traverses the left subtree, then visits the root,
then the right subtree ($L$, root, $R$). On a binary search tree it yields the keys in sorted order;
produces infix notation for expression trees. integer linear programming (ILP) — a linear program with the added requirement that the variables take integer values. NP-hard in general (it can encode SAT and hard graph problems); the standard modeling language for hard combinatorial optimization in industry. integration test — a test that exercises several components together to confirm they still compose correctly, as opposed to a unit test that checks one component in isolation; in the Toolkit it is intersection (Ch. 8) — The set of elements common to two sets, $A \cap B = {x \mid x \in A \land x
\in B}$. Sets with empty intersection are disjoint. inverse (Ch. 9) — For a bijection $f\colon A \to B$, the unique function $f^{-1}\colon B \to A$
satisfying $f^{-1} \circ f = \operatorname{id}_A$ and $f \circ f^{-1} = \operatorname{id}_B$; it
undoes $f$. Exists iff $f$ is bijective. (Distinct from the preimage of a set, which is defined for
every function.) join — The least upper bound $a \vee b$ of two elements $a, b$ in a poset: an upper bound of both that precedes every upper bound. Unique when it exists. key generation — The procedure that produces a matched (public, private) key pair for a cryptosystem. In RSA it is the prime-choosing / exponent-computing process above; its outputs are the published public key and the secret private key (with $p, q, \phi(n)$ discarded or guarded). Kruskal's algorithm (Ch. 32) — A greedy MST algorithm that processes edges in ascending weight
order and adds each edge whose endpoints lie in different components (using union-find to test),
stopping at $n-1$ edges. Runs in $O(E \log V)$. Kuratowski's theorem — a graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or of $K_{3,3}$. language (Ch. 35) — Any subset $L \subseteq \Sigma^{*}$ of the strings over an alphabet — that is,
a set of strings. The recognition problem for $L$ is, given a string $w$, to decide whether
$w \in L$. A language is regular if some finite automaton (equivalently, some regular expression)
recognizes it. lattice — A poset in which every pair of elements has both a least upper bound (join) and a greatest lower bound (meet). lemma (Ch. 4) — A true statement proved mainly as a stepping stone toward a larger theorem; a
helper result. light edge (Ch. 32) — A minimum-weight crossing edge of a cut (the cheapest edge among all edges
crossing that cut). linear code (Ch. 38) — A code $C\subseteq \mathrm{GF}(2)^n$ that is a linear subspace: it contains the all-zeros word and the XOR of any two codewords is a codeword. An $[n,k]$ linear code has $2^k$ codewords. For a linear code, $d_{\min}$ equals the minimum weight of a nonzero codeword (Theorem 38.4). linear homogeneous recurrence relation with constant coefficients (Ch. 18) — A recurrence of the
form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$ where the $c_i$ are constants with
$c_k \ne 0$: linear (a linear combination of previous terms, each to the first power), homogeneous
(no standalone term depending only on $n$), and of order $k$. Solvable in closed form by the
characteristic-equation method. (A nonzero added term $f(n)$ makes it nonhomogeneous.) linear programming (LP) — optimizing a linear objective function subject to linear inequality constraints over real-valued variables. The feasible region is a polytope, and an optimum (if one exists) occurs at one of its corners (vertices). Solved in practice by the simplex algorithm or interior-point methods. linearity of expectation (Ch. 20) — The fact that $E[aX + bY] = a\,E[X] + b\,E[Y]$ and, for any
$X_1,\dots,X_n$, $E[\sum_i X_i] = \sum_i E[X_i]$ — holding whether or not the variables are independent.
It is the basis of the "write a quantity as a sum of indicators, then add their probabilities"
technique. load factor (Ch. 26) — For a hash table holding $n$ keys in $m$ slots, the ratio $\alpha = n/m$, the
average number of keys per slot. It governs expected lookup cost ($O(1 + \alpha)$ with chaining under
uniform hashing); the generalized pigeonhole principle forces some slot to hold at least
$\lceil\alpha\rceil$ keys. logical equivalence (Ch. 1) — The relation $A \equiv B$ holding when $A$ and $B$ have the same
truth value for every assignment of truth values to their variables (identical truth-table output
columns). Equivalently, $A \equiv B$ iff $A \leftrightarrow B$ is a tautology. loop invariant (Ch. 6) — A condition that is true at a fixed point of a loop on every pass (it holds
at initialization and is preserved by each iteration); used with a termination argument to prove
iterative code correct. LP duality — the pairing of every linear program (the primal) with a second linear program (the dual) in which a maximization becomes a minimization and resources become prices. Weak duality: any feasible dual value bounds any feasible primal value. Strong duality: if the primal has a finite optimum, the dual does too and the two optimal values are equal. Master Theorem (Ch. 19) — A formula that solves the divide-and-conquer recurrence $T(n)=a\,T(n/b)+
f(n)$ by comparing $f(n)$ to the leaf cost $n^{E}$ where $E=\log_b a$ (the critical exponent). Case 1
(leaves dominate): if $f(n)=O(n^{E-\varepsilon})$ then $T(n)=\Theta(n^{E})$. Case 2 (balanced): if
$f(n)=\Theta(n^{E})$ then $T(n)=\Theta(n^{E}\log n)$. Case 3 (root dominates): if $f(n)=
\Omega(n^{E+\varepsilon})$ and the regularity condition $a\,f(n/b)\le c\,f(n)$ holds for some $c<1$,
then $T(n)=\Theta(f(n))$. It does not apply to subtractive recurrences, merely-logarithmic gaps between
$f$ and $n^E$, or unequal subproblem sizes. matching (Ch. 34) — A set $M\subseteq E$ of edges no two of which share a vertex. A vertex in an edge of $M$ is matched; otherwise unmatched. A maximum matching is largest by edge count; a perfect matching of a side covers every vertex on that side. mathematical induction (Ch. 6) — A proof technique establishing that a statement $P(n)$ holds for
all integers $n \ge \text{start}$ by proving a base case $P(\text{start})$ and an inductive step
$P(k) \rightarrow P(k+1)$ for all $k \ge \text{start}$. matrix exponentiation (Ch. 19) — The technique of computing a high power $M^n$ of a matrix by
exponentiation by squaring (repeatedly squaring $M$ and multiplying in the factors selected by the
binary digits of $n$), achieving $O(\log n)$ matrix multiplications instead of $\Theta(n)$. Applied to
the Fibonacci generating matrix $M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ — for which $M^n=
\begin{pmatrix}F_{n+1}&F_n\F_n&F_{n-1}\end{pmatrix}$ — it computes the $n$th Fibonacci number in
$O(\log n)$ time using exact integer arithmetic. max flow (maximum flow) (Ch. 34) — A flow $f$ of the greatest possible value $\lvert f\rvert$ (net amount leaving the source) in a given flow network; equivalently the solution to the maximum-flow problem. By the max-flow min-cut theorem its value equals the minimum cut capacity. max-flow min-cut theorem (Ch. 34) — The theorem that in any flow network the maximum flow value equals the minimum s–t cut capacity (a strong-duality result; Ford–Fulkerson and Elias–Feinstein–Shannon, 1956). meet — The greatest lower bound $a \wedge b$ of two elements $a, b$ in a poset: a lower bound of both that every lower bound precedes. Unique when it exists. min cut (minimum s–t cut) (Ch. 34) — An s–t cut — a partition $(S,T)$ of the vertices with $s\in S$, $t\in T$ — of smallest capacity $c(S,T)=\sum_{u\in S,\,v\in T} c(u,v)$, where only edges crossing from $S$ to $T$ are counted. By the max-flow min-cut theorem its capacity equals the maximum flow value; at a max flow it is constructed as the residual-reachable set of $s$. minimum distance (Ch. 38) — The minimum distance $d_{\min}(C)=\min\{d(x,y):x\ne y\in C\}$ is the smallest Hamming distance between distinct codewords. It is the single design parameter that determines a code's power: a code detects up to $d_{\min}-1$ errors and corrects up to $\lfloor (d_{\min}-1)/2\rfloor$ errors. (Supporting term; not in the §1 ledger.) minimum spanning tree (MST) (Ch. 32) — A spanning tree of a connected weighted graph whose total
edge weight is as small as possible; i.e. a spanning tree $T$ with $w(T) \le w(T')$ for every spanning
tree $T'$. Unique when all edge weights are distinct. modular exponentiation (Ch. 23) — The computation of $b^{e} \bmod n$ without forming the full
integer $b^{e}$; performed efficiently by the square-and-multiply method in $O(\log e)$ modular
multiplications. modular inverse (Ch. 23) — For integers $a$ and $n > 1$, an integer $a^{-1}$ satisfying $a \cdot
a^{-1} \equiv 1 \pmod{n}$. It exists if and only if $\gcd(a, n) = 1$, in which case it is unique modulo
$n$ and equals the Bézout coefficient $s$ from $as + nt = 1$. An element possessing an inverse is
called a unit modulo $n$. modus ponens (Ch. 3) — The inference rule "from $p \rightarrow q$ and $p$, conclude $q$" (affirming
the antecedent). Valid. modus tollens (Ch. 3) — The inference rule "from $p \rightarrow q$ and $\neg q$, conclude $\neg p$"
(denying the consequent). Valid; equivalent to modus ponens on the contrapositive. naive Bayes (Ch. 21) — A classifier that predicts the class maximizing the posterior
$P(c \mid \text{features})$ via Bayes' theorem under the naive assumption that the features are
mutually conditionally independent given the class: $P(f_1,\dots,f_n \mid c) = \prod_i P(f_i \mid c)$.
The predicted class is $\arg\max_c\ P(c)\prod_i P(f_i \mid c)$. nearest-codeword decoding (Ch. 38) — The decoding rule that returns the codeword at smallest Hamming distance from the received word (also called minimum-distance decoding). It corrects all error patterns of weight $\le t$ exactly when $d_{\min}\ge 2t+1$. (Supporting term; not in the §1 ledger.) negative cycle (Ch. 29, supporting) — A cycle whose edge weights sum to a negative value; if
reachable from the source, it drives affected shortest-path distances to $-\infty$ and makes "shortest
path" undefined. (In a currency-exchange graph, an arbitrage opportunity.) nested quantifier (Ch. 2) — A quantifier appearing within the scope of another, as in
$\forall x\, \exists y\, P(x,y)$. With mixed quantifiers, order is meaning: an inner existential may
depend on an outer universal, so $\forall x\,\exists y$ and $\exists y\,\forall x$ generally differ
(the latter implies the former, not conversely). Like quantifiers commute. NFA (nondeterministic finite automaton) (Ch. 35) — A 5-tuple like a DFA except the transition
function returns a set of states, $\delta\colon Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$,
allowing zero, one, or many successors and $\varepsilon$-transitions (state changes that read no input).
It accepts $w$ iff some path from $q_0$ consuming $w$ ends in an accepting state. By the subset
construction, every NFA has an equivalent DFA, so NFAs recognize exactly the regular languages too. noisy channel (Ch. 38) — Any transmission or storage medium that may corrupt some of the bits passing through it. The binary symmetric channel is the idealized model in which each bit is independently flipped with probability $p<1/2$. (Supporting term; not in the §1 ledger.) NP — The complexity class (nondeterministic polynomial time) of decision problems for which a yes-answer can be verified in polynomial time given a polynomial-size certificate; equivalently, problems whose proposed solutions can be checked fast. NP does not mean "non-polynomial." NP-complete — A problem that is both in NP and NP-hard — the hardest problems within NP. If any single NP-complete problem is in P, then $\text{P} = \text{NP}$. NP-hard — A problem $H$ such that every problem in NP reduces to it in polynomial time ($A \le_p H$ for all $A \in \text{NP}$); at least as hard as everything in NP, and need not itself be in NP. (Formal definition; Chapter 30 used the term only as an informal preview.) NP-hard (preview only; formally defined in Ch.37) — Informally, a problem at least as hard as every problem in the class NP: a polynomial-time algorithm for one NP-hard problem would yield one for all of them. The Hamilton circuit problem and the TSP are NP-hard. Introduced here only as a name for "no known efficient algorithm, believed intractable"; the precise definition (via polynomial-time reductions and the class NP) belongs to Chapter 37. ordered pair (Ch. 8) — A pairing $(a, b)$ in which order is significant: $(a, b) = (c, d)$ if and
only if $a = c$ and $b = d$ (contrast the set $\{a, b\}$, where order and repetition are ignored). P — The complexity class of decision problems solvable by an algorithm with worst-case running time $O(n^k)$ for some constant $k$, where $n$ is the input size; the formal class of tractable (efficiently solvable) problems. parity bit (Ch. 26) — A single extra bit appended to a block of bits, chosen to make the total
number of 1-bits even (even parity) or odd (odd parity). It detects any odd number of bit errors
and misses any even number — the simplest possible checksum (one bit of information). parity-check matrix (Ch. 38) — An $(n-k)\times n$ matrix $H$ over $\mathrm{GF}(2)$ whose null space is the code: $c$ is a codeword iff $Hc^{\mathsf T}=\mathbf 0$. It satisfies $GH^{\mathsf T}=\mathbf 0$, and $d_{\min}$ equals the fewest columns of $H$ that are linearly dependent (XOR to zero). partial order — A relation $\preceq$ on a set that is reflexive, antisymmetric, and transitive. It generalizes "less than or equal to," ranking elements while allowing some pairs to be incomparable. partition (Ch. 12) — A collection of non-empty, pairwise-disjoint subsets (blocks/cells) of a set
$A$ whose union is all of $A$. The equivalence classes of an equivalence relation form a partition, and
every partition arises from exactly one equivalence relation. Pascal's triangle (Ch. 16) — The triangular array whose row $n$ lists the binomial coefficients
$\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$; each interior entry is the sum of the two entries
above it (Pascal's rule, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$), and the entries of row $n$
sum to $2^n$. path (Ch. 27) — A walk $v_0, v_1, \dots, v_k$ (consecutive vertices joined by edges) in which no
vertex repeats. Its length is the number of edges $k$. (Contrast a walk, in which vertices may
repeat.) path compression (Ch. 32) — A union-find optimization performed during path weight (length) (Ch. 29, supporting) — For a path $p = v_0, v_1, \dots, v_k$, the sum $w(p) =
\sum_{i=1}^{k} w(v_{i-1}, v_i)$ of its edge weights. "Length" in a weighted graph means total weight, not
edge count. permutation (Ch. 16) — An ordered arrangement of objects. An $r$-permutation of an $n$-element
set is an ordered arrangement of $r$ of the $n$ objects; the number of them is
$P(n,r) = \frac{n!}{(n-r)!} = n(n-1)\cdots(n-r+1)$, with $P(n,n) = n!$. pigeonhole principle — If $n$ objects are placed into $m$ boxes and $n > m$, then at least one box contains at least two objects. Equivalently, a function from a finite set $A$ to a finite set $B$ with $\lvert A\rvert > \lvert B\rvert$ cannot be injective. Planar graph — a graph that can be drawn in the plane with vertices as points and edges as curves meeting only at shared endpoints, so that no two edges cross. Plane graph — a planar graph together with one particular crossing-free drawing of it in the plane. polynomial time (Ch. 14) — A running time that is $O(n^k)$ for some constant $k$; the standard
threshold for a tractable (feasible) algorithm. polynomial-time reduction ($A \le_p B$) — A polynomial-time computable function $f$ mapping instances of problem $A$ to instances of problem $B$ such that $x$ is a yes-instance of $A$ iff $f(x)$ is a yes-instance of $B$; establishes that $B$ is at least as hard as $A$. (Also called a many-one or Karp reduction.) poset — Short for partially ordered set: a set $S$ together with a partial order on it, written $(S, \preceq)$. posterior (Ch. 21) — In a Bayesian update, the probability $P(A \mid B)$ assigned to a hypothesis
$A$ after observing evidence $B$; the output of Bayes' theorem, proportional to likelihood $\times$
prior. postorder (Ch. 31) — The traversal that recursively traverses the left subtree, then the right
subtree, then visits the root ($L$, $R$, root). Produces postfix/Reverse Polish Notation; used to
evaluate an expression tree and to safely free a tree (children before parent). power set (Ch. 8) — The set of all subsets of a set $S$, written $\mathcal{P}(S) = {A \mid A
\subseteq S}$; if $\lvert S \rvert = n$ then $\lvert \mathcal{P}(S) \rvert = 2^n$. predicate (Ch. 2) — A statement containing one or more variables that becomes a proposition
(definitely true or false) once each variable is assigned a specific value from a fixed collection;
equivalently, a boolean-valued function $P(x)$. The number of variables is its arity. preimage (Ch. 9) — The preimage (inverse image) of a set $T \subseteq B$ under $f$ is $f^{-1}(T) =
{a \in A \mid f(a) \in T}$ — the set of inputs landing in $T$. A set, defined for every function;
it does not require $f$ to be invertible. premise (Ch. 3) — A statement given or assumed as an input to an argument. preorder (Ch. 31) — The traversal that visits the root first, then recursively traverses the left
subtree, then the right subtree (root, $L$, $R$). Produces prefix/Polish notation for expression trees;
used to serialize or copy a tree. Prim's algorithm (Ch. 32) — A greedy MST algorithm that grows a single tree from a start vertex,
repeatedly adding the minimum-weight edge that crosses from the tree to a vertex not yet in it (using a
priority queue). Runs in $O(E \log V)$ with a binary heap. prime (Ch. 22) — An integer $p > 1$ whose only positive divisors are $1$ and $p$ itself; the
multiplicative "atoms" of the integers. By convention $1$ is not prime. prior (Ch. 21) — In a Bayesian update, the probability $P(A)$ assigned to a hypothesis $A$ before
observing the evidence; the starting belief that Bayes' theorem revises. priority queue (Ch. 29) — An abstract data type storing elements each with an associated priority
(key) and supporting probabilistic method (Ch. 20) — A proof technique (due to Erdős) establishing that an object with a
property $Q$ exists by choosing an object at random and showing $P(\text{the random object has } Q) > 0$;
since a probability of $0$ would be forced if no such object existed, positive probability proves
existence. A proof by contradiction that never constructs the object. product rule (Ch. 15) — If a procedure consists of $k$ steps where step $i$ can be performed in
$n_i$ ways regardless of how earlier steps were performed, the whole procedure can be performed in
$n_1 \times n_2 \times \cdots \times n_k$ ways; equivalently $\lvert A_1 \times \cdots \times A_k \rvert
= \lvert A_1 \rvert \cdots \lvert A_k \rvert$. proof by cases (Ch. 5) — A proof technique that splits the possibilities into a finite, exhaustive
list of cases, proves the claim in each case, and concludes it holds in all. Correctness requires both
proving every case and proving the cases cover every possibility (they may overlap but may not leave a
gap). proof by contradiction (Ch. 5) — A proof technique that establishes a statement $P$ by assuming its
negation $\neg P$ and deriving a contradiction (a statement of the form $q \land \neg q$, which is always
false); since $\neg P$ leads to absurdity, $P$ must be true. Also called reductio ad absurdum. The
contradiction may be internal (against the proof's own assumptions) or external (against a known fact). Proper coloring — an assignment of colors to the vertices of a graph, $c\colon V \to \{1,\dots,k\}$, such that every edge has endpoints of different colors ($c(u) \neq c(v)$ for all $\{u,v\} \in E$). proposition (Ch. 1) — A declarative statement that is either true or false, but not both.
Questions, commands, and statements with a free variable (e.g. "$x>3$") are not propositions. propositional variable (Ch. 1) — A symbol (typically $p, q, r, s$) standing for a proposition;
it holds one of the two truth values. (Defined inline; not reserved elsewhere — see continuity note.) public-key cryptography — (Also asymmetric cryptography.) A scheme giving each participant a pair of keys: a public key, published openly and used by anyone to encrypt to that participant, and a private key, kept secret and used only by that participant to decrypt. The keys are mathematically linked, but recovering the private key from the public key is computationally infeasible. Eliminates the need to pre-share a secret. pumping lemma (Ch. 35) — A necessary condition for regularity: if $L$ is regular, there is a
pumping length $p$ such that every $s\in L$ with $\lvert s\rvert\ge p$ can be written $s=xyz$ with
$\lvert y\rvert>0$, $\lvert xy\rvert\le p$, and $xy^{i}z\in L$ for all $i\ge 0$. It is used (by
contradiction) to prove a language is not regular; passing it does not prove a language is regular. RAM model (Ch. 14) — The Random Access Memory model of computation: memory is an array of cells
each holding an integer, and every primitive operation (reading/writing a cell, an arithmetic
operation, a comparison, a branch) costs one unit of time; running time is the total operation count
as a function of input size. The cost model underlying all asymptotic analysis in this book. Ramsey theory — the branch of combinatorics studying the conditions under which order must appear in sufficiently large structures ("complete disorder is impossible"). Its central objects are the Ramsey numbers $R(s,t)$, the smallest $n$ such that every red/blue edge-coloring of the complete graph $K_n$ contains a red $K_s$ or a blue $K_t$. Known: $R(3,3)=6$, $R(4,4)=18$; $R(5,5)$ is unknown. random variable (Ch. 20) — A function $X \colon S \to \mathbb{R}$ assigning a real number to each
outcome; despite the name it is neither random nor a variable. The notation $X = a$ denotes the event
$\{s \in S : X(s) = a\}$, and the values of $X$ together with their probabilities form its distribution. recurrence relation (Ch. 18) — An equation that expresses the $n$-th term $a_n$ of a sequence, for
all $n$ beyond some threshold, in terms of one or more of the preceding terms $a_0, a_1, \dots,
a_{n-1}$. On its own it has many solutions; combined with initial conditions it specifies a unique
sequence. (The same object viewed as a definition is a recursive definition, Ch. 7.) recursion tree (Ch. 19) — A diagram of the calls a recursive algorithm makes, used to solve a
recurrence by summing work level by level. For $T(n)=a\,T(n/b)+f(n)$, level $i$ contains $a^i$ nodes
each handling an input of size $n/b^i$ and doing $f(n/b^i)$ non-recursive work, so level $i$ contributes
$a^i f(n/b^i)$; the tree has height $\log_b n$ and $a^{\log_b n}=n^{\log_b a}$ leaves, and the total
cost is $T(n)=\sum_{i=0}^{\log_b n} a^i f(n/b^i)$. recursive definition (Ch. 7) — A definition of a collection given by a basis clause (naming
starting elements outright), a recursive clause (rules for building new elements from existing ones),
and an implicit exclusion clause (nothing is in the collection unless produced by finitely many
applications of the basis and recursive clauses). Also called an inductive definition. recursively defined set (Ch. 7) — A set specified by a recursive definition; its members are
exactly those objects (numbers, strings, expressions, structures) generable from the basis elements by
finitely many applications of the recursive clauses. reduction — An algorithm that transforms every instance of a problem $A$ into an instance of a problem $B$ while preserving the yes/no answer; written $A \le B$ ("$A$ reduces to $B$") and read "$B$ is at least as hard as $A$." A solver for $B$ then yields a solver for $A$, so solvability flows downward and impossibility upward. The standard tool for proving a new problem undecidable: reduce a known undecidable problem (e.g. $\mathrm{HALT}$) to it. Reed-Solomon (Reed–Solomon code) (Ch. 38) — A linear code over a finite field $\mathrm{GF}(q)$ (usually $\mathrm{GF}(2^8)$, one symbol per byte) that treats a $k$-symbol message as the coefficients of a degree-$ reflexive (Ch. 12) — A relation $R$ on $A$ is reflexive if every element is related to itself:
$\forall a \in A,\ (a,a) \in R$. (Digraph: a self-loop on every node; matrix: all-$1$s diagonal.) regular expression (Ch. 35) — A pattern denoting a language, defined recursively from the bases
$\emptyset$, $\varepsilon$, and each symbol $a\in\Sigma$, combined by union $R\mid S$ (denoting
$L(R)\cup L(S)$), concatenation $RS$ (denoting $\{xy : x\in L(R), y\in L(S)\}$), and the Kleene star
$R^{*}$ (zero or more concatenated copies). By Kleene's theorem, the languages denotable by regular
expressions are exactly the regular languages. relation (Ch. 12) — A binary relation from a set $A$ to a set $B$ is a subset
$R \subseteq A \times B$; we write $a\,R\,b$ to mean $(a,b) \in R$. When $A = B$ it is called a relation
on $A$. (A function is the special case in which every input appears in exactly one pair.) relaxation (Ch. 29) — The fundamental update step of every shortest-path algorithm: for an edge
$(u, v)$ of weight $w$, if $\text{dist}[u] + w < \text{dist}[v]$, set $\text{dist}[v] = \text{dist}[u] +
w$ (and record $u$ as the predecessor of $v$). Relaxation is safe: it never sets a tentative distance
below the true shortest-path distance. residual capacity / residual network (Ch. 34) — For a flow $f$, the residual capacity of an ordered pair is $c_f(u,v)=(c(u,v)-f(u,v))+f(v,u)$ — forward slack plus cancellable back-flow. The residual network $G_f$ is the directed graph of all pairs with $c_f(u,v)>0$; it contains forward edges (spare capacity) and back edges $v\to u$ of capacity $f(u,v)$. residue (Ch. 23) — The unique representative $r$ of an integer's congruence class with $0 \le r <
n$; produced by the operator $a \bmod n$. The full set of residues ${0, 1, \dots, n-1}$ is denoted
$\mathbb{Z}_n$. (A residue class is the set of all integers congruent to a given one modulo $n$.) ring — a set $R$ with two operations, $+$ and $\cdot$, such that $(R,+)$ is an abelian group, multiplication is associative, and multiplication distributes over addition. (In this book "ring" means a commutative ring with unity $1\ne 0$.) You can add, subtract, and multiply in a ring, but not necessarily divide. rooted tree (Ch. 31) — A tree together with one distinguished vertex, the root. The root choice
orients every edge away from the root, defining parent/child relationships, ancestors, descendants, and
the subtree rooted at each vertex. RSA — The public-key cryptosystem of Rivest, Shamir, and Adleman (1978). Key generation: pick distinct primes $p, q$; set $n = pq$ and $\phi(n) = (p-1)(q-1)$; choose $e$ with $\gcd(e,\phi(n))=1$; set $d \equiv e^{-1} \pmod{\phi(n)}$. Public key $(n,e)$, private key $d$. Encrypt $c \equiv m^e \pmod n$; decrypt $m \equiv c^d \pmod n$. Correct because $ed \equiv 1 \pmod{\phi(n)}$ forces $m^{ed} \equiv m \pmod n$ (Euler; CRT for the general case); secure under the assumption that factoring $n$ is infeasible. sample space (Ch. 20) — The set $S$ of all possible outcomes of an experiment, where the outcomes
are mutually exclusive (exactly one occurs) and exhaustive (at least one occurs); in discrete
probability $S$ is finite or countable. SAT (Boolean satisfiability problem) — The decision problem: given a Boolean formula, does there exist an assignment of true/false to its variables that makes the whole formula true? The first problem proven NP-complete. satisfiability (Ch. 1) — The property of a compound proposition having at least one assignment of
truth values that makes it true; such a proposition is satisfiable and the assignment is a
satisfying assignment. A proposition with no satisfying assignment is unsatisfiable (a
contradiction). The associated decision problem (SAT) is the prototype hard problem (Ch. 37). sequence (Ch. 11) — A function whose domain is a set of consecutive integers (the indices, usually
$\{0,1,2,\dots\}$); the value at index $n$ is the term $a_n$, and the whole sequence is written
$\{a_n\}$. A sequence may be given by a closed form (a direct rule for $a_n$) or by a recurrence (each
term defined from earlier terms plus initial conditions). series (Ch. 11) — The sum of the terms of a sequence. A finite series is $\sum_{i=m}^{n} a_i$; an
infinite series $\sum_{i=m}^{\infty} a_i$ has a value only if it converges. set (Ch. 8) — An unordered collection of distinct objects, determined entirely by which objects it
contains (so order and repetition do not matter). Shannon entropy — for a discrete random variable $X$ taking value $x_i$ with probability $p_i$, the quantity $H(X) = -\sum_i p_i \log_2 p_i$ bits (with $0\log_2 0 = 0$). It measures the average information content (uncertainty/surprise) per outcome and equals the average codeword length of an optimal code; maximized at $\log_2 n$ when all $n$ outcomes are equally likely. shortest path (Ch. 29) — A path between two vertices of minimum total weight (the sum of its edge
weights) among all paths joining them; need not be unique. Its weight is the shortest-path distance
$\delta(u, v)$, taken to be $\infty$ when no path exists and $0$ from a vertex to itself. shortest-path distance (Ch. 29, supporting) — $\delta(u, v)$, the minimum weight over all paths from
$u$ to $v$ ($\infty$ if none; $0$ if $u = v$; $-\infty$ if a negative cycle lies on some path). shortest-path tree (Ch. 29, supporting) — The tree formed by the predecessor ( single-source / all-pairs shortest paths (Ch. 29, supporting) — The two problem variants: SSSP finds
$\delta(s, v)$ for a fixed source $s$ and all $v$ (Dijkstra, Bellman-Ford); APSP finds $\delta(u, v)$ for
all ordered pairs (Floyd-Warshall). Singleton bound (Ch. 38) — The upper bound $d_{\min}\le n-k+1$ holding for every $[n,k]$ code; codes meeting it with equality (e.g. Reed–Solomon) are called maximum distance separable (MDS). (Supporting term; not in the §1 ledger.) soundness (Ch. 3) — A property of an argument: it is sound if it is valid and all of its premises
are actually true. A sound argument has a guaranteed-true conclusion. source / sink (Ch. 34) — In a flow network, the source $s$ is the vertex where flow originates and the sink $t$ is the vertex where it is collected; flow conservation holds at every other vertex. spanning tree (intro) — A subgraph of a connected graph $G$ that includes every vertex of $G$, is connected, and contains no cycle (a tree on all of $G$'s vertices, using exactly $n-1$ of its edges). The tree edges discovered by any single BFS or DFS of a connected graph form a spanning tree (the BFS tree or DFS tree). Full treatment, including minimum-weight spanning trees, in Chapter 32. stars and bars — A bijective counting technique: the number of ways to distribute $n$ identical objects into $k$ distinct boxes (boxes may be empty) is $\binom{n+k-1}{k-1}$, equal to the number of non-negative integer solutions of $x_1 + x_2 + \cdots + x_k = n$. Objects are represented as $n$ "stars" and the $k-1$ dividers between boxes as "bars." strong induction (Ch. 7) — A proof technique establishing that $P(n)$ holds for all integers
$n \ge n_0$ by proving the necessary base case(s) and a step in which $P(k+1)$ is derived from the
assumption that $P(n_0), P(n_0+1), \dots, P(k)$ are all true (the strong inductive hypothesis). It is
logically equivalent to ordinary induction. structural induction (Ch. 7) — A proof technique establishing that a property $P$ holds for every
element of a recursively defined set by proving $P$ for each basis element (basis step) and proving
that $P$ is preserved by each recursive clause (recursive step, assuming $P$ for the parts being
combined). Its validity rests on the exclusion clause. Subdivision (of a graph) — supporting term defined inline in §33.4: the result of replacing some edges with paths by inserting new degree-2 vertices; preserves planarity. (Noted here for the orchestrator; assign ownership to Ch.33 if not claimed elsewhere.) subgroup — a subset $H\subseteq G$ that is itself a group under the same operation as $G$; equivalently, $H$ contains the identity and is closed under the operation and under taking inverses. Every group has the two trivial subgroups $\{e\}$ and $G$. subset (Ch. 8) — A set $A$ such that every element of $A$ is also an element of $B$, written $A
\subseteq B$; equivalently $\forall x\,(x \in A \rightarrow x \in B)$. If additionally $A \ne B$, then
$A$ is a proper subset ($A \subset B$). sum rule (Ch. 15) — If a task can be done in one of several mutually exclusive ways — $n_i$ ways for
case $i$ — then it can be done in $n_1 + n_2 + \cdots + n_k$ ways; equivalently, for pairwise-disjoint
finite sets, $\lvert A_1 \cup \cdots \cup A_k \rvert = \lvert A_1 \rvert + \cdots + \lvert A_k \rvert$. summation (Ch. 11) — The operation and notation $\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n$
that adds the terms of a sequence from a lower limit $m$ to an (inclusive) upper limit $n$; $i$ is the
bound index of summation. An empty sum (lower limit exceeding upper) equals $0$. surjection (Ch. 9) — A surjective (onto) function: every codomain element is the image of some
input, i.e. $\forall b \in B,\ \exists a \in A$ with $f(a) = b$; equivalently $\operatorname{range}(f)
= B$. symmetric (Ch. 12) — A relation $R$ on $A$ is symmetric if $(a,b) \in R$ implies $(b,a) \in R$ for
all $a, b \in A$. (Digraph: every arrow has its reverse; matrix: $M = M^{\mathsf{T}}$.) symmetric-key cryptography — Encryption in which the same key (or two keys trivially derived from each other) is used to encrypt and to decrypt, so sender and receiver must share a single secret in advance; anyone who learns it can both read and forge messages. Contrast with public-key cryptography. syndrome (Ch. 38) — For a received word $y$, the syndrome is $s=Hy^{\mathsf T}$. Since $Hc^{\mathsf T}=\mathbf 0$ for any codeword $c$, the syndrome of $y=c\oplus e$ equals $He^{\mathsf T}$ and so depends only on the error $e$. For a Hamming code, whose $H$ has column $j$ equal to $j$ in binary, the syndrome read as a binary number is exactly the position of a single-bit error ($\mathbf 0$ = no detected error). (Ch.26 used "syndrome" operationally in its Toolkit checkpoint; canonical definition is reserved here — flagged in continuity.) s–t cut (Ch. 34) — A partition $(S,T)$ of a flow network's vertices with $s\in S$ and $t\in T$. Its capacity is the total capacity of edges directed from $S$ to $T$; edges from $T$ to $S$ and within a side do not contribute. tautology (Ch. 1) — A compound proposition that is true for every assignment of truth values to
its variables (its output column is all $T$). Example: $p \lor \neg p$. technical write-up — a structured communication of a built system: problem and model, design and build, correctness argument, evidence (with limits), and complexity/scope; the deliverable that turns working code into a defensible result. telescoping (Ch. 11) — A summation technique (and the sums it applies to) in which the summand is
written as a difference of consecutive values of some sequence, $a_i = t_i - t_{i-1}$, so that
intermediate terms cancel in pairs and the sum collapses to its endpoints: $\sum_{i=1}^{n}(t_i -
t_{i-1}) = t_n - t_0$. Used to derive (not merely verify) closed forms, including the power sums. theorem (Ch. 4) — A statement that has been proved true by a valid logical argument; the label is
usually reserved for results of some importance (a minor true statement may be called a proposition or
fact). topological sort — A total order on the elements of a finite poset (or directed acyclic graph) that is consistent with the partial order: whenever $a \preceq b$, $a$ appears before $b$. Also called a linear extension or topological ordering. Every finite poset has one. total order — A partial order in which every two elements are comparable (for all $a,b$, either $a \preceq b$ or $b \preceq a$); also called a linear order. A set with a total order is a chain. totient (Ch. 23) — Euler's totient function $\phi(n)$: the number of integers in ${1, 2, \dots,
n}$ coprime to $n$, equal to the number of units modulo $n$. Key values: $\phi(p) = p - 1$ for prime
$p$; $\phi(mn) = \phi(m)\phi(n)$ when $\gcd(m, n) = 1$; hence $\phi(pq) = (p-1)(q-1)$ for distinct
primes $p, q$. transitive (Ch. 12) — A relation $R$ on $A$ is transitive if $(a,b) \in R$ and $(b,c) \in R$ imply
$(a,c) \in R$ for all $a, b, c \in A$. (Digraph: every two-step path has a direct shortcut.) transitive closure (Ch. 12) — The smallest transitive relation containing a given relation $R$;
equivalently, the reachability relation of $R$'s digraph: $(a,b)$ is in the transitive closure iff there
is a path of length $\ge 1$ from $a$ to $b$. trapdoor function — A function that is easy to evaluate but computationally infeasible to invert in general, except for anyone holding a secret "trapdoor," for whom inversion is also easy. (A one-way function with no trapdoor cannot be used for encryption, since the legitimate receiver could not decrypt.) RSA's trapdoor: multiplying two large primes is easy, factoring the product is hard, and knowing the factors makes inversion easy. Traveling Salesman Problem (TSP) — Given $n$ cities and the pairwise costs of travel between them, find a tour visiting every city exactly once and returning to the start that minimizes total cost; equivalently, the minimum-cost Hamilton circuit on a complete weighted graph. The decision form (is there a tour of cost $\le B$?) is NP-complete; the optimization form is NP-hard. The number of distinct symmetric tours is $(n-1)!/2$. traversal (Ch. 31) — A systematic visit of every node of a tree exactly once. The principal
depth-first orders for binary trees are preorder, inorder, and postorder; level-order (breadth-first)
visits nodes by increasing depth. tree (Ch. 31) — A connected, acyclic undirected graph. Equivalently: a graph with exactly one path
between every pair of vertices; a minimally connected graph (removing any edge disconnects it); or a
maximally acyclic graph (adding any edge creates a cycle). A tree on $n$ vertices has exactly $n - 1$
edges. trie (Ch. 31) — A rooted tree storing a set of strings as shared prefixes: each edge is labeled with
a character, the path from the root to a node spells a prefix, and flagged nodes mark complete words.
Lookup of a length-$m$ string costs $O(m)$, independent of the number of stored strings. trivial proof (Ch. 4) — A proof of $P \rightarrow Q$ that works by showing the conclusion $Q$ is
always true, without using the hypothesis $P$. truth table (Ch. 1) — A table listing every one of the $2^n$ assignments of truth values to the
$n$ variables of a compound proposition, together with the resulting truth value in each case. truth value (Ch. 1) — One of the two values a proposition can take: true ($T$) or false ($F$);
the Booleans Turing machine — The standard formal model of computation: a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ consisting of a finite set of states, a finite input alphabet, a finite tape alphabet (including a blank symbol), a transition function $\delta\colon Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, a start state, and distinct accept and reject states. It operates on an unbounded tape via a read/write head; on any input it either accepts, rejects, or runs forever. Captures exactly the class of mechanically computable functions. uncountable (Ch. 10) — A set that is not countable: no list $s_0, s_1, s_2, \dots$ can contain
every element (any proposed list provably misses one, by diagonalization). Example: $\mathbb{R}$. undecidable — A decision problem is undecidable if it is not decidable: no Turing machine halts on all inputs and always answers it correctly. By the Church–Turing thesis, undecidable means no algorithm in any language can always solve it. The halting problem is the canonical example. union (Ch. 8) — The set of elements in either of two sets, $A \cup B = {x \mid x \in A \lor x \in
B}$ (inclusive or). union by rank (Ch. 32) — A union-find optimization that attaches the shorter (lower-rank) tree
under the taller one's root during union-find (disjoint-set) (Ch. 32) — A data structure maintaining a collection of disjoint sets
with two operations: uniqueness proof (Ch. 5) — A proof that at most one object satisfies a property, typically by
assuming two objects $x_1, x_2$ both satisfy it and deriving $x_1 = x_2$. To prove "there is exactly one
$x$" ($\exists!\, x\, P(x)$) one must prove both existence and uniqueness. universal quantifier (Ch. 2) — The symbol $\forall$; the statement $\forall x\, P(x)$ ("for all
$x$, $P(x)$") is true exactly when $P(x)$ holds for every element of the domain. Over a finite domain it
is a conjunction of $P$ over all elements; over the empty domain it is vacuously true. vacuous proof (Ch. 4) — A proof of $P \rightarrow Q$ that works by showing the hypothesis $P$ is
always false, so the conditional holds regardless of $Q$. validity (Ch. 3) — A property of an argument's form: an argument is valid if no assignment of truth
values makes all premises true while making the conclusion false; equivalently, if the conditional
(conjunction of premises) $\rightarrow$ conclusion is a tautology. variance (Ch. 20) — The expected squared deviation of a random variable from its mean,
$\operatorname{Var}(X) = E[(X - \mu)^2] = E[X^2] - (E[X])^2$ where $\mu = E[X]$; it measures the spread
of the distribution (in squared units). Its square root is the standard deviation $\sigma$. verifier — A polynomial-time algorithm $V(x, c)$ that, given an instance $x$ and a candidate certificate $c$, accepts iff $c$ proves $x$ is a yes-instance; the existence of such a $V$ (with short certificates that exist for every yes-instance and fool the verifier on no-instances) defines membership in NP. vertex (Ch. 27) — An element of a graph's vertex set $V$; the "dot" of a graph (plural: vertices;
also called a node). Represents the thing being connected (a person, intersection, page, module). weight (Ch. 38) — The weight $\operatorname{wt}(z)$ of a string is its number of nonzero positions, i.e. its Hamming distance from the all-zeros string. (Supporting term; not in the §1 ledger.) weight function (Ch. 29, supporting) — The map $w \colon E \to \mathbb{R}$ that assigns each edge of
a weighted graph its weight; the defining datum of a weighted graph. weight of a spanning tree (Ch. 32) — The sum of the weights of a tree's edges,
$w(T) = \sum_{e \in E_T} w(e)$ (also called its cost). weighted graph (Ch. 27) — A graph together with a weight function $w \colon E \to \mathbb{R}$
assigning a real number (cost, distance, capacity, or strength) to each edge. The "shortest path" then
minimizes total edge weight rather than edge count. well-ordering (Ch. 7) — The principle that every non-empty subset of the natural numbers
$\mathbb{N} = \{0, 1, 2, \dots\}$ has a least element. It fails for $\mathbb{Z}$ and for the positive
rationals, and it is the foundation beneath all forms of mathematical induction and of termination
arguments. without loss of generality (Ch. 5) — (Abbreviated WLOG.) A phrase used in a proof by cases to
handle a single representative of a set of symmetric cases, asserting that the remaining cases follow by
identical reasoning after relabeling. Legitimate only when the variables involved are genuinely
interchangeable in the statement. worst case (Ch. 14) — For inputs of size $n$, the maximum running time over all such inputs,
$\max_{|x|=n} T(x)$; a guarantee the algorithm never exceeds, and the default measure when complexity
is stated without qualification.self_test(), which asserts one round-trip per major module.J
K
L
M
N
O
P
find: after reaching the
root, every node visited on the way is repointed directly to the root, flattening the tree for future
queries.insert(item, key) and extract_min() (remove and return the minimum-key
element). Unlike a FIFO queue, it returns the currently cheapest element regardless of insertion order.
Typically implemented with a binary heap (Chapter 31), giving $O(\log n)$ per operation.R
S
prev) pointers a
shortest-path algorithm records, rooted at the source; every shortest path from the source is a root-to-
vertex path in this tree.T
True/False in code. (Defined inline; not reserved elsewhere — see continuity note.)U
union, keeping trees shallow. (Union by size is the analogous
variant using element counts.)find(x), returning a canonical representative of $x$'s set, and union(x, y),
merging two sets. Used by Kruskal to test, in near-constant time, whether two vertices are already
connected.V
W