Index

Page references are by chapter and section number.

"n choose r" — 16.2
$1/e$ (derangement limit) — 17.6
$n$-tuple — 8.4
0^n 1^n (canonical non-regular language) — 35.5
2-opt (local search) — 30.6, key-takeaways
2-SAT (in P) — 37.5, 37.6, Spaced Review
3-SAT — 37.5

A

abelian group (commutative group) — 24.2
absorption law — 1.4, 1.5
accept state / reject state — 36.1
accepting / final state — 35.2
acyclic graph — 31.1
addition (rule of inference) — 3.2
additive inverse (uniqueness example) — 5.4
additivity (probability) — 20.2
adjacency list — 28.6, 28.1
adjacency matrix — 28.6, 40.5 [Ch. 28], 28.1
adjacent — 27.2
adversary / counting argument — 14.6
AES (S-box, MixColumns) — 24.5, 24.6
affine cipher (inverse example) — 23.3
affirming the consequent — 3.3
aggregate / amortized counting — 28.6
Akra–Bazzi method — §19.6
al-Khwarizmi (origin of "algorithm") — 14.1
al-Kindi (frequency analysis, attribution) — 25.1
aleph-null — 10.5
algebra of logic (equivalence proof) — 1.4
algebraic structure — 24.1
algorithm — 14.1
algorithm vs. implementation — 14.1
algorithmic-complexity attack — 26.3
all() as universal quantifier — 2.5
all-horses-same-color fallacy — 6.6
alphabet ($\Sigma$) — 35.1
alphabet (binary) — 38.1
alternating sum identity — 16.4
alternating sum of binomial coefficients — 17.4
ancestor / descendant — 31.2
anti-diagonal sweep — 10.2
antisymmetric — 12.3
any() as existential quantifier — 2.5
append (concatenation) — 7.5
approximation algorithm — 30.6, Summary
approximation algorithm (Christofides) — 37.6
approximation algorithms (mention) — 40.5
arbitrary element (UG) — 3.4
arc (directed edge) — 27.3
argument — 3.1
arithmetic expression grammar — 7.3, 7.4
arithmetic sequence — 11.3
arithmetic series — 11.3
arity (of a predicate) — 2.1
array representation of a heap — 31.5
arrow / morphism — 40.4
assignment problem — 34.6
associated homogeneous recurrence — 18.5
asymptotic analysis — 14.3
augmenting path — 34.3
average case — 14.6

B

back edge — 28.4
back edge (residual) — 34.3
backreference (non-regular, mentioned) — 35.4
balanced parentheses (non-regular) — 35.5
base case — 6.2, 6.3
base cases, counting (strong induction) — 7.1
base rate — 21.4
base-rate fallacy — 21.4
basis clause — 7.3, 7.4
bayes (toolkit function) — 21.3, Project Checkpoint
Bayes' theorem — 21.3
bayes_update (toolkit function) — Project Checkpoint
begging the question — 4.5
best case — 14.6
BFS correctness (queue invariant) — 28.2
BFS tree / DFS tree — 28.4
biconditional — 1.2, 1.3
biconditional (proving both directions) — 4.3
Big-O notation — 14.3
Big-Omega notation — 14.3
Big-Theta notation — 14.3
bijection (combinatorial proof) — 16.5
bijection (in stars-and-bars proof) — 17.3
bijective / bijection / one-to-one correspondence — 9.3
binary entropy function — 40.2
binary exponentiation — 23.5
binary operation — 24.1
binary search — §19.1, §19.4
binary search (analysis) — 14.4
binary search tree (BST) — 31.4
binary strings avoiding "00" — 18.2
binary symmetric channel — 38.1, 40.2
binary tree — 31.3
binomial coefficient — 16.2, 16.4, 16.5
binomial theorem — 16.4
bipartite graph — 27.3
bipartite matching — 34.5, 40.1 [Ch. 34]
bipartition — 27.3
birthday problem — 20.2
block / cell (of a partition) — 12.4
block / message size (RSA) — 25.4
block code — 38.1
block length — 38.1
Borůvka's algorithm — 32.1 (Learning Paths), 32.6
bottleneck (of an augmenting path) — 34.3
bound variable — 2.5
bounded halting ("halts within N steps") — 36.6
branch-and-bound (Concorde, mention) — 30.5
branch-and-bound / Held–Karp — 37.6
branching factor (a) — §19.1
breadth-first search (BFS) — 28.4, 28.6, 28.2
bridges of Königsberg — 30.2, 30.1, Summary
brute-force attack (on a cipher) — 25.1
brute-force feasibility — 16.6
brute-force search (counting) — 15.1, 15.6
brute-force search (TSP) — 30.5
BST insertion — 31.4
BST property / invariant — 31.4
BST search — 31.4
burst error — 26.5
burst error (in coding) — 38.6
Bézout coefficients — 22.5
Bézout's identity — 22.5
Bézout's identity (for inverse) — 23.3

C

