Chapter 26
Parallel Algorithms
Fork-join exposes independent tasks; work T₁ counts all operations, while span T∞ is the longest dependency chain. Parallelism is T₁/T∞. These visual traces simulate parallel schedules; JavaScript executes them sequentially.
Ready · merge sort splits independent subarrays, then joins them.
Merge sort has Θ(n log n) work and Θ(log² n) span with a linear-work parallel merge; ideal parallelism is Θ(n/log n). Matrix multiplication uses independent output cells: Θ(n³) work and Θ(log n) span with enough processors and a balanced reduction.
Chapter 27
Online Algorithms
Decisions must be made before future requests are known. Compare strategies by their cost against an offline optimum.
Ready · choose a scenario.
The elevator demo immediately follows each newly revealed request; it is a deliberately simple online policy, not an optimality claim. Move-to-front and LRU costs depend on the request sequence.
Chapter 28
Matrix Operations
Elimination solves Ax=b; Gauss–Jordan can form A⁻¹; positive-definite structure enables Cholesky factorization and least-squares solutions.
Ready · examples use small, well-conditioned matrices.
Dense Gaussian elimination costs Θ(n³) arithmetic operations. Cholesky A=LLᵀ applies when A is symmetric positive definite; least squares solves (XᵀX)β=Xᵀy here to illustrate the normal equations (QR is generally more numerically stable).
Chapter 29
Linear Programming
Optimize a linear objective subject to linear inequalities. In two dimensions, a bounded optimum occurs at a feasible vertex.
Example: maximize 3x + 2y, with x+y ≤ 4, x ≤ 2, y ≤ 3, x,y ≥ 0.
Formulations model decisions and constraints. Duality pairs bounds for primal/dual objectives; under standard feasibility and boundedness conditions, strong duality equates their optimal values.
Chapter 30
Polynomials and the FFT
The discrete Fourier transform evaluates a polynomial at roots of unity. Divide-and-conquer symmetry computes the same transform in O(n log n).
Example polynomial coefficients: [1, 2, 0, 1] (zero-padded to length 4).
FFT circuits implement butterfly stages; inverse FFT changes the sign of the roots and scales by 1/n. Coefficients here are real; the transform generally has complex values.
Chapter 31
Number-Theoretic Algorithms
GCD, modular arithmetic, inverses, and the Chinese remainder theorem are core tools. RSA illustrates how arithmetic supports public-key cryptography.
Ready · cryptography example uses tiny insecure teaching values only.
RSA is for concepts only: tiny keys are trivially breakable. Real systems require vetted cryptographic libraries, secure padding, and appropriately sized keys. The primality demo uses deterministic trial division, not a production-scale primality test.
Chapter 32
String Matching
Find a pattern in text. Naive matching retries each position; Rabin–Karp filters by rolling hash; KMP uses the prefix function to avoid rechecking matched characters.
Text: ABABDABACDABABCABAB · Pattern: ABAB
Naive: O(nm) worst case. Rabin–Karp: expected O(n+m) with verification after hash matches, O(nm) worst case. KMP: O(n+m). Suffix arrays sort suffix starts and support repeated-query indexing.
Chapter 33
Machine-Learning Algorithms
Clustering groups data without labels; multiplicative weights adapts among experts; gradient descent follows the negative gradient to reduce an objective.
Ready · small deterministic examples for clarity.
K-means can converge to a local optimum and depends on initialization. Multiplicative weights is a general online-learning update. Gradient descent convergence depends on the objective, step size, and initialization.