Appendix A
Summations
Summations combine per-step costs. Closed forms simplify exact totals; comparison bounds expose asymptotic growth.
Σᵢ₌₁ⁿ i = n(n+1)/2
Arithmetic growth: Θ(n²).
Σᵢ₌₀ⁿ⁻¹ rⁱ = (rⁿ−1)/(r−1)
For r>1, dominated by the largest term: Θ(rⁿ).
Hₙ = Σ 1/i
Integral bounds give ln(n+1) ≤ Hₙ ≤ 1+ln n, hence Θ(log n).
A summation property such as linearity lets us split sums: Σ(aᵢ+bᵢ)=Σaᵢ+Σbᵢ. For bounds, compare each term or area under the curve to an integral.
Appendix B
Sets, Relations, Functions, Graphs & Trees
These definitions describe the objects algorithms manipulate and the guarantees those objects satisfy.
B.1 Sets
Membership, subsets, union, intersection, and difference.
B.2 Relations
A relation on S is a subset of S×S; test reflexivity, symmetry, antisymmetry, and transitivity.
B.3 Functions
A function maps each domain element to exactly one codomain element; injective and surjective are distinct properties.
B.4 Graphs
Vertices joined by edges; directed or undirected, weighted or unweighted.
B.5 Trees
A connected, acyclic undirected graph. A tree with n vertices has exactly n−1 edges; between any two vertices there is a unique simple path.
Appendix C
Counting & Probability
Counting measures outcome spaces; probability assigns mass to events; random variables turn outcomes into numbers.
C.1 Counting
Product rule: sequential independent choices multiply. For k-subsets of n items: C(n,k)=n!/(k!(n−k)!).
C.2–C.3 Probability
For finite equally likely outcomes, P(A)=|A|/|Ω|. Expectation is linear: E[X+Y]=E[X]+E[Y], even without independence.
C.4 Distributions
Binomial counts successes in n independent Bernoulli trials. Geometric counts trials until the first success.
C.5 Tail bounds
Concentration bounds show large deviations are unlikely; Chernoff bounds apply to sums of independent indicator variables.
Appendix D
Matrices
Matrices represent linear transformations and compactly encode systems, graphs, and dynamic programs.
D.1 Operations
Addition is entrywise; multiplication uses row-by-column dot products; transpose swaps row and column indices.
D.2 Properties
Multiplication is associative and distributive, but generally not commutative: AB≠BA. The identity I satisfies AI=IA=A.