Caesar cipher — 25.1
cancellation (modular, restriction on) — 23.2, 23.3
canonical remainder (Python %) — 22.3
Cantor pairing function — 10.2, Project Checkpoint
Cantor's diagonal argument (diagonalization) — 10.3
Cantor's theorem — 10.5
capacity (of an edge) — 34.1
capacity constraint — 34.1
capacity of a cut — 34.4
cardinality (finite) — 8.1
cardinality (infinite) — 10.1
Carter–Wegman family — 26.3
Cartesian product — 8.4
Cartesian product (used; defined Ch. 8) — 12.1
category — 40.4
category theory — 40.4
Cayley's formula — 32.1
ceiling function — 9.5
certain event — 20.1
certificate (witness) — 37.3, 37.4, 37.2
change of coordinates (CRT as) — 23.4
change of logarithm base — 14.4
channel capacity — 40.2
characteristic equation — 18.4
characteristic root — 18.4
characterizations of trees — 31.1
checksum — 26.4
Chinese Remainder Theorem — 23.4
Chinese Remainder Theorem (in RSA proof) — 25.5
Chomsky hierarchy — 35.6
choosing a proof strategy — 5.6
choosing the counting model (order? repetition?) — 16.3
chosen-plaintext comparison attack — 25.6
Christofides' algorithm — 30.6, Summary
Church–Turing thesis — 36.2
Church–Turing thesis (strong / extended) — 37.1
cipher — 25.1
ciphertext — 25.1
CIRC (CD error correction) — 38.6
circular arrangement — 15.5
circular permutation / circular arrangement — 16.1
classification of finite fields (Theorem 24.5) — 24.5
clause / literal — 37.3, 37.5
CLIQUE — 37.5
closed form (explicit formula) — 18.1
closed form (of a sequence) — 11.1
closure (of a relation) — 12.5
closure (property) — 24.1, 24.2
code — 38.1
code rate — 38.2
code to recurrence — 18.6
codeword — 38.1
codomain — 9.2
coefficient extraction $[x^n]$ — 17.5
collision — 26.2
collision (hash) — 17.1, Summary; (forward to Ch.26)
collision (hashing) — 9.6
collision resistance — 26.6
collision resolution (chaining, probing) — 26.1, 26.2
collision theorem (collisions unavoidable) — 26.2
combination — 16.2, 16.3
combinations with repetition — 17.3
combinatorial explosion — 15.6
combinatorial optimization — 40.1
combinatorial proof — 16.5
committee–chair identity — 16.5
common difference — 11.3
common proof mistakes — 4.5
common ratio — 11.3
commutative ring with unity — 24.4
complement — 8.3
complement counting — 15.6, 17.4, 17.6
complement rule (probability) — 20.2
complete binary tree — 31.3
complete bipartite graph, K_{m,n} — 27.3
complete graph $K_n$ (Euler vs. Hamilton) — 30.3, key-takeaways
complete graph, K_n — 27.3
complexity class — 37.1
complexity of traversal — 28.6
composite — 22.2
composition (of arrows) — 40.4
composition of functions — 9.4
composition, associativity of — 9.4
composition, non-commutativity of — 9.4
computable / definable real number — 10.6
computational formula for variance — 20.5
computational infeasibility — 26.6
concatenation (regex) — 35.4
conclusion — 3.1
conclusion (consequent) — 1.2
condition on the last choice (setup move) — 18.2
condition simplification — 1.5
conditional independence (given the class) — 21.5
conditional probability — 21.1
conditional statement (proving) — 4.3
conditioning (shrinking the sample space) — 21.1
configuration (of a Turing machine) — 36.1
congruence — 23.1
congruent modulo n — 23.1
conjecture — 4.1
conjecture, disproving (used) — 5.5
conjunction — 1.2, 1.3
conjunction (rule of inference) — 3.2
conjunctive normal form (CNF) — 37.5
connected — 27.2
connected component — 27.2, 28.4
connected graph (tree context) — 31.1
connective — 1.2
connectivity (required for Euler) — 30.2, Spaced Review, Summary
connectivity (testing via traversal) — 28.4
Cons / Nil — 7.5
conservation constraint (flow conservation) — 34.1
constant coefficients — 18.3
constant time — 14.5
constrained selection (generating function) — 17.5
constructive proof — 5.4
context-free language — 35.6
context-sensitive language — 35.6
contingency — 1.4
continuum — 10.5
Continuum Hypothesis — 10.5
contradiction — 1.4
contraposition template — 4.4
contrapositive — 1.4, 4.4
convergence (of a series) — 11.3
converse — 1.4
converse (vs. contrapositive) — 4.4
convolution (power-series multiplication) — 17.5
Cook–Levin theorem — 37.4, Summary
coping with intractability (menu) — 37.6
coprime / relatively prime — 22.4
coprime message case ($\gcd(m,n)=1$) — 25.5
corner / vertex (of a polytope) — 40.1
corollary — 4.1
Corollary (a^|G| = e in a finite group) (24.3) — 24.3
correction threshold (Theorem 38.3) — 38.3
coset — 24.3
countable — 10.2
countable union of countable sets — 10.2
countably infinite — 10.2
counterexample — 2.4
counterexample (to an argument) — 3.1
counterexample (used) — 5.5
counting principle — 15.1
coupon-collector problem (mention) — 17.6
critical exponent (log_b a) — §19.3, §19.2
crossing edge — 32.5
CRT construction — 23.4
cryptographic hash function — 26.6
cubic time — 14.5
cut — 32.5
cut property — 32.5
cut vertex (mentioned) — 27.2
cycle — 27.2
cycle detection (undirected) — 28.4
cycle property — 32.5
cyclic group — 24.3
cyclic multiplicative group of a finite field (Theorem 24.6) — 24.5
cyclic redundancy check (CRC) — 24.6, 26.5

D

De Morgan's laws — 1.4, 1.5
De Morgan's laws (for sets) — 8.5
dead state / trap state — 35.2
decidable (recursive) — 36.3
decider — 36.3
decimal expansion (uniqueness) — 10.3
decision problem — 10.4, 36.3 (uses Ch.10), 37.6, 37.1
decision table (four counting models) — 16.3
decision vs. optimization (TSP) — 30.5, Summary
declarative statement — 1.2
Dedekind-infinite set — 10.1
deduplication — 8.6
deficiency (Hall's condition) — 34.5
definiteness / finiteness / effectiveness (algorithm properties) — 14.1
degenerate BST — 31.4
degree sequence — 27.4, 27.5
degree, deg(v) — 27.2
degrees of separation — 28.2 (social-network anchor)
dense graph — 28.1, 28.6
denying the antecedent — 3.3
dependency graph — 27.6
depth (of a vertex) — 31.2
depth-first search (DFS) — 28.4, 28.5, 28.6, 28.3
derangement — 17.6
derangement recurrence — 17.6
derivation — 3.5
detection threshold (Theorem 38.2) — 38.3
deterministic encryption (weakness) — 25.6
deterministic finite automaton (DFA) — 35.2
diagonalization (applied to programs) — 36.4 (defined Ch.10)
Diffie-Hellman key exchange (mention) — 24.3, 24.6
Diffie–Hellman (attribution; Ellis/Cocks/Williamson) — 25.3
digest — 26.6
digital signature — 25.6
digraph (frequency) — 25.1
dimension of a code — 38.5
Dirac's theorem — 30.3, Summary
direct proof — 4.3
direct-proof template — 4.3
directed acyclic graph (DAG) — 28.5
directed graph (digraph) — 27.3
discrete logarithm — 24.3, 24.6
disjoint events — 20.1, 20.2
disjoint sets — 8.3
disjoint sets (in counting) — 15.3, 15.4
disjoint-set forest — 32.3
disjunction (inclusive or) — 1.2, 1.3
disjunctive syllogism — 3.2
disproof — 5.5
disprove_forall (Toolkit) — Project Checkpoint
distinct roots (case) — 18.4
distribution (of a random variable) — 20.3
distributive law (for sets) — 8.5
distributive law (logic) — 1.4, 1.5
divide-and-conquer — §19.1
divide-and-conquer (exponent halving) — 23.5
divide-and-conquer recurrence — §19.1
divide-and-conquer recurrence (forward to Ch. 19) — 18.6
divide-and-conquer, relation to strong induction — 7.1
divides ($a \mid b$) — 22.1
divides / divisibility ($a \mid b$) — 4.2
divisibility — 22.1
divisibility counting (1..1000 by 2,3,5) — 17.4
divisibility, in contradiction proofs (used) — 5.1
divisibility, proof by induction — 6.3
divisible difference (pigeonhole, mod m) — 17.1
Division Algorithm — 22.3
division algorithm (existence) — 7.2
division rule — 15.5
divisor / factor — 22.1
divisor / factor / multiple — 4.2
dmtoolkit summary() — Project Checkpoint
domain — 9.2
domain (domain of discourse, universe) — 2.1, 2.2
domino tiling (2×n board) — 18.2
dominoes (intuition) — 6.1
double counting — 16.5, 27.4
doubling loop — 11.6
doubling ratios — Project Checkpoint
dropped-case error — 4.6
dual (linear program) — 40.1

E

easy-vs-hard boundary — 30.4, What's Next, Summary
ECC memory (error-correcting memory) — 38.4
edge — 27.1
Edmonds–Karp algorithm — 34.3
element (of a set) — 8.1
element method (of proof) — 8.5
empirical complexity estimator — Project Checkpoint
empty language vs. {ε} — 35.1
empty product — 11.5
empty set — 8.1
empty string ($\varepsilon$) — 35.1
empty sum — 11.2
empty-acceptance problem (EMPTY) — 36.5
encode / decode — 38.1
endpoint — 27.2
enumeration — 10.2
equally-likely model — 20.2
equinumerous — 10.1
equivalence class — 12.4
equivalence of induction forms — 7.6
equivalence of NFA and DFA — 35.3
equivalence relation — 12.4
equivalence relation (congruence as) — 23.1
equivalent (Toolkit) — Project Checkpoint
Erdős probabilistic lower bound (R(k,k) > 2^{k/2}) — 40.3, attributed Erdős 1947
error amplification (repetition) — 21.6
error correction (vs. detection) — 38.1, 38.3
error detection (vs. correction) — 38.1, 38.3
error detection vs. error correction — 26.6, Project Checkpoint
error polynomial — 26.5
Euclid key lemma ($\gcd(a,b)=\gcd(b, a\bmod b)$) — 22.4
Euclid's Lemma — 22.5
Euclid's number ($p_1\cdots p_r + 1$) — 22.2
Euclidean algorithm — 22.4
Euler (Leonhard), 1736 — 30.1, 30.2
Euler circuit (Euler tour) — 30.4, 30.2, Summary, Project Checkpoint
Euler path — 30.4, 30.2, Summary
Euler's prime-generating polynomial — 5.5
Euler's theorem — 23.6, 30.2, Summary
Euler's theorem (derived from Corollary 24.3) — 24.3 [first-defined Ch. 23]
Euler's theorem (in RSA proof) — 25.5
Euler's totient function — 23.6
Euler's totient phi(n) (as |Z_n^*|) — 24.2, 24.3 [first-defined Ch. 23]
Euler–Mascheroni constant — 11.4
evaluation map (polynomial code) — 38.6
even (definition) — 4.2
even parity / odd parity — 26.4
even-degree condition — 30.2
event — 20.1
evidence (Bayes denominator) — 21.3
exchange argument — 31.6, 32.5
exclusion clause — 7.3, 7.4
exclusive or (xor) — 1.2, 1.3
exhaustive cases — 5.3
existence of modular inverse — 23.3
existence proof — 5.4
existential generalization (EG) — 3.4
existential instantiation (EI) — 3.4
existential quantifier — 2.2
expectation — 20.4
expected number of empty buckets — 20.4
expected value — 20.4
explicit formula — 18.1
exponent reduction (mod phi) — 23.6
exponential / factorial time — 30.4, 30.5
exponential function — 9.5
exponential running time (naive Fibonacci) — 18.6
exponential state blow-up — 35.3
exponential time — 14.5
exponentiation by squaring — 6 (case study 2), §19.5
expression tree — 31.5
extended Euclidean algorithm — 22.5
extended Euclidean algorithm (for inverse) — 23.3
extended Master Theorem (n^E log^k n) — §19.6

F

factorial — 11.5
factorial growth — 11.5
factorial overflow — 11.5
factorial time — 14.5
factoring (NP, not known NP-complete) — 37.6
fallacy — 3.3
falling product (computing P(n,r)) — 16.1
false-positive rate — 21.4
fast modular exponentiation (RSA use) — 25.4
fast power (mod_pow) — 23.5
feasible region / polytope — 40.1
Fermat's little theorem — 23.6
Fermat's little theorem (derived from Corollary 24.3) — 24.3 [first-defined Ch. 23]
Fermat's little theorem (in RSA proof) — 25.5
Fibonacci generating matrix — §19.5
Fibonacci numbers — 6.4
Fibonacci numbers, growth bound — 7.1
Fibonacci recurrence — 18.2, 18.4, 18.6
Fibonacci sequence — 11.1
Fibonacci worst case (Euclidean algorithm) — 22.4
Fibonacci, closed form (Binet's formula) — §19.5
field — 24.4
field criterion for Z_n (Theorem 24.4) — 24.4
FIFO queue (in BFS) — 28.2
find operation (union-find) — 32.3
find_counterexample (Toolkit) — Project Checkpoint
finding the maximum (lower bound) — 14.6
finishing time (DFS post-order) — 28.5
finite field — 24.5
finite injective–surjective equivalence — 9.3
fixed point (of a random permutation) — 20.4
fixed-parameter tractable (FPT) — 37.6
floating-point as countable approximation — 10.6
flood fill — 28.4
floor function — 9.5
floor function (counting multiples) — 15.4
flow — 34.1
flow network — 34.1
forcing term — 18.5
Ford–Fulkerson method — 34.3
forest — 31.1
formal fallacy — 3.3
formal power series — 17.5
formal proof — 3.5
forward edge (residual) — 34.3
free variable — 2.5
frequency analysis — 25.1
freshness condition (EI) — 3.4
frozenset — 8.6
full binary tree — 7.5, 31.3
function — 9.1, 9.2
function as a relation — 9.1
function composition — 40.4 [Ch. 9]
functions N -> {0,1}, uncountability of — 10.4
functor — 40.4
fundamental theorem of arithmetic (FTA) — 22.6

G

gadget reduction (3-SAT ≤_p CLIQUE) — 37.5
Galois field — 24.5
gcd (greatest common divisor) — 22.4
gcd–lcm identity ($\gcd\cdot\operatorname{lcm}=ab$) — 22.6
general number field sieve (mention) — 25.6
general recursive functions — 36.2
generalized pigeonhole principle — 17.2
generalized pigeonhole principle (worst chain length) — 26.2
generating function (ordinary, OGF) — 17.5
generator — 24.3
generator matrix — 38.5
generator polynomial — 26.5
geometric sequence — 11.3
geometric series — 11.3
geometric series (as generating function $1/(1-x)$) — 17.5
geometric series (in recurrence solving) — §19.2
GF(2^8) (AES, Reed-Solomon) — 24.5, 24.6
GF(2^n) — 24.5, 24.6
GF(p) — 24.5
golden ratio (forward to Ch. 19) — 18.4
golden ratio (mention) — 11.1
golden ratio (phi) — §19.5
grammar / production rule — 35.6
graph — 27.1
graph 3-coloring (complexity) — 37.5
graph isomorphism — 27.5
greedy algorithm (suboptimal for TSP) — 30.6
group — 24.2
group as one-object category — 40.4 [Ch. 24]
group axioms (associativity, identity) — 40.4 [Ch. 24]
growth-rate hierarchy — 11.5, 11.6, 14.5

H

Hall's marriage theorem — 34.5
halt (vs. loop forever) — 36.1, 36.3, 36.4
halting problem (HALT) — 36.5, 36.6, 36.4
halting problem (preview) — 5.2
halving loop / logarithmic time — 14.4
Hamilton (William Rowan); Icosian game — 30.3
Hamilton circuit (complexity / NP membership) — 37.2, 37.5, Project Checkpoint
Hamilton circuit (Hamilton cycle) — 30.4, Summary, 30.3
Hamilton path — 30.4, Summary, 30.3
Hamming ball (decoding sphere) — 38.3
Hamming code — 38.4
Hamming code / linear code over GF(2) — 40.2 [Ch. 38]
Hamming distance — 38.2, Project Checkpoint
Hamming distance is a metric (Theorem 38.1) — 38.2
Hamming(7,4) code — 38.4, Project Checkpoint
handshaking lemma — 27.4
handshaking lemma (in time analysis) — 28.6 (defined in Ch.27)
harmonic number — 11.4
harmonic number (in quicksort analysis) — 21.6
hash collision (probability) — 20.2
hash function — 9.6, 26.1
hash function (as pigeonhole example) — 17.1
hash table — 26.1
hashable — 8.6
hat-check problem — 17.6, 20.4
heap — 31.5
heap property — 31.5
height (of a tree) — 31.2
Held–Karp dynamic programming — 30.5, key-takeaways
heuristic — Summary, 30.6
heuristic (nearest-neighbor, local search) — 37.6
Hierholzer's algorithm — 30.2, Project Checkpoint
Hilbert's Hotel — 10.5
Hilbert's tenth problem — 36.5
Hindley–Milner type inference — 3.6
homogeneous recurrence — 18.3
homogeneous solution — 18.5
Horner's method — 6 (case study 1)
Horner's rule (in hashing) — 26.1
Huffman coding — 31.6, 40.2 [Ch. 31]
Huffman optimality — 31.6
Huffman tree — 31.6
hypothesis (antecedent) — 1.2
hypothetical syllogism — 3.2

I

identity arrow — 40.4
identity function — 9.4
image (of a set) — 9.2
image (of an element) — 9.1
image segmentation (graph cut) — 34.6
implication — 1.2, 1.3
impossibility results — 5.2
impossible event — 20.1, 20.2
in-degree, out-degree — 27.3
incidence ((vertex, edge) pair) — 27.4
incident — 27.2
inclusion-exclusion — 15.4
inclusion-exclusion, three sets — 15.4
inclusion-exclusion, two sets — 15.4
inclusion–exclusion (probability) — 20.2
inclusion–exclusion principle (general) — 17.4
inclusion–exclusion, sign rule — 17.4, Summary
independence (of events) — 21.2
INDEPENDENT SET — 37.5
independent vs. mutually exclusive — 21.2
index of summation — 11.2
index shift — 11.2
indicator expectation — 20.4
indicator random variable — 20.3, 20.4, 21.6
inductive definition — 7.3
inductive hypothesis — 6.2, 6.4
inductive step — 6.2, 6.3
inference rule — 3.2
infinite geometric series — 11.3
infinitude of primes (Euclid's theorem) — 5.1, 22.2
infix / prefix / postfix notation — 31.5
information theory — 40.2
initial condition — 11.1, 18.1
initialization (loop) — 6.5
injective / injection / one-to-one — 9.3
inorder traversal — 31.3
input size — 14.2
input space, sizing — 15.6
integer factorization (hardness) — 25.6
integer linear programming (ILP) — 40.1
integers, countability of — 10.2
integrality (of integer-capacity max flow) — 34.5
interior-point method — 40.1
internal node — 31.2
intersection — 8.3
invalid argument — 3.1
inverse Ackermann function — 32.3
inverse function — 9.4
invertibility theorem (invertible iff bijective) — 9.4
irrational number — 5.1
irreducible polynomial — 24.5
is_tautology (Toolkit) — Project Checkpoint
is_tree (toolkit) — Project Checkpoint
ISBN-10 check digit — 26.4
isolated vertex — 27.2
isomorphic graphs — 27.5
isomorphism (Z_N and product) — 23.4
isomorphism invariant — 27.5
iterative DFS (explicit stack) — 28.3

J

join (relational) — 12.6
joins (an edge joins two vertices) — 27.1
joint probability table — 21.1

K

k-ary relation — 12.6
Karatsuba multiplication — §19.1, §19.3
Kerckhoffs's principle — 25.1
key (cryptographic) — 25.1
key (database) — 12.6
key generation — 25.4
key size (RSA, 1024/2048/3072 bits) — 25.6
key space (size) — 25.1, 25.6, Summary
key-distribution problem (key exchange) — 25.2
keyspace — 15.1, 15.6
keyspace sizing — 15.6
Kirchhoff's matrix-tree theorem — 32.1
Kleene star (regex) — 35.4
Kleene star of an alphabet ($\Sigma^{*}$) — 35.1
Kleene's theorem — 35.4
Kruskal's algorithm — 32.3

L

Lagrange's theorem (Theorem 24.2) — 24.3
lambda calculus — 36.2
language — 35.1
language recognized by a machine, L(M) — 35.2
Laplace model — 20.2
Laplace smoothing — 21.5
Las Vegas algorithm — 21.6
last digit (via mod 10) — 23.2
law of large numbers — 20.6
law of the excluded middle — 1.4, 5.1
law of total probability — 21.3, 21.4
laws of logic (catalog) — 1.4
lcm (least common multiple) — 22.6
leading term dominates (theorem) — 14.3
leaf — 31.1, 31.2
leaf (pendant vertex) — 27.2
leaf cost (n^{log_b a}) — §19.3, §19.2
leaf existence lemma — 31.1
least element — 7.2
leaves vs. internal nodes — 7.5
left child / right child — 31.3
lemma — 4.1, 4.2
length (of a list) — 7.5
length (of a walk/path) — 27.2
length of a string — 35.1
level-order traversal — 31.3
lexer vs. parser (compiler phases) — 35.6
liar paradox — 1.2
LIFO stack (in DFS) — 28.3
light edge — 32.5
like quantifiers commute — 2.3
likelihood — 21.3
linear code — 38.5
linear combination (divisibility) — 22.1, 22.4
linear congruence — 23.3
linear extension — 28.5 (cross-ref Ch.13)
linear homogeneous recurrence — 18.3
linear programming (LP) — 40.1
linear recurrence — 18.3
linear time — 14.5
linear-bounded automaton — 35.6
linearithmic time (n log n) — 14.5
linearity of expectation — 20.4, 40.3 [Ch. 20]
linearity of summation — 11.2
linearly dependent columns (and d_min) — 38.5
list (recursive definition) — 7.5
load balancing (pigeonhole bound) — 17.2
load factor (α) — 26.2
local search / local optimum — 30.6
log-probabilities (underflow) — 21.5
logarithm function — 9.5
logarithmic time — 14.5
logic programming (Prolog) — 3.6
logical equivalence — 1.4
loop (self-loop) — 27.1
loop invariant — 6.5, 40.5 [Ch. 6]
lower bound (asymptotic) — 14.3, 14.6
lower bound (problem) — 14.6
lower limit / upper limit — 11.2
LP duality — 40.1

M

machine-checkable proof — 3.5
maintenance (loop) — 6.5
making change (generating function) — 17.5
many-one (Karp) reduction — 37.4
map fusion — 40.4
Master Theorem — §19.3
Master Theorem, Case 1 (leaves win) — §19.3
Master Theorem, Case 2 (tie) — §19.3
Master Theorem, Case 3 (root wins) — §19.3
matched / unmatched vertex — 34.5
matching — 34.5
matching (vs. counting) — 10.1
matching-to-max-flow reduction — 34.5
mathematical induction — 6.1, 6.2, 6.3
matrix exponentiation — §19.5
max flow (maximum flow) — 34.2
max-flow min-cut as LP duality — 40.1 [first-defined Ch. 34]
max-flow min-cut theorem — 34.4, 40.1 [first-defined Ch. 34]
maximally acyclic — 31.1
maximum distance separable (MDS) — 38.6
maximum edges, C(n,2) — 27.1
maximum flow — 40.1 [Ch. 34]
maximum matching — 34.5
maximum-flow problem — 34.2
mean (of a random variable) — 20.4
membership relation ($\in$) — 8.1
memoization — §19.5
merge (procedure) — §19.4
merge sort — §19.1, §19.4, §19.2
method of undetermined coefficients — 18.5
metric TSP — 30.6
Millennium Prize Problem — 30.4
Millennium Prize Problems — 37.6
min cut (minimum s–t cut) — 34.4
min-cut segmentation — 34.6
min-heap / max-heap — 31.5
minimally connected — 31.1
minimax path property — 32.6
minimum distance — 38.2
minimum distance equals minimum weight (Theorem 38.4) — 38.5
minimum spanning forest — 32.6
minimum spanning tree (MST) — 32.2, 32.3, 32.4, 32.5, 32.6, 40.1 [Ch. 32]
mod as a function — 9.5
mod operator vs. congruence relation — 23.1, 23.2
model-independence of polynomial time — 37.1
modeling with graphs — 27.6
modeling with recurrences — 18.2
modular arithmetic rules — 23.2
modular exponentiation — 23.5
modular hash — 26.1, 26.3
modular inverse — 23.3
modular inverse (used in keygen) — 24.2, Project Checkpoint [first-defined Ch. 23]
modular inverse (via Bézout, preview) — 22.5
modulus — 23.1
modulus $n = pq$ (RSA) — 25.4
modus ponens — 3.2
modus tollens — 3.2
monad (mention) — 40.4
monochromatic triangle — 40.3
monotonicity (probability) — 20.2
Monte Carlo algorithm — 21.6
Monte-Carlo simulation — 20.6
MST problem (statement) — 32.2
MST vs. shortest-path tree — 32.6
MST, uniqueness (distinct weights) — 32.2, 32.4
multigraph — 27.1, 30.1
multiple — 22.1
multiple edges — 30.1
multiplication rule (probability) — 21.1, 21.3
multiplicative function (totient) — 23.6
multiplicity (of a root) — 18.4
multiset — 17.3
multiset permutation — 16.1
mutual inclusion (double containment) — 8.2, 8.5
mutual independence — 21.2
mutually exclusive cases — 15.3
mutually exclusive events — 20.1

N

naive Bayes — 21.5
naive recursive Fibonacci (exponential) — §19.5
natural frequencies — 21.4
natural transformation (mention) — 40.4
nearest-codeword decoding (minimum-distance decoding) — 38.3
nearest-neighbor heuristic — 30.6, Project Checkpoint
negation — 1.2, 1.3
negation of a quantified implication — 2.4
negation of quantifiers (De Morgan for quantifiers) — 2.4
neighborhood, N(v) — 27.2
nested loop analysis — 11.6
nested loops, analysis of — 14.4
nested quantifier — 2.3
network design — 32.6
noisy channel — 38.1
noisy-channel coding theorem — 40.2
noisy-channel coding theorem (Shannon) — 40.2
non-constructive proof — 5.4, 40.3
non-negative integer solutions (of $x_1+\cdots+x_k=n$) — 17.3
non-negative residue convention — 23.1
non-regular language — 35.5
nondeterministic finite automaton (NFA) — 35.3
nondeterministic polynomial time — 37.2
nonhomogeneous recurrence — 18.5
nonlinear recurrence — 18.3
normalization (probability) — 20.2
NP (complexity class) — 37.3, 37.4, 37.6, Summary, 37.2
NP (verification class, informal) — 30.4, 30.5
NP-complete — 37.5, 37.6, 37.4, Summary
NP-complete zoo — 37.5
NP-hard — 37.5, 37.4, Summary
NP-hard (preview) — 30.5, 30.4, Summary
NP-hard / NP-complete / SAT — 37], 40.1, 40.5 [Ch. 30

O

object (category theory) — 40.4
odd (definition) — 4.2
odd-degree vertex (as obstruction) — 30.1, 30.2
odd-degree-vertex corollary — 27.4
off-by-one (indexing) — 11.1
one-way function — 25.3
one-way function (intro) — 9.6
open-padlock analogy — 25.3
operation counting — 14.2
operator precedence (logic) — 1.2
optimal algorithm — 14.6
optimality certificate — 40.1
optimality certificate (flow) — 34.4
optimization problem (vs. decision) — 37.1, 37.6
order (of a recurrence) — 18.1, 18.3
order of a group — 24.2
order of an element — 24.3
order of quantifiers — 2.3
ordered pair — 8.4
ordered pair (used; defined Ch. 8) — 12.1, 27.1, 27.3
ordered selection without repetition — 15.2, 15.6
outcome — 20.1
over-counting — 15.5

P

P (complexity class) — 37.3, 37.4, 37.6, Summary, 37.2
P versus NP problem — 37.6
P vs. NP (preview) — 1.6
P vs. NP problem — 30.4, What's Next
P ⊆ NP (containment) — 37.2, 37.3
P(n, k) (introduced via product rule) — 15.2, 15.6
padding (OAEP, mention) — 25.6
pairwise coprime moduli — 23.4
pairwise independence — 21.2
pairwise keys, $\binom{n}{2}$ (scaling) — 25.2, Summary
parallel edges — 27.1
parent / child — 31.2
parity argument — 5.3, 30.1, 30.2
parity bit — 26.4
parity-check matrix — 38.5
parity-check position — 38.4
partial fractions (in telescoping) — 11.4
particular solution — 18.5
partition — 12.4
party problem — 40.3
Pascal's rule — 16.4
Pascal's triangle — 16.4
password counting — 15.1, 15.2, 15.6
path — 27.2
path compression — 32.3
path reconstruction — 28.2
peel off the structure (setup move) — 18.2
perfect matching — 34.5
permutation — 16.1, 16.3
permutation, with repeated objects (multiset) — 16.1
permutations vs. combinations — 16.3
pigeonhole principle — 40.3 [Ch. 17], 17.1
pigeonhole principle (applied to hashing) — 26.2
pigeonhole principle (preview) — 9.3
pigeonhole principle, as non-injective function — 17.1
pivot (randomized) — 21.6
pivotal consequence (one NP-complete in P ⇒ P = NP) — 37.4, 37.6
plaintext — 25.1
points in a unit square (pigeonhole) — 17.2
polynomial hash (string hashing) — 26.1
polynomial over Z_2 — 26.5
polynomial root bound (over a field) — 38.6
polynomial time — 14.5, 30.4
polynomial time (as the efficiency boundary) — 37.1, 37.2, 37.6
polynomial-time reduction (≤_p) — 37.5, 37.4
positive integer solutions (non-empty boxes) — 17.3
Post Correspondence Problem — 36.5
post-order (DFS) — 28.5
post-quantum cryptography / lattices (mention) — 40.5
postcondition — 2.6
posterior — 21.3
postorder traversal — 31.3
power set — 8.2
power set, cardinality of (Cantor's theorem) — 10.4, 10.5
powers of two (sum) — 11.3
pre-order (DFS) — 28.3
precondition — 2.6
predecessor / parent map — 28.2
predicate — 2.1, 2.2
prefix code — 31.6
prefix-code cost — 31.6
preimage / inverse image (of a set) — 9.2
preimage resistance — 26.6
premise — 3.1
preorder traversal — 31.3
Prim's algorithm — 32.4
primal (linear program) — 40.1
prime — 22.2
prime divisor (existence) — 22.2
prime factorization — 22.6
prime fingerprint — 22.6
prime modulus (in hashing) — 26.3
prime number (used) — 5.1
primitive element — 24.5
primitive operation — 14.2
primitive root mod p — 24.3
principle of mathematical induction — 6.2
prior — 21.3
priority queue, in Prim — 32.4
private exponent $d$ — 25.4
private key — 25.3, 25.4
probabilistic method — 20.6, 40.3 [Ch. 20]
probabilistic method (revisited) — 40.3
probability axioms (Kolmogorov) — 20.2
probability function — 20.2
product notation — 11.5
product rule — 15.2, 15.6
program equivalence (undecidability) — 36.5
programs, countability of — 10.4
projection (relational) — 12.6
proof (what it is) — 4.1
proof assistant — 36.6
proof by cases — 5.3, 5.6
proof by contradiction — 5.1, 5.2, 5.6
proof by contraposition — 4.4
proof by example (fallacy) — 4.5
proof template (universal) — 4.5
proper subset — 8.2
proper subset, equinumerous with whole — 10.1
proposition — 1.2
proposition vs. predicate — 2.1
propositional variable — 1.2
prosecutor's fallacy — 21.4
public exponent $e$ — 25.4
public key — 25.3, 25.4
public-key cryptography (asymmetric cryptography) — 25.3
pumping (a string) — 35.5
pumping lemma (for regular languages) — 35.5
pumping length — 35.5
pure function — 9.6
pushdown automaton — 35.6

Q

QED ($\blacksquare$) — 4.1
quadratic time — 14.5
quantifier — 2.2
quantifier game (move order) — 2.3
quotient — 22.3

R

r-combination — 16.2
r-permutation — 16.1
RAM model — 14.2
Ramsey number — 40.3
Ramsey theory — 40.3
Ramsey's theorem (R(3,3) ≤ 6) — 40.3
random variable — 20.3
randomized algorithm — 21.6
randomized quicksort — 21.6
range — 9.2
rationals, countability of — 10.2
reachability — 12.5
read/write head — 36.1
reading proofs critically — 4.6
real numbers, uncountability of — 10.3
recognition problem — 35.1
recognizable (recursively enumerable / semi-decidable) — 36.3
recognizer — 36.3
recurrence (of a sequence) — 11.1
recurrence relation — 18.1
recursion tree — §19.2
recursion, relation to induction — 6.1, 6.4
recursion-tree method — §19.2
recursive clause — 7.3, 7.4
recursive definition — 7.3
recursive definition (as recurrence) — 18.1
recursive traversal — 28.3
recursively defined set — 7.3
recursively enumerable language — 35.6
reduce early reduce often — 23.2
reductio ad absurdum — 5.1
reduction ($A \le B$) — 36.5
Reed-Solomon code — 38.6
Reed-Solomon codes — 24.5, 24.6
Reed–Solomon codes — 40.2 [Ch. 38, mentioned Ch. 24]
referential transparency — 9.6
reflexive — 12.3
reflexive closure — 12.5
regular expression — 35.4
regular language — 35.4
regularity condition — §19.6, §19.3
relation (binary) — 12.1
relation digraph (directed-graph view) — 12.2
relation matrix / adjacency matrix — 12.2
relation on a set — 12.1
relational model — 12.6
remainder — 22.3
repeated root (case) — 18.4
repeated squaring — 23.5
repetition code — 38.2, 38.3
representation (graph), space–time tradeoff — 28.1, 28.6
representative (of a class) — 12.4
residual capacity — 34.3
residual network — 34.3
residue — 23.1
residue class — 23.1
resolution — 3.2
restricted quantifier (forall with →, exists with ∧) — 2.2
Reverse Polish Notation (RPN) — 31.5
reverse-delete algorithm — 32.5
Rice's theorem — 36.5
ring — 24.4
ring / shell (BFS exploration) — 28.2
Rivest–Shamir–Adleman — 25.4
road network graph — 27.6
root — 31.2
rooted tree — 31.2
roster notation — 8.1
RSA — 25.4
RSA (correctness via group order) — 24.3, 24.6, Project Checkpoint [implemented Ch. 25]
RSA / factoring assumption — 25.6
RSA / factoring hardness — 40.5 [Ch. 25]
RSA correctness (via Euler) — 23.6
RSA correctness theorem — 25.5
RSA decryption ($m \equiv c^d \bmod n$) — 25.4
RSA encryption ($c \equiv m^e \bmod n$) — 25.4
RSA security — 25.6
rsa_keygen (dmtoolkit crypto.py) — Project Checkpoint
running time as a summation — 11.6

S

same cardinality — 10.1
sample space — 20.1
SAT (Boolean satisfiability problem) — 37.5, 37.6, 37.4
SAT solvers (industrial) — 37.6
satisfiability (SAT) — 1.6
satisfiability (verifying, verify_sat) — 37.3
satisfying assignment — 1.6
saturated edge — 34.1
search space, sizing — 16.6
SECDED (single-error-correct, double-error-detect) — 38.3, 38.4
second-preimage resistance — 26.6
security through obscurity — 25.1
selection (relational) — 12.6
selection with constraints (subtraction / cases) — 16.2
self-balancing tree (AVL, red-black) — 31.4
self-information — 40.2
self-loop — 12.2
self-reference — 5.2
self-reference / running a program on itself — 36.4
sensitivity (true-positive rate) — 21.4
sequence — 11.1
series — 11.2
set — 8.1
set difference — 8.3
set equality — 8.2
set identity — 8.5
set in Python — 8.6
set-builder notation — 8.1
shadow price — 40.1
Shannon entropy — 40.2
shared-modulus attack — 25.6
shift cipher — 25.1
Shor's algorithm (mention) — 40.5
Shor's algorithm / post-quantum (mention) — 25.6
short-circuit evaluation — 1.5
short-circuit evaluation (quantifier early exit) — 2.5
shortest path (unweighted) — 28.2
shrink factor (b) — §19.1
Sieve of Eratosthenes — 22.2
sign with $d$, verify with $e$ — 25.6
simple graph — 27.1
simplex algorithm — 40.1
simplification (rule of inference) — 3.2
single-linkage clustering — 32.6
Singleton bound — 38.6
sink (vertex) — 34.1
six degrees of separation — 28.2
small-exponent attack ($e=3$, cube root) — 25.6
smallest counterexample (proof pattern) — 7.2
SMT solver — 3.6
social network graph — 27.6
solution (of a recurrence) — 18.1
solvability of linear congruences — 23.3
solve_linear (Toolkit) — Project Checkpoint
sound argument — 3.1
sound vs. complete (program analysis) — 36.6
soundness — 3.1
source (vertex) — 34.1
source-coding theorem — 40.2
source-coding theorem (Shannon) — 40.2
spanning tree — 32.1, 28.4 (intro)
spanning tree, edge count ($n-1$) — 32.1
spanning tree, number of (counting) — 32.1
sparse graph — 28.1, 28.6
specification (program contract) — 2.6
spectral graph theory / PageRank / graph neural networks (mention) — 40.5
splitting the range — 11.2
square root of 2, irrationality of — 5.1
square-and-multiply — 23.5
standard deviation — 20.5
stars and bars — 17.3
start state — 35.2
state (of an automaton) — 35.2
state space (counting) — 15.1, 15.6
state-elimination method (mentioned) — 35.4
Stirling numbers of the second kind (mention) — 17.6
string / word — 35.1
strong duality — 34.4
strong duality theorem — 40.1
Strong Duality Theorem (LP) — 40.1
strong induction — 7.1, 7.6
strong inductive hypothesis — 7.1
structural induction — 7.4, 7.5
structural inductive hypothesis — 7.4
subgroup — 24.2
subset — 8.2
subset construction — 35.3
subset enumeration (2^n) — 16.6
SUBSET SUM — 37.5
subset-sum (search space) — 16.6
substitution cipher — 25.1
substitution method — §19.6
subtraction principle (complement counting) — 15.6
subtractive recurrence — §19.6
subtree — 31.2
sufficient condition (vs. characterization) — 30.3
sum of binomial coefficients (= 2^n) — 16.4, 16.5
sum of cubes — 11.4
sum of squares — 11.4
sum rule — 15.3
sum rule (asymptotic) — 14.4
summation — 11.2
summation, proof by induction — 6.3
Sun Tzu's puzzle — 23.4
superposition (of solutions) — 18.3, 18.4
surjection counting (onto functions) — 17.6
surjective / surjection / onto — 9.3
symbol (vs. bit) — 38.6
symmetric — 12.3
symmetric closure — 12.5
symmetric difference — 8.3, 8.6
symmetric matrix (undirected graph) — 28.1
symmetric-key cryptography — 25.2
symmetry identity (binomial) — 16.2, 16.5
syndrome — 38.4, 38.5
syndrome (error position) — Project Checkpoint
syndrome decoding — 38.4
syntactic consequence — 3.5
s–t cut — 34.4

T

table index (slot) — 26.1
tail / head (of an arc) — 27.3
tape (unbounded) — 36.1
tautology — 1.4
telescoping — 11.4
telescoping sum — 11.4
term (of a sequence) — 11.1
termination (Euclidean algorithm) — 22.4
termination (loop) — 6.5
test coverage (counting) — 15.1, 15.6
testing fallacy (tests-passed) — 3.3
textbook RSA (insecurity of) — 25.6
theorem — 4.1
Theta(V+E) bound — 28.6
Thompson's construction — 35.4
tight bound — 14.3
tiling recurrence — 18.2
time recurrence (algorithm cost) — 18.6
topological sort (via DFS) — 28.5 (defined in Ch.13; re-derived here)
total transition function — 35.2
total_probability (toolkit function) — Project Checkpoint
totality (of a function) — 9.1
totient — 23.6
totient $\phi(n) = (p-1)(q-1)$ (RSA use) — 25.4
tour count $(n-1)!/2$ — 30.5, key-takeaways
Tower of Hanoi — 18.2, 18.5
trace (of a computation) — 35.2
tractable / intractable — 30.4, Summary
tractable vs. intractable — 14.5
trail (walk with no repeated edge) — 30.2
transition function ($\delta$) — 36.1
transition function (δ) — 35.2
transitive — 12.3
transitive closure — 12.5
transitivity of divisibility — 4.2, 22.1
transitivity of reductions — 37.4
transposition error — 26.4
trapdoor function — 23.6, 25.3
Traveling Salesman Problem (TSP) — 30.6, 40.1 [Ch. 30], 30.5, Summary
traversal — 31.3
tree — 31.1
tree edge — 28.4
tree edge count (n-1 edges) — 31.1
tree reconstruction (preorder + inorder) — 31.3
tree_height (toolkit) — Project Checkpoint
trial division (factoring) — 22.6
triangle inequality (Hamming) — 38.2
triangle inequality (metric TSP) — 30.6
triangle inequality (special case) — 5.3
trie — 31.5
trivial proof — 4.5
trivial subgroup — 24.2
truncation vs. floor — 9.5
truth table — 1.3
truth value — 1.2
truth_table (Toolkit) — Project Checkpoint
TSP (decision form, NP-completeness) — 37.1, 37.5, 37.6
TSP 2-approximation (via MST) — 32.6
Turing complete — 36.6, 36.2
Turing machine — 36.2, 36.3, 36.4, 36.6, 36.1
Turing's theorem (halting undecidable) — 36.4
turnstile ($\vdash$) — 3.5
two-coloring (monochromatic block) — 20.6
type inference — 3.6
type signature (as domain/codomain) — 9.6

U

uncomputable problem — 10.4
uncountable — 10.3
undecidable — 36.4, 36.5, 36.3
union — 8.3
union / alternation (regex) — 35.4
union bound — 20.2, 20.6
union bound (in the probabilistic method) — 20.6
union by rank — 32.3
union operation (union-find) — 32.3
union-find (disjoint-set) — 32.3
unique factorization — 22.6
unique path property — 31.1
uniqueness of identity and inverses (Theorem 24.1) — 24.2
uniqueness proof — 5.4
uniqueness quantifier ($\exists!$) — 2.2
unit (modulo n) — 23.3, 23.6
units modulo n (count by totient) — 23.6
universal family of hash functions — 26.3
universal generalization (UG) — 3.4
universal hashing — 26.3
universal instantiation (UI) — 3.4
universal quantifier — 2.2
universe (universal set) — 8.3
unordered pair (used; defined Ch. 8) — 27.1
unpack/repackage habit — 4.2, 4.3
unsatisfiable — 1.6
unsolvability (preview) — 5.2
upper bound (asymptotic) — 14.3

V

vacuous proof — 4.5
vacuous truth (empty domain) — 2.5
vacuous truth (empty set is a subset) — 8.2
vacuously true — 1.2
valid argument — 3.1
validity — 3.1
value of a flow — 34.1
variable-length code — 31.6
variance — 20.5
Venn diagram — 8.3
verification vs. solution (the verify/find gap) — 37.6, 37.3
verifier — 37.3, 37.2, Project Checkpoint
verify vs. find (asymmetry) — 30.4, 30.5
verify_hamilton_circuit (Toolkit) — Project Checkpoint
vertex (node) — 27.1
VERTEX COVER — 37.5

W

walk — 27.2
Warshall's algorithm (mentioned) — 12.5
watchdog timer / resource bound — 36.6
weak duality — 40.1
weak duality (flow/cut) — 34.4
Weak Duality (worked LP) — 40.1
web graph — 27.6
weight (of a string) — 38.2
weight function w — 27.3
weight of a spanning tree — 32.2
weighted checksum — 26.4
weighted graph — 27.3
well-defined / single-valued — 9.1
well-ordering principle — 7.2, 7.6
well-ordering principle (preview) — 6.2
without loss of generality (WLOG) — 5.3, 40.3 [Ch. 5]
witnesses (c and n_0) — 14.3
worst case — 14.6

Z

Z_n (integers mod n) — 23.1
zero divisor — 24.4
zero divisor (why RS needs a field) — 38.6
zero-frequency problem — 21.5
zero-knowledge proofs / PCP (mention) — 40.5
zig-zag enumeration — 10.2

Ε

ε-closure — 35.3
ε-transition — 35.3