Concrete Mathematics — the companion volume
Why Concrete Mathematics (Graham, Knuth & Patashnik) is the one extra book to read for a full Knuth experience, and how it maps onto this course.
If TAOCP has a sibling, this is it. Module 02 of this course teaches Vol. 1 §1.2, "Mathematical Preliminaries" — and Concrete Mathematics (CM) is that section, grown into a full 650-page course. Where TAOCP compresses the mathematics into a dense dozen pages you're expected to already know, CM unfolds it patiently, with motivation, history, and (famously) margin graffiti from the students who first took the class. You do not need it to complete this course — every lesson is self-contained — but reading it is the surest way to acquire the mathematical maturity the analysis of algorithms quietly assumes.
What it is
Concrete Mathematics: A Foundation for Computer Science grew out of a Stanford course Knuth began in 1970, itself an expansion of §1.2. Ron Graham, Don Knuth, and Oren Patashnik wrote it up in 1988 (2nd ed. 1994, Addison-Wesley).
The title is a pun on two levels. "Concrete" is CONtinuous + disCRETE — the book's method is to bring the tools of continuous mathematics (sums, calculus-like manipulation) to bear on discrete problems. And "concrete" stands against "abstract": this is mathematics you compute with, drilled through hundreds of problems, not admired from a distance. That is exactly the stance this course takes toward algorithms.
Why it earns a place next to TAOCP
- It's the prerequisite TAOCP doesn't stop to teach. Knuth's analyses lean on summation manipulation, recurrences, generating functions, and asymptotics as though they were arithmetic. CM is where you actually learn them.
- It teaches a method, not just facts. The "repertoire method" for solving recurrences, the perturbation method for sums, the mechanics of generating functions — these are reusable engines. You'll recognize them powering the average-case analyses in Modules 06 and 07.
- It's where the notation comes from. The Iverson bracket
[P], floor and ceiling, falling/rising factorialsx^{\underline{n}}/x^{\overline{n}}, and the readable Stirling-number notation you meet in for-newcomers.md §7 were all standardized or popularized here, and TAOCP uses them throughout. - It's a genuinely enjoyable read — the margin notes, the running jokes, the problems rated in the same 00–50 scale TAOCP uses. It rewards a notebook.
How it maps onto this course
CM's nine chapters line up with the mathematics you build and use here:
| CM chapter | What it covers | Where it powers this course |
|---|---|---|
| 1 · Recurrent Problems | The Tower of Hanoi, Josephus, the repertoire method | The invariant + recurrence habit from Module 01 onward |
| 2 · Sums | Summation notation, the perturbation method, finite calculus | Module 02 (closed-form sums); analyses in Modules 06–07 |
| 3 · Integer Functions | Floor, ceiling, mod, the ⌊lg n⌋+1 style of bound | Module 07 (binary search bound); Module 20 (decision-tree lower bound) |
| 4 · Number Theory | Divisibility, gcd, modular arithmetic, primes | Module 01 (Euclid), Module 05 (binary gcd, Miller–Rabin), Module 04/12 (LCG theory) |
| 5 · Binomial Coefficients | Identities, the multiplicative method, Pascal's rule | Module 02 (binomials); combinatorics in Module 08 |
| 6 · Special Numbers | Harmonic, Fibonacci, Stirling, Bernoulli, Eulerian | Module 02 (harmonic H_n, Fibonacci); Stirling/Eulerian behind sorting analyses |
| 7 · Generating Functions | The algebra of sequences; solving recurrences cold | The machinery behind Fibonacci identities and average-case results |
| 8 · Discrete Probability | Expectation, variance, the analysis of randomized methods | Module 04 (shuffling, chi-square), average-case analyses everywhere |
| 9 · Asymptotics | O-notation done rigorously, Euler–Maclaurin, sums→integrals | Module 02 (O-notation) and every growth-curve claim ./grade bench checks |
A practical reading path: read CM Chapter 2 alongside Module 02, then dip into Chapter 4 before Module 05, Chapter 8 before Module 04, and Chapter 9 whenever a lesson waves at an asymptotic estimate you'd like to see derived in full.
Getting it / using it
- Concrete Mathematics, 2nd ed. (Graham, Knuth, Patashnik), Addison-Wesley, 1994. Widely available; the errata live on Knuth's site.
- Read it the way you study this course: with pen and paper. Do the warmup exercises (rating ≤ 15) — they're short and they're where the methods stick.
- Treat it as a reference, too. When a lesson here cites "the perturbation method (§1.2.3)" or a harmonic-number asymptotic, CM is where the full treatment lives.
New to all this? Start with For newcomers. Want the map of the course itself? See the Syllabus. For how the section numbers like §1.2.3 point into the physical books, see For newcomers §8.