Bibliography

Sources are grouped by confidence tier, following the book's citation-honesty policy (see any chapter's further-reading, or _style-bible.md). Tier 1 are works we are confident exist; Tier 2 are real ideas whose exact publication we have not pinned down; Tier 3 are constructed teaching examples, labeled where they appear.

Tier 1 — Verified canonical sources

Aaronson, "P =? NP," in Open Problems in Mathematics (eds. Nash & Rassias), Springer, 2016. Also freely available on the author's website. (Source of the chapter epigraph; the major modern survey.)
Abelson & Sussman, Structure and Interpretation of Computer Programs, §1.2.
Alon, N. & Spencer, J. H., The Probabilistic Method, 4th ed., Wiley, 2016 (canonical text on the probabilistic method).
Arora & Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. (Graduate-level; co-NP, polynomial hierarchy, PSPACE, proof barriers — the Deep Dive material.)
Benjamin, Arthur T., and Jennifer J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America (Dolciani Mathematical Expositions #27), 2003 (the standard book on double-counting/bijective proofs — the §16.5 technique; proves hockey-stick and Vandermonde, our Part C exercises). NOT YET in references.bib.
Biere, Heule, van Maaren & Walsh (eds.), Handbook of Satisfiability, 2nd ed., IOS Press, 2021. (Industrial CDCL SAT solvers; why worst-case hardness and practical solvability coexist — §37.6.)
Clay Mathematics Institute, "P vs NP Problem," official Millennium Prize Problem statement (with Stephen Cook's official problem description), claymath.org. Freely available.
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R. & Schrijver, A., Combinatorial Optimization, Wiley, 1998 (standard combinatorial-optimization text).
Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms, 4th ed. (Boolean reasoning inside algorithms and correctness). [clrs2022]
Cover, T. M. & Thomas, J. A., Elements of Information Theory, 2nd ed., Wiley, 2006 (standard information-theory text; entropy, capacity).
Davis (ed.), The Undecidable (Raven Press / Dover) — collected foundational papers of Turing, Church, Gödel, Post, Kleene. Real, canonical anthology.
Diffie, W. & Hellman, M. E., "New Directions in Cryptography," IEEE Transactions on Information Theory, vol. IT-22, no. 6, pp. 644–654 (1976). The founding public-key paper; the chapter epigraph and the §25.2 key-distribution / §25.3 trapdoor ideas originate here. Cited in further-reading and as the Case Study 2 epigraph (same epigraph the chapter body uses).
Enderton, Elements of Set Theory (Academic Press; Zermelo–Fraenkel axiomatics). (Not in references.bib; canonical text.)
Epp, Discrete Mathematics with Applications, 5th ed., Ch. 2 (translation; converse/contrapositive; "only if"/"unless"/necessary-sufficient phrasings). [epp2019discrete]
Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. (The classic NP-completeness field guide; the encyclopedic "zoo" and reduction technique.)
Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed. (style of manipulating formal expressions by rule). [concrete1994]
Halmos, Naive Set Theory (Springer; classic axiomatic introduction, Russell's paradox). (Not in references.bib; widely available canonical text.)
Hodges, Alan Turing: The Enigma (biography; source of the chapter epigraph "It is difficult today to imagine how revolutionary Turing's ideas seemed at the time"). Real, canonical.
Katz & Lindell, Introduction to Modern Cryptography, 3rd ed. (security definitions; brute-force / exhaustive search — the formal backing for §15.6 keyspace argument). [katzlindell2020]
Knuth, The Art of Computer Programming, Vol. 1, §1.3 (Boolean basics); Vol. 4A (Boolean functions, functional completeness, the $2^{2^n}$ count). [knuth1997taocp1] (Vol. 1 in references.bib; Vol. 4A cited by title only.)
Knuth, The Art of Computer Programming, Vol. 2 (arithmetic / polynomials) and Vol. 3 (hashing) — reference for hash distribution and modular/polynomial arithmetic. [knuth1997taocp1] (Vol. 1 entry in references.bib; Vols. 2–3 are the same canonical series.)
Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. (equivalence relations and partitioning / union-find — Case Study 2's deduplicator). [knuth1997taocp1]
Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.5.2–4.5.3 (Euclidean algorithm and its analysis). NOTE: references.bib currently has Knuth Vol. 1 [knuth1997taocp1]; this citation is to Vol. 2, a distinct (also canonical, verifiable) volume — flag for orchestrator to add a Vol. 2 entry if this source is kept in the assembled bibliography.
Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, §7.2.1.2–§7.2.1.3 (generating all permutations and all combinations; the lexicographic next-permutation / next-combination algorithms built in case-study-02). NOT YET in references.bib.
Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), propositions chapter (logic + verification + digital logic framing). [lehman2018mcs]
Levin, Discrete Mathematics: An Open Introduction, 3rd ed., logic chapter (freely available). [levin2019discrete]
MacKay, D. J. C., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (freely available author PDF; readable info theory + coding).
MacWilliams & Sloane, The Theory of Error-Correcting Codes (North-Holland) — the classic comprehensive coding-theory monograph (linear codes, Hamming and Reed–Solomon families, Singleton bound). Title/authors verified; no specific page/edition claimed.
Milewski, B., Category Theory for Programmers, 2019 (freely available online/PDF; functors, monads for programmers).
Pierce, B. C., Types and Programming Languages, MIT Press, 2002 (standard PL-theory text).
Python Software Foundation, "Set Types — set, frozenset," Python Language Reference / Library docs. Free online; authoritative reference for set/frozenset semantics and operators.
Python Software Foundation, itertools module documentation (permutations, combinations, combinations_with_replacement) — the standard-library realizations of all four §16.3 cells; cited in further-reading as the production counterpart to the from-scratch generators. (Official docs; verifiable.)
Python Software Foundation, official documentation for the timeit and cProfile modules (docs.python.org). Freely available.
Rivest, R. L., Shamir, A. & Adleman, L., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120–126 (1978). The original RSA paper: key generation, the $m^{ed}\equiv m$ correctness argument, the factoring-hardness security claim, and the digital-signature application. Cited in further-reading.
Rosen, Discrete Mathematics and Its Applications, 8th ed., §1.1–1.3 (propositions, connectives, truth tables, logical equivalences). [rosen2019discrete]
Sedgewick & Wayne, Algorithms, 4th ed. (Addison-Wesley, 2011), §1.4 ("Analysis of Algorithms"; the doubling-ratio method). Booksite freely available at algs4.cs.princeton.edu.
Shannon, C. E., "A Mathematical Theory of Communication," Bell System Technical Journal, 27 (1948), 379–423 & 623–656 (founding paper of information theory; source of entropy & capacity).
Sipser, Introduction to the Theory of Computation, 3rd ed., NP-completeness chapter (P, NP, Cook–Levin; SAT as NP-complete). [sipser2012]
Skiena, The Algorithm Design Manual, 3rd ed. (Springer, 2020), Chapter 2 (growth-rate hierarchy and the running-time-vs-input-size table).
The On-Line Encyclopedia of Integer Sequences (OEIS), oeis.org. Freely available.
The SAT Competition, satcompetition.org. Freely available. (Annual benchmark of SAT solvers on large real-world instances.)
Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proc. London Math. Soc. (1936). The founding paper: the machine, the universal machine, and the undecidability argument. Real, canonical primary source.
Velleman, How to Prove It, 3rd ed. (logic and proof-strategy chapters). (Canonical proof-writing text; same Tier-1 treatment as Chapter 6's bib.)
West, Introduction to Graph Theory, 2nd ed. (weighted graphs, paths, cycles, trees). [west2001graph]
West, Introduction to Graph Theory, 2nd ed. — connectivity, distance, cut vertices. [west2001graph]
West, Introduction to Graph Theory, 2nd ed. — matchings and network flow (Hall, König, Berge's augmenting-path theorem; deriving König/Hall from flow). [west2001graph]
West, Introduction to Graph Theory, 2nd ed., Chapter 1 (formal graphs, degree, paths, isomorphism; handshaking lemma + corollary as theorems; §1.1 isomorphism invariants). [west2001graph]
Wilf, generatingfunctionology, 3rd ed. (A K Peters, 2006; also freely available as a PDF from the author's site). Source of the "a generating function is a clothesline on which we hang up a sequence of numbers for display" quotation used in §17.5 of the chapter body, and of the "Snake Oil method" section. Cited in further-reading.md. This is a genuinely canonical, verifiable text.
Williamson, D. P. & Shmoys, D. B., The Design of Approximation Algorithms, Cambridge University Press, 2011 (freely available author PDF; LP duality for approximation guarantees).

Tier 2 — Attributed (specifics unverified)

"All horses are the same color" — classic mathematical fallacy, attribution commonly to George Pólya.
"Anagrams collide under a sum-of-code-points hash" and polynomial string hashing h(s) = Σ ord(s_i)·31^i mod m (case study 1) — the order-insensitivity weakness and the 31-multiplier polynomial hash are standard folklore in hashing (the 31 multiplier is widely associated with Java's String.hashCode); treated properly in Chapter 26 / CLRS.
"Complete disorder is impossible" — phrase commonly attributed to Theodore Motzkin describing Ramsey theory (chapter body §40.3).
"Fibonacci numbers," OEIS sequence A000045 (oeis.org) — Online Encyclopedia of Integer Sequences entry; source of identities (e.g. fast-doubling F_{2k} = F_k(2F_{k+1}-F_k)) for the conjecture-and-test exercises. Freely available online.
"Most interaction faults are triggered by two interacting parameters" (the empirical basis for pairwise / all-pairs combinatorial testing in case-study-01) — a finding associated with the NIST combinatorial-testing line of work (e.g., D. R. Kuhn and colleagues). Attributed in general terms; no specific study's statistic is quoted, and the figures in the case study are illustrative.
"Schoolboy Gauss" attribution for the arithmetic-series folding trick — traditional anecdote; attribution commonly to Carl Friedrich Gauss.
"Six degrees of separation" — the empirical claim that random pairs in a real social graph are typically within ~6 hops, discussed in case-study-01 and the chapter. Popularly associated with Stanley Milgram's 1960s "small-world" letter-forwarding experiments; the specific six-figure is folklore widely attributed to that line of work. Attributed, not pinned to an exact publication.
"The art of counting is the art of not listing" (chapter epigraph) — a teaching maxim of combinatorics; no single attributable origin.
"The enemy knows the system" / Shannon's maxim, a restatement of Kerckhoffs's principle — commonly attributed to Claude Shannon (used as the case-study-01 epigraph). The principle is due to Auguste Kerckhoffs (1883).
3Blue1Brown (YouTube channel). Euler's-formula / planar-graph explainers. Cited in further-reading for visual intuition. Real channel; specific video not pinned. Tier 2.
Case Study 1 ("Diagnosing Register Spills"): the 8-line graphics blend routine, its live ranges, interference graph, and the embedded 3-register machine are a constructed scenario built to exhibit a size-5 clique forcing a spill. Hypothetical, labeled as a worked scenario.
Case Study 2 ("Conflict-Free Exam Scheduler"): the seven-course department, the enrollment-derived conflict pairs, and the timetable are a constructed scenario. Hypothetical, labeled as a worked scenario. (The deliberately mis-derived expected-output value in Phase 2 is an intentional "Find the Error" device, flagged in-text.)
Chaitin, Gregory J., et al. "Register Allocation via Coloring" (and related Chaitin work, ~1981–82). Cited in further-reading and underpinning Case Study 1's interference-graph model. The foundational graph-coloring register-allocation paper; real and seminal. Exact venue/year not pinned here. Tier 2.
Exercises: the access-point channel-assignment instance (33.11), the 6-course exam graph (33.27), the straight-line code fragments (33.7), and the crown-graph experiments (33.29) are constructed illustrative instances. The Petersen graph (33.8) and crown graph are standard named graphs, not fabricated.
Gonthier, Georges. "Formal Proof — The Four-Color Theorem." Notices of the American Mathematical Society, vol. 55, no. 11, 2008. (With Benjamin Werner, the 2005 Coq-verified proof.) Cited in §33.5 and further-reading. The article in the Notices is real and well known; tagged Tier 2 pending exact volume/page verification. Authorship and the 2005 Coq proof are well established.
Numberphile (YouTube channel). Four Color Theorem / map-coloring episodes. Cited in further-reading as accessible video. Real channel/content; specific episode not pinned. Tier 2.
Wilson, Robin. Four Colors Suffice: How the Map Problem Was Solved. Princeton University Press / Penguin, 2002. Cited in further-reading as the definitive popular history. Real, widely-cited book; exact edition/publisher not pinned here. Tier 2.
3Blue1Brown number-theory videos (YouTube) — free educational videos (real, freely available).
3Blue1Brown, "Bayes theorem, the geometry of changing beliefs" (YouTube). (Real video; title from memory.)
3Blue1Brown, "Binary, Hanoi, and Sierpinski" (YouTube) — free video connecting the Hanoi recurrence to binary counting and fractal structure. Cited for intuition only.
Aaronson, Quantum Computing Since Democritus (Cambridge University Press, 2013) — early chapters on sets/infinities and computation. Tier 2.
Aeschylus epigraph ("It is a profitable thing, if one is wise, to seem foolish") — commonly attributed to Aeschylus; used illustratively for the cautious-engineer framing.
Akra, M. & Bazzi, L., "On the solution of linear recurrence equations," Computational Optimization and Applications, 1998 — the original Akra–Bazzi method (unequal-split recurrences, §19.6). Real paper; exact volume/pages not pinned here.
al-Kindi and the origin of frequency analysis (9th century) — referenced in §25.1 and reused in the exercises/quiz. A real historical attribution; no single primary text is cited directly.
Alan Perlis epigraph ("Within a computer, natural language is unnatural") — case study 2; from Perlis's Epigrams on Programming (ACM SIGPLAN Notices, 1982), widely reprinted.
Algorithmic-complexity / hash-flooding denial-of-service attacks — a real, widely documented class of attack (the basis of Case Study 1's scenario); no single specific publication is pinned down here.
All mathematical content (Euler's formula, edge bounds, clique/greedy bounds, bipartite characterization, six-/five-color theorems, Kuratowski) matches the chapter body; no result was introduced that the chapter did not teach.
Babbage epigraph ("The whole of arithmetic now appeared within the grasp of mechanism") — Charles Babbage, Passages from the Life of a Philosopher (1864); reused from the chapter body as the case-study-02 epigraph. (Real source; exact page not pinned.)
Bell–LaPadula model (security clearances as a lattice of (level, compartments) labels) — attributed to D. E. Bell and L. J. LaPadula (1973). Used illustratively in Exercise 13.24.
Bertrand's postulate (a prime exists in (n, 2n] for every n >= 1), proved by Chebyshev; referenced in Exercise 2.26. Classical, widely reported theorem; specific publication not pinned — treat as attributed.
Birthday bound / birthday paradox for hash collisions ($\sim \sqrt{N}$ threshold for an $N$-bucket hash) — standard cryptographic folklore result; see Katz–Lindell. [katzlindell2020]
Borůvka's algorithm — Otakar Borůvka, 1926 (Moravian electrical grid).
Burnside's lemma (referenced in §15.5 and Exercise 15.20 as the tool for non-uniform over-counting) — the result is classical, commonly attributed to Burnside though also to Cauchy and Frobenius ("the lemma that is not Burnside's"); not developed in this book.
C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, 27:379–423, 623–656, 1948. (Founding information-theory paper; defines entropy. Freely available.)
Cantor epigraph ("A set is a Many that allows itself to be thought of as a One") — commonly attributed to Georg Cantor (also used as the chapter epigraph).
Cantor epigraph (case study 2), "In mathematics the art of proposing a question must be held of higher value than solving it" — commonly attributed to Georg Cantor (doctoral thesis, 1867).
Cantor pairing function $\pi(i,j) = (i+j)(i+j+1)/2 + j$ — standard, attributed to Georg Cantor.
Cantor pairing function π(x,y) = (x+y)(x+y+1)/2 + y (case study 2, Option C) — the standard bijection N×N -> N, commonly attributed to Georg Cantor.
Cantor's diagonal argument (1891) and Cantor's theorem $\lvert S\rvert < \lvert \mathcal{P}(S)\rvert$ — Georg Cantor. Attributed; covered rigorously in Tier-1 texts above.
Carly Fiorina, "The goal is to turn data into information, and information into insight." — epigraph of Case Study 2; commonly attributed to Fiorina (oft-quoted as a 2004 remark).
Case Study 2 epigraph ("The channel does not promise to deliver your bits unchanged…") and Case Study 1 epigraph ("It passed every load test we ran. It still went down.") — composed for this book (no external attribution claimed).
Case-study-01 epigraph ("You cannot manage what you cannot measure") — management folklore, often loosely attributed to Drucker; used as paraphrase, not a verified quotation.
Cayley's formula ($n^{n-2}$ spanning trees of $K_n$) — Arthur Cayley, 1889.
Chapter epigraph (index.md, "Logic is the anatomy of thought") — commonly attributed to John Locke (per the chapter body); attribution carried as-is from the chapter, not independently verified.
Chazelle, "A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity," Journal of the ACM, vol. 47 (2000). Real landmark paper; cited for context only.
Christofides' algorithm (3/2-approximation for metric TSP), 1976 — commonly attributed to N. Christofides; the bound and method are standard textbook material (CLRS), the original technical report not independently verified here.
Christofides' metric-TSP approximation (the $\le \tfrac{3}{2}$-optimal heuristic referenced via §37.6 and Chapter 30) — commonly attributed to N. Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Carnegie Mellon University technical report, 1976.
Church–Turing thesis as the convergence of Turing machines, Church's lambda calculus (1936), and Gödel–Herbrand general recursive functions, with Post's systems — standard attribution; the equivalences are theorems covered in Sipser. Used in quiz Q4–Q5 and case studies. Attributed.
Computerphile halting-problem and Turing-machine explainer videos (YouTube) — real, freely available video series featuring working theorists. Specific episodes not pinned. Attributed.
Concorde TSP solver and Google OR-Tools — named as real, widely-used tools in further-reading / case-study connections; mentioned by name only, no specific claims requiring citation.
Continuum Hypothesis independence: Gödel (1940, consistency of CH with ZFC) and Cohen (1963, independence via forcing). Real results; original papers not pinned here. Summaries in Sipser and standard set-theory texts.
Cut property / cycle property and the exchange-argument proof technique — standard; presented as in CLRS Ch. 23 and Kleinberg–Tardos.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proceedings of the IRE, 40(9):1098–1101, 1952. (The original Huffman paper; volume/issue/pages are the commonly cited values.)
D. Kozen, Automata and Computability (Springer, 1997) — lecture-note-style text covering this chapter's arc plus computability and complexity. Real text; flagged Tier 2 pending edition/section pinning.
Daniel Kahneman, Thinking, Fast and Slow — base-rate neglect and representativeness (synthesis of the Kahneman–Tversky program). (Real book; specific chapters not pinned.)
Davey & Priestley, Introduction to Lattices and Order, 2nd ed. (Cambridge University Press) — standard order-theory text; cited for the lattice/Boolean-algebra development and "finite Boolean algebra has size a power of two." (Real, widely used; exact pagination not pinned here.)
Dedekind's definition of an infinite set (a set equinumerous with a proper subset of itself) — Richard Dedekind, Was sind und was sollen die Zahlen? (1888). Attributed.
Descartes epigraph (chapter body, "Divide each difficulty…", Discourse on the Method) — verified classical source; noted here only because the ancillaries echo the chapter's divide-and-conquer theme.
Descartes, Discourse on the Method (1637), the second precept ("divide each difficulty…") — used as the Case Study 2 epigraph; standard translation.
Diffie & Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, 1976 (foundational public-key / trapdoor paper; year and venue widely documented).
Dijkstra epigraph ("Testing shows the presence, not the absence, of bugs") — commonly attributed to E. W. Dijkstra.
Dijkstra epigraph for Case Study 2 ("Simplicity is prerequisite for reliability") — commonly attributed to E. W. Dijkstra (EWD498).
Dijkstra-style aphorisms about testing are NOT used here (that quote belongs to Ch.6); confirmed no reuse.
Dilworth's theorem (largest antichain = minimum chain cover) — attributed to R. P. Dilworth (1950).
Dirac's theorem (degree ≥ n/2 ⇒ Hamilton circuit), 1952 — result stated in the chapter body; commonly attributed to G. A. Dirac. (Treated as named result; primary publication not independently verified here.)
E. F. Codd, "A Relational Model of Data for Large Shared Data Banks," Communications of the ACM, 13(6), 1970 — founding paper of the relational model; source of the chapter epigraph (paraphrased premise) and the §12.6 database section. Real and historic; exact page numbers not pinned here.
E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959 (early example of analyzing an algorithm by input size; the origin of Dijkstra's shortest-path algorithm).
E. W. Dijkstra, "Testing shows the presence, not the absence, of bugs." (Genuine, widely quoted Dijkstra remark; used as Case Study 1 reasoning and §39.7 framing.)
Easley & Kleinberg, Networks, Crowds, and Markets (Cambridge UP) — small-world structure, centrality, communities. (Real, widely used text; freely readable online.)
Enderton, Elements of Set Theory (Academic Press, 1977) — standard text for Cantor's theorem in full generality. Tier 2 (real, edition/printing not pinned here).
Epigraph (Case Study 1), "A model of computation is not a computer. It is an argument about what computers can do." — paraphrase in the spirit of Sipser (as labeled in the chapter body); not a verbatim quotation.
Epigraph (Case Study 1): "It is the mark of an instructed mind to rest satisfied with the degree of precision…" — commonly attributed to Aristotle (Nicomachean Ethics, Book I). Attribution hedged.
Epigraph (Case Study 2), "A program is correct when you can explain why it works — to a skeptic." — uncredited aphorism reused from the Chapter 6 case-study style; constructed for teaching, not attributed to a specific source.
Epigraph (Case Study 2): "All models are wrong, but some are useful." — commonly attributed to George E. P. Box.
Epigraph (case-study-01), "It is the mark of an educated mind to be able to entertain a thought without accepting it" — commonly attributed to Aristotle; precise source disputed, so attributed, not asserted.
Epigraph (case-study-02), Curry–Howard correspondence ("a proof is a program; the formula it proves is a type") — a real, well-known result (Curry; Howard 1969), summarized rather than quoted.
Epigraph (chapter body, not mine): "When the facts change, I change my mind…" — commonly attributed to John Maynard Keynes (attribution disputed; already hedged in index.md).
Erdős "alien demanding R(5,5) / R(6,6)" remark — widely retold anecdote, commonly attributed to Paul Erdős (chapter body §40.3).
Erdős, P., "Some remarks on the theory of graphs," Bulletin of the AMS, 53 (1947), 292–294 (landmark paper launching the probabilistic method; track down a reliable copy).
Euclid, Elements, Book VII Props. 1–2 (Euclidean algorithm) and Book IX Prop. 20 (infinitude of primes). Canonical attribution is secure; exact proposition numbering varies slightly by edition/ translation — labeled as such in further-reading.md.
Fermat pseudoprime to base 2 / smallest example 341 = 11·31 (Exercise 23.23) — standard number-theory fact; the term and example appear in Rosen and CLRS.
Feynman blackboard quote, "What I cannot create, I do not understand," 1988. (Real, widely attributed to Richard Feynman; also the chapter-body epigraph — Case Study 2 epigraph.)
Feynman epigraphs: "The first principle is that you must not fool yourself — and you are the easiest person to fool" (Caltech commencement address, 1974, "Cargo Cult Science"); "What I cannot create, I do not understand" (found on Feynman's blackboard at his death, 1988). Commonly attributed to Richard P. Feynman.
G. H. Hardy, A Mathematician's Apology (1940) — the "number theory is useless" remark referenced in the chapter Overview and further-reading.md. Real, widely cited essay; specific page not pinned.
George E. P. Box epigraph ("All models are wrong, but some are useful") — case study 1; the aphorism is commonly attributed to Box (statistician).
Gerd Gigerenzer, Calculated Risks (also published as Reckoning with Risk) — natural-frequencies treatment of the base-rate fallacy; real medical-test and courtroom examples. (Real, widely cited book; exact edition/pagination not pinned.)
Goldbach conjecture, referenced in quiz Q18 ("verified by computer past $10^{18}$, still unproved"). The bound $10^{18}$ is widely reported but not pinned to a specific source here; treat as attributed. (Carried over from index.md, which raised the same flag.)
Graham & Hell, "On the History of the Minimum Spanning Tree Problem," Annals of the History of Computing, 1985. Real, frequently cited survey; exact volume/pages not verified here.
Graham, R. L., Rothschild, B. L. & Spencer, J. H., Ramsey Theory, 2nd ed., Wiley (standard Ramsey-theory monograph; confirm edition for your copy).
Graph-cut image segmentation literature — interactive foreground extraction, commonly associated with Y. Boykov & M.-P. Jolly (interactive graph cuts) and with the GrabCut system (Rother, Kolmogorov & Blake). Cited in further-reading and §34.6 application; exact publications not pinned down here.
Hamming epigraph ("The purpose of computing is insight, not numbers") — commonly attributed to R. W. Hamming (motto of his Numerical Methods for Scientists and Engineers).
Hamming epigraph, "The purpose of computing is insight, not numbers" — commonly attributed to Richard W. Hamming (Numerical Methods for Scientists and Engineers, 1962). Used as the Case Study 2 epigraph.
Hamming epigraph, Case Study 2 ("The purpose of computing is insight, not numbers.") — commonly attributed to Richard W. Hamming (preface, Numerical Methods for Scientists and Engineers).
Hart, Nilsson & Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968 (the original A* paper). Cited in further-reading and Case Study 1 for the admissible-heuristic idea.
Held–Karp dynamic-programming TSP, O(n^2 2^n) — commonly attributed to M. Held and R. M. Karp (1962); the complexity is standard, the original paper not independently verified here.
Hilbert epigraph (case study 1), "The infinite! No other question has ever moved so profoundly the spirit of man" — commonly attributed to David Hilbert ("Über das Unendliche", 1926).
Hilbert epigraph, "No one shall expel us from the paradise that Cantor has created for us" — commonly attributed to David Hilbert ("Über das Unendliche", 1926). [used in index.md; referenced for consistency]
Hilbert's Hotel parable — commonly attributed to David Hilbert (popularized via Gamow). Illustrative pedagogy.
Hoare epigraph ("The most important property of a program is whether it accomplishes the intention of its user") — commonly attributed to C. A. R. Hoare.
Hopcroft, Motwani & Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed. (Pearson, 2006) — classic text; cited for the pumping lemma and the Myhill–Nerode theorem. Exact section numbers vary by printing, so flagged Tier 2.
Hypothesis property-based testing library documentation (hypothesis.readthedocs.io), "What is property-based testing?" introduction. Real, widely used tool; cited as the practical realization of §2.4 counterexample search. Specific page not pinned.
I. S. Reed & G. Solomon, "Polynomial Codes over Certain Finite Fields," Journal of the Society for Industrial and Applied Mathematics (SIAM), 1960 — original Reed–Solomon paper (evaluation view). Widely cited; exact pagination not pinned down here.
icontract (Python design-by-contract library), named in Case Study 2 as a real-world analogue of the contract decorator built there. Real library; no specific page cited. NOT in references.bib.
J. Bloch, "Nearly All Binary Searches and Mergesorts Are Broken," Google Research Blog, 2006 (widely cited account of the binary-search overflow bug).
J. Hadamard, "The shortest path between two truths in the real domain passes through the complex domain." (Genuine remark commonly attributed to Jacques Hadamard; Case Study 1 epigraph.)
K. Thompson, "Regular Expression Search Algorithm," Communications of the ACM, vol. 11, no. 6, pp. 419–422, 1968 — the original source for Thompson's construction (regex → NFA). Real and historic; flagged Tier 2 pending exact citation verification.
Kahn's algorithm for topological sorting (the in-degree / repeated-source-removal method offered as case-study-02 "Your Turn" Option D). Commonly attributed to A. B. Kahn, "Topological sorting of large networks," Communications of the ACM, 1962. Named here; exact pagination not pinned down. The algorithm itself is standard and also appears in CLRS-style treatments.
Kahneman, Thinking, Fast and Slow (Farrar, Straus and Giroux, 2011). Real, popular; cited as context for why fallacies persuade (§3.3). General reference, no specific chapter pinned.
Kerckhoffs's principle — "a cryptosystem must remain secure even if everything about it except the key is public." Due to Auguste Kerckhoffs, La cryptographie militaire (1883); most often met via Shannon's restatement "the enemy knows the system." Used as the Case Study 1 epigraph (attributed to Shannon's restatement) and throughout the security discussion. Attribution reliable; exact 1883 wording not pinned down here.
Khan Academy "Journey into Cryptography" unit — free online course resource (real, freely available).
Kirchhoff's matrix-tree theorem — Gustav Kirchhoff, 1847.
Kleinberg & Tardos, Algorithm Design (Addison-Wesley, 2005), greedy-algorithms chapter (MST via exchange arguments; MST and maximum-spacing clustering). Real, widely used text; specific section numbering not verified here.
Knuth epigraph ("Beware of bugs in the above code; I have only proved it correct, not tried it") — commonly and reliably attributed to Donald E. Knuth (from a 1977 memo to Peter van Emde Boas); used as the case-study-01 epigraph. (Wording verified in wide circulation; original memo not pinned.)
Knuth epigraph, "Premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" — commonly attributed to Donald E. Knuth ("Structured Programming with go to Statements," 1974). Used as the Case Study 1 epigraph.
Knuth epigraph, Case Study 1 ("Premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.") — commonly attributed to Donald E. Knuth (from "Structured Programming with go to Statements," 1974).
Knuth, "Premature optimization is the root of all evil…" (Case Study 1 epigraph) — widely attributed to D. E. Knuth, "Structured Programming with go to Statements," ACM Computing Surveys, 1974.
Knuth, Larrabee & Roberts, Mathematical Writing (MAA / Stanford course notes). (Real, freely available notes on writing mathematics.)
Kruskal's algorithm — Joseph B. Kruskal, 1956.
Kurose & Ross, Computer Networking: A Top-Down Approach (network-layer routing: OSPF/link-state ≈ Dijkstra; RIP/distance-vector ≈ distributed Bellman-Ford; count-to-infinity). Edition not pinned.
L. Euler, "Solutio problematis ad geometriam situs pertinentis" (1736) — the founding paper of graph theory resolving the Königsberg bridge problem; cited via commonly available English translations and summaries (exact translation/edition not pinned down here).
L. Fortnow, "The Status of the P versus NP Problem," Communications of the ACM, vol. 52, no. 9, 2009, pp. 78–86. (Widely read survey of the open problem.)
Leslie Lamport, "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable." — epigraph of Case Study 1; widely attributed to Lamport (email/quote, c. 1987).
Manning, Raghavan & Schütze, Introduction to Information Retrieval — "Text classification and Naive Bayes" chapter (Laplace smoothing, log-space scoring, conditional-independence assumption). Freely available online. (Real, standard reference; chapter title attributed from memory.)
Matiyasevich, Hilbert's Tenth Problem (MIT Press, 1993) — monograph on the 1970 result (no algorithm decides integer solvability of Diophantine equations), the Davis–Putnam–Robinson–Matiyasevich line. Real result; exact edition not pinned. Attributed (matches the chapter body's mention).
Max-flow min-cut theorem attribution: Ford & Fulkerson (1956) and, independently, Elias, Feinstein & Shannon (1956) — historical attribution stated in the chapter epigraph (index.md), reused without re-citation in ancillaries.
Mirsky's theorem (longest chain = minimum antichain cover) — attributed to Leon Mirsky (1971).
Motwani & Raghavan, Randomized Algorithms — Las Vegas vs. Monte Carlo, error amplification. (Real graduate text; specific pages not pinned.)
Møller & Schwartzbach, Static Program Analysis (lecture notes, Aarhus University; freely available online) — widely used notes on sound approximation / abstract interpretation as the practical response to undecidability (§36.6). Real, but the current version/date is not pinned. Attributed.
networkx documentation — shortest-path functions (dijkstra_path, bellman_ford_path, floyd_warshall, astar_path), free online. Cited as a tool for checking hand-rolled implementations.
Niklaus Wirth, Algorithms + Data Structures = Programs (1976) — referenced only via the folk paraphrase used as the Case Study 1 epigraph spirit ("the structure of the data determines the structure of the program"); the exact wording is illustrative, not a direct quotation (see Tier 3).
No DOIs, page numbers, or statistics were invented. All Tier-2 attributions name real, well-documented results or works; specifics left unpinned are tagged accordingly per Bible §7.
OEIS / networkx sample graph datasets (free) — suggested as real graphs for conjecture-and-test exercises.
OEIS — On-Line Encyclopedia of Integer Sequences, sequence A000045 (Fibonacci), oeis.org. Real, freely available; specific identities not individually verified here.
On-Line Encyclopedia of Integer Sequences (OEIS), sequences A000040 (primes) and A000010 (Euler totient) — community-maintained reference; cited in further-reading.md and used illustratively for the $\phi(26)=12$ remark in case-study-02.
Petzold, The Annotated Turing (Wiley, 2008) — a real, well-regarded line-by-line commentary on Turing's 1936 paper. Edition/printing not independently re-verified here. Attributed.
Pierce et al., Software Foundations, Vol. 1 Logical Foundations (Coq-based, freely available). Real, widely used; cited as an interactive proof-checker companion to §3.5.
Pierce, Types and Programming Languages (MIT Press). Real, canonical; cited for "a type system is a set of inference rules" (§3.6). Specific chapter numbers not pinned.
Post Correspondence Problem — Emil Post (1946), proven undecidable; treated in Sipser Ch. 5. Real result. Attributed.
Post-quantum cryptography and Shor's algorithm — the real fact (a large quantum computer factors efficiently, threatening RSA) and the NIST post-quantum standardization effort. Mentioned in further-reading as "what comes after RSA." Tier 2: widely documented; no single publication pinned down.
Prim's algorithm — Vojtěch Jarník (1930), Robert C. Prim (1957), Edsger W. Dijkstra (1959).
Python all() / any() official documentation (docs.python.org, Built-in Functions), including the empty-iterable semantics (all([]) is True, any([]) is False). Stable, verifiable online reference; exact URL/version not pinned here.
R. M. Karp, "Reducibility Among Combinatorial Problems," in Complexity of Computer Computations (eds. Miller & Thatcher), Plenum Press, 1972, pp. 85–103. (Karp's 21 NP-complete problems.)
R. W. Hamming, "Error Detecting and Error Correcting Codes," Bell System Technical Journal, 1950 — the founding paper of the (7,4) Hamming code. Widely cited; exact pagination not pinned down here.
Red Blob Games / "Amit's A Pages" (redblobgames.com) — interactive BFS/Dijkstra/A visualizations (free online). Cited in further-reading and Case Study 1 for the "expanding circle vs. goal-directed" contrast.
Rice's theorem (every nontrivial semantic property of programs is undecidable) — H. G. Rice (1953); proof by reduction from HALT given in Sipser §5.1. Real result; original paper not pinned here. Attributed.
Russ Cox, "Regular Expression Matching Can Be Simple And Fast" (and the follow-up articles in the series), swtch.com, 2007 — widely cited explanation of catastrophic backtracking vs. automaton-based (Thompson NFA + on-the-fly subset) matching. Online article; flagged Tier 2.
Russell & Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (logical agents; first-order inference: resolution, forward/backward chaining, unification). Real, standard reference; exact chapter numbers not verified.
S. A. Cook, "The Complexity of Theorem-Proving Procedures," 1971 — the original paper introducing NP-completeness and proving SAT NP-complete (the Cook–Levin theorem). Named here; exact proceedings pagination not pinned down. Widely regarded as the founding NP-completeness result.
Sedgewick & Wayne, Algorithms, 4th ed. (Addison-Wesley, 2011), §4.3 (Minimum Spanning Trees); lazy/eager Prim. Real text with a freely available companion site; section attributed from memory.
Sedgewick & Wayne, Algorithms, 4th ed. (BSTs, balanced trees, priority queues; widely used text).
Sedgewick & Wayne, Algorithms, 4th ed., "Graphs" section, and the associated free Algorithms, Part I materials (Graph API, adjacency-list implementation). Real, widely used; exact section/page not pinned here.
Shannon / Kerckhoffs's principle ("the enemy knows the system") — epigraph in case-study-02; commonly attributed to Claude Shannon paraphrasing Auguste Kerckhoffs. Standard attribution; exact wording varies.
Shannon's maxim ("The enemy knows the system being used") — commonly attributed to Claude Shannon, paraphrasing Kerckhoffs's principle; used as the Case Study 1 epigraph.
SHAttered (2017): Stevens, Bursztein, Karpman, Albertini, Markov — first practical SHA-1 collision (two distinct PDFs with the same SHA-1). Used illustratively in case study 1; real result, exact citation not pinned. Attributed.
Singh, S., The Code Book (Anchor/Doubleday, 1999) — popular history of cryptography (Caesar → al-Kindi → RSA → the secret British public-key prehistory of Ellis/Cocks/Williamson). Cited in further-reading as the narrative companion. Tier 2: a real, widely read book whose specific page claims are not pinned here.
Sperner's theorem (largest antichain in the subset lattice is the middle binomial coefficient) — attributed to Emanuel Sperner (1928). Used in Exercise 13.25.
Stanford Encyclopedia of Philosophy, entries "Set Theory" and "The Continuum Hypothesis" — real, citable scholarly references (plato.stanford.edu); specific revision dates not pinned.
Sun Tzu, Mathematical Classic (孫子算經), 3rd–5th century CE — original statement of the remainder puzzle solved in §23.4 (primary historical source; exact dating approximate, attribution standard).
Tan, Steinbach, Karpatne & Kumar, Introduction to Data Mining, 2nd ed. (Pearson, 2018), hierarchical (single-linkage) clustering section. Real text; section attributed from memory.
The Frobenius / postage-stamp ("Chicken McNugget") problem and the formula g(a,b) = ab − a − b for the largest non-representable amount with coprime a, b — a classical result commonly attributed to J. J. Sylvester / G. Frobenius. Exact original publication not pinned down here.
The appearance of 1/e as the limiting fraction of derangements (hat-check / secret-santa), used in the quiz, exercises 17.29 and 17.31, and case-study framing, is classical and textbook-standard (covered by Rosen §8.6 above); attributed there rather than to a primary source.
The CRT-based RSA decryption "~4× speedup" (Case Study 2, Phase 5; Exercise 25.27) — a real, standard implementation technique (often called "RSA-CRT" / the Garner/Quisquater–Couvreur approach). The factor is the chapter body's stated figure; the precise origin is attributed but not pinned to one paper.
The friendship-theorem result R(3,3) <= 6 ("any 6 people contain 3 mutual acquaintances or 3 mutual strangers"), used in Exercise 17.16, is the classical base case of Ramsey theory — a standard result; the specific small-Ramsey-number value is well established but no single source is pinned here.
The On-Line Encyclopedia of Integer Sequences (OEIS), oeis.org — community-maintained; entries A000045 (Fibonacci), A000073 (Tribonacci), A000225 (2^n - 1, Tower of Hanoi). Cited as a practice resource; verify any specific identity independently.
Thomas Mann epigraph for Case Study 1 ("Order and simplification are the first steps toward the mastery of a subject") — from The Magic Mountain; commonly attributed to Mann.
Tower of Hanoi puzzle and the "priests of Brahma"/end-of-the-world legend — introduced and popularized by Édouard Lucas (1883); the legend is folklore, and it is the source of the 2^64 - 1 figure in §18.2. (Lucas's name is also attached to the Lucas numbers.)
Trudeau, Introduction to Graph Theory (Dover reprint). Real, well-known introductory paperback; edition/year not pinned here.
Turing chapter epigraph (in index.md, "cold porridge") — commonly attributed to Alan Turing; inherited from the chapter body, not re-cited in ancillaries.
Universal hashing and the family $h_{a,b}(k) = ((ak+b)\bmod p)\bmod m$ — commonly attributed to J. L. Carter and M. N. Wegman ("Universal classes of hash functions"), as presented in CLRS Ch. 11. Named in §26.3 of the chapter body and reused in the exercises/case study.
Velleman, How to Prove It, 3rd ed. (chapters on quantificational logic — reading a statement's logical form to translate and negate). Real, widely used text; specific chapter/section not pinned. NOT in references.bib (add if a hard cite is wanted).
Wilson's theorem ($(p-1)! \equiv -1 \pmod p$), Exercise 23.24 — result commonly attributed to John Wilson (stated by Waring, 1770; first proved by Lagrange).

Tier 3 — Illustrative / constructed (labeled in text)

"BallotBox" confidential-voting service (Case Study 1) and "NoteDrop" public-key note service (Case Study 2) are constructed teaching scenarios. The numeric keys reuse the chapter's own hand-verified example $(n,e)=(3233,17)$, $d=2753$ (Case Study 1) and a freshly worked key $(n,e)=(391,5)$, $d=141$ (Case Study 2); the load-bearing claims are the hand-derived round-trips and attacks, not the fictional product framing.
"Fleetwise" telemetry-pipeline audit scenario (case-study-01) — fully constructed.
"HashVault" content-addressable storage vendor and its three marketing claims (case study 1) — constructed for teaching; a hypothetical composite of real CAS systems (Git, Docker, IPFS).
"NorthPay" fraud-detector scenario (Case Study 1) — hypothetical company and numbers.
"Quotron" quote-aggregation service (Case Study 1) and the environmental-sensor frame protocol (Case Study 2) are constructed teaching scenarios.
"TerminusGuard" static-analysis vendor and its three marketing guarantees G1/G2/G3 (case study 1) — constructed for teaching; a hypothetical composite of real static analyzers / termination checkers. Labeled as a scenario.
All capacity numbers, eligibility lists, and seat counts in the case studies and exercises are fabricated for pedagogy.
All capacity/timing tables use the chapter's "1 operation = 1 ns" convention as an illustrative back-of-envelope, matching the §14.5 table.
All code examples are author-written and hand-traced; none were executed.
All exercise relations, partitions, and the Bell-number brute-force scenario (12.29) are constructed examples.
All exercise scenarios (delivery-truck assignment, streaming UI layouts, etc.) — constructed for teaching.
All exercise scenarios (espresso-machine cleaning cycles 23.21, open-addressing hash probes 23.22) are constructed/illustrative.
All exercise scenarios (exam scheduling, "people you may know," snapshot deduplication) are constructed for instruction.
All exercise scenarios (license plates, menus, configuration objects, hash buckets, protocol state descriptors) are illustrative constructions.
All exercise scenarios (snowplow, genome-assembly framing, PCB drilling, museum tour) — constructed or composite teaching scenarios.
All exercise scenarios (URL shortener, seating system, ID-card PINs, network event encoding) are hypothetical examples for modeling practice.
All numeric cost estimates in case study 1 (e.g., ~3e14 vs ~4e7 operations) are order-of-magnitude illustrations reasoned by hand, not measured benchmarks.
All Python code, sample tables, and hand-traced outputs — authored for the chapter; never executed (per Hard Rule §9.1).
All Python code, transition tables, configuration traces, and hand-derived # Expected output: comments — authored for the chapter; never executed (per Hard Rule §9.1).
All scenarios are composite/hypothetical: the "Helpdesk Console" access-control system and its users/roles/resources data (Case Study 1); the contract-checker decorator and property tester built in Case Study 2; the access-control, distributed-system, and contract modeling prompts (Exercises 2.24, 2.25, 2.31). No real product is referenced.
All small numeric instances (the 4-cycle conflict graph, the two-clause 3-SAT formulas, the §37.6 TSP distance matrix reused in Exercise 37.27) are hand-constructed examples; outputs are hand-derived, never executed.
All worked scenarios (the calculator/expression-tree code review in Case Study 1; the Huffman logging compressor in Case Study 2; the file-system, autocomplete, and org-chart modeling exercises) are constructed composites for instruction.
Case Study 1 "Maplewood" street-sweeper network and its edge list — a hypothetical example constructed to be hand-verifiable.
Case Study 1 ("Aggregator" nightly job, the two planted performance bugs, the 45x slowdown and doubling ratios) is a composite scenario constructed for teaching; the numbers are illustrative.
Case Study 1 ("Northgate Couriers" delivery-routing district, road map, travel times, and the admissible heuristic table) — a constructed scenario.
Case Study 1 ("Recurrence Forensics"): the three suspect helper functions and the timing-out service are a constructed scenario.
Case Study 1 (data-center scheduler: jobs J1–J5, machines M1–M4) — a constructed teaching scenario.
Case Study 1 (ECC memory post-mortem on a database server) — a constructed scenario; the Hamming(7,4) used as a faithful scale model of real 72/64 SECDED memory.
Case Study 1 epigraph ("It is not enough to know that a program is slow...") — composed for this case study; not a sourced quotation.
Case Study 1 epigraph ("The bottleneck is always somewhere…") — constructed/folklore, labeled as such.
Case Study 1 epigraph attributed "in the spirit of" Wirth — the quoted sentence itself is a paraphrase constructed for teaching, explicitly labeled as a folk theorem, not a verbatim quotation.
Case Study 1 epigraph: "'It passed every test we tried' is the most expensive sentence in software." — constructed maxim (in the spirit of, but not attributed to, any specific source).
Case Study 1 epigraph: "A specification is a promise about every possible run, not a story about one." — constructed maxim.
Case Study 1's CI/CD "minimum workers" feature-request scenario (MIN-WORKERS) is a constructed, hypothetical example; no specific company or product. The reduction (3-COLORING $\le_p$ MIN-WORKERS) and the conflict-graph model are standard, but the workplace framing is composite.
Case Study 1: the build-system dependency manifest (release/api/auth/db/crypto/logging/metrics/ legacy_cache) is a hypothetical scenario.
Case Study 2 "SwiftDrop" courier and its 5×5 cost matrix — a hypothetical example; all costs chosen so every tour is hand-enumerable.
Case Study 2 ("arbitrage detector" three-currency rate table USD/EUR/GBP) — a rigged, constructed market for teaching; the 5.84%-per-lap loop is engineered to demonstrate a negative cycle.
Case Study 2 ("Fibonacci hashing buckets" / largest_fib_at_most feature) is a constructed example; the recurrence-analyzer and recursion-tree-summer tools are pedagogical.
Case Study 2 ("Layout Counter"): the widget-strip layout scenario and its variants are constructed for teaching (the underlying combinatorics is the standard domino/tiling problem of §18.2).
Case Study 2 (interleaved-Hamming burst-tolerant link for an IR sensor) — a constructed scenario; the binary block-interleaver is a teaching analogue of the CD CIRC scheme described in §38.6.
Case Study 2 (seminar enrollment: students s1–s6, sections SecA–SecC) — a constructed teaching scenario.
Case Study 2 epigraph ("A program is correct when you can explain why it works — to a skeptic") — reused unattributed maxim from the Chapter 6 case study; illustrative.
Case Study 2 epigraph ("A program is correct when you can explain why it works — to a skeptic.") — unattributed aphorism reused from the Chapter 6 sample's voice; illustrative.
Case Study 2 epigraph ("First make it correct, then make it fast, then make it general...") — composed for this case study; it paraphrases the well-known programming maxim "make it work, make it right, make it fast" (commonly attributed to Kent Beck) but is not a verbatim quotation and is not cited as such.
Case Study 2 epigraph is an in-text paraphrase of this chapter's §30.4, not an external quotation.
Case Study 2 epigraph: "Every assertion you write is a quantifier you decided to check at runtime." — constructed maxim.
Case Study 2 epigraph: "First make the conjecture cheap to test. Then make the proof impossible to fake." — constructed maxim.
Case Study 2's "verify/find workbench" onboarding-tool scenario is a constructed teaching device built directly on the chapter's verify_sat and three_sat_to_clique code; the brute-force find_sat and the instrumentation counters are illustrative.
Case Study 2: the customer-records table (Lovelace/Hopper/Turing rows and their messy contact fields) is a hypothetical scenario.
Case-study epigraphs: "The structure of the program should reflect the structure of the data" (a common recursive-programming maxim, stated without specific attribution) and the Case Study 2 opening line (an unattributed teaching aphorism). Neither is presented as a quotation from a named source.
Chapter epigraph "The shortest distance between two points is under construction." — attributed to Noelie Altito; humorous attribution carried from the chapter body, used illustratively.
Chapter index.md epigraph ("For all x, there exists a bug...") — constructed/illustrative, attributed in-text to "every programmer," not to a real source.
Euler's prime-generating polynomial $n^2 + n + 41$ (Exercise 2.27, and the code in exercise-solutions.py): a real, classical fact attributable to Euler (prime for n = 0..39, composite at n = 40), used illustratively; no in-text citation made.
Joyce Kilmer, "Trees" (1913) — chapter-body epigraph (public-domain poem; real attribution, used illustratively in index.md, not an ancillary citation).
No new bib keys beyond references.bib were required; all Tier-1 works are already in references.bib.
The "dependency bundler" plugin-selection scenario in case-study-02 (12-plugin catalog, ≤5 cap, the small 5-plugin value/cost instance) is hypothetical, constructed for teaching. The planted-error expected output and its correction are deliberate teaching devices.
The "Orchestrate" deploy-tool configuration (eight options with the stated value-counts), the brotli + ap interaction bug, and the 30-seconds-per-test framing in case-study-01 are hypothetical, constructed for teaching. The strategy counts (1,728 / 14 / 191 / 28) are computed from the constructed value-counts and are exact for that constructed instance.
The 14-user study-group friendship graph in case-study-01 (the giant component {0..11} plus the isolated pair {12,13}) is a constructed dataset designed to exhibit eccentricity, diameter, and disconnection.
The collisions_for_slot example output in Case Study 1 is an illustrative (hypothetical) run; the load-bearing claim there is the proof that such a collision set is enumerable, not the specific strings printed.
The cost.py running-time-predictor scenario in Case Study 2 (the team re-deriving loop costs, the planted wrong expected-output value) is constructed for teaching.
The fingerprint complexity-fingerprinter library in Case Study 2 is a teaching construction built on the chapter's complexity.py Project Checkpoint.
The render(...) configuration-space and test-generator scenario in case-study-02 is a hypothetical, constructed for teaching.
The suggest_mutuals recommendations-endpoint scenario in Case Study 1 is a composite, constructed example (no specific company or system).
The access-control "can_delete" scenario in case-study-01 (admin/owner/locked record) is a constructed code-review scenario.
The access-control, feature-flag, and toy-type-checker scenarios in exercises Part E are constructed.
The affine-cipher teaching tool and its concrete keys ($a=5,b=8$, etc.) in case-study-02 are constructed for instruction; the affine cipher itself is a standard classical cipher.
The binary symmetric channel is, per the chapter, a deliberate Tier-3 idealization.
The C-project build-dependency graph in case-study-02 (config/utils/db/api/web/cli/logger, plus the injected api->config cycle) is a constructed example in the spirit of make/Bazel dependency files.
The chapter epigraph (Lewis Carroll, Through the Looking-Glass) lives in index.md, not in the ancillaries, and is not re-cited here.
The CI-pipeline scenario in Case Study 1 (jobs, durations, the introduced cycle) is a constructed teaching example.
The clickbait-detector, load-balancer, and Monte Carlo primality modeling exercises (Part E/F) — constructed scenarios with chosen numbers.
The code-review scenarios in both case studies are constructed for teaching.
The course-enrollment table, "divides on {1,2,3,4}", and congruence-mod-3 examples (from the chapter body; reused in exercises/answers).
The DataCrate capacity-planning scenario in case-study-02 (CPU credits across service tiers; the premium/batch/cache constraints; the configcount module) is a hypothetical, constructed for teaching.
The eight-person engineering collaboration network in Case Study 1 (Priya/Quinn/Raj/Sam/Tara/Uma/Vik/Wen) is a hypothetical, constructed dataset.
The epigraphs opening case-study-01 ("How far apart are two people in a social network? Knock on every door one ring at a time, and count the rings.") reuses the chapter's own opening epigraph; the case-study-02 epigraph ("A build system's only real job is to do things in an order that never breaks a promise.") is an original aphorism written for this book, deliberately left unattributed (no fabricated source).
The exam-scheduling, music-app, and flash-storage scenarios in the "Model it" exercises are constructed examples.
The expression-evaluator code-review scenario (Case Study 1) and the shipping/stamp-maker scenario (Case Study 2) are constructed for teaching.
The feature-flag configuration explorer (case study 2) is a constructed teaching example.
The hash-table incident in case-study-01 (the "collapsed to one bucket" production scenario, the specific stride/size numbers) is a constructed teaching scenario.
The incident postmortem in case-study-01 (checkout 504s, database overload vs. connection-pool leak) is a constructed teaching scenario.
The intercepted ciphertext and the HE crib in Case Study 1 are a constructed example.
The login/authentication security policy and the "alarm" monitoring rule in Case Study 2 are constructed for teaching.
The mailing-list audit scenario (case study 1) is a constructed teaching example.
The office-graph running example, the eight-sensor clustering data set (Case Study 1), and the six-building campus fiber survey (Case Study 2) are all hypothetical examples with hand-chosen numbers.
The opening epigraph of case-study-01 ("The trouble with quotes on the internet…") is a deliberately light, fabricated-for-the-page line and is not attributed to any real source.
The password-policy audit scenario (Policies A/B/C), attacker guess rates, and the company review framing in case-study-01 are hypothetical, constructed for teaching.
The performance-review scenario in Case Study 1 (the timing-out batch job, the count_triples routine) is constructed for teaching.
The procurement/acceptance-test scenario, the "perfect infinite-loop detector" pitch, and the rival "detect every null-return" vendor (case study 1) — constructed teaching scenarios.
The product-code cache audit (case study 1) and the game-event codec (case study 2) are constructed teaching scenarios.
The Python build-tool / module-dependency scenario in case study 2 is a constructed teaching example.
The QA "oracle battery" coverage claim and the dovetailing test-input scenario (case study 2) — constructed teaching scenarios.
The ReDoS / input-validation incidents in Case Study 1 are constructed teaching scenarios (the (a+)+b pattern is a real, well-known catastrophic-backtracking example; the surrounding "incident" framing is composite).
The Residue Number System calculator scenario and its moduli (7, 11, 13) in Case Study 2 are constructed for teaching.
The SaaS conversion joint table (from §21.1, reused in exercises) — hypothetical.
The ShopRing hash-sharding scenario in case-study-01 (8 shards, 5,000,000 customer IDs, design claims D1/D2) is a hypothetical, constructed for teaching.
The six-message spam/ham training corpus (Case Study 2) — constructed toy corpus.
The small graphs used in the conjecture-and-test exercise (28.25) — path P4, triangle C3, cycle C4, K4 — are standard named graphs used illustratively, not citations.
The sniffed-ciphertext lists in Case Study 1 (e.g. [1387, 3086, 0, 1211, 1752, 1387]) are illustrative inputs chosen to demonstrate the deterministic-encryption attack; the load-bearing content is the rainbow table, every entry of which is hand-derived.
The social-media "generations" sharing model (Ex. 11.25) and the dynamic-array doubling figures (Ex. 11.26) are illustrative; the dynamic-array amortization result itself is standard (cf. CLRS, amortized analysis).
The startup employee-messaging scenario (Alice..Frank) in Exercise 28.21, the build-dependency rules in Exercise 28.22, the grid-maze model in Exercise 28.23, and the equal-cost packet-routing scenario in Exercise 28.24 are constructed modeling prompts.
The streaming-access, feature-flag, alarm-logic, and package-install scenarios in the exercises are constructed examples in the spirit of the chapter's §1.1 and §1.6.
The string "ABRACADABRA" and its frequency tally are a standard pedagogical example, used here for hand-tracing; the derived bit counts (23 vs. 33) are computed by hand in the text.
The study-buddy app / CSV edge-list export scenario in case study 1 is a constructed teaching example (extends the chapter's study-group anchor with users fin, gus, hal).
The telemetry-device noisy-wire scenario in Case Study 2 is a constructed teaching scenario.
The toy type lattice (Exercise 13.23) and the hardware-toolchain enable expression in Case Study 2 are constructed for teaching.
The Turing-machine simulator build, the three encoded machines (even length, length divisible by 3, unary/binary incrementer, spin), and the applied_to_self/make_D traces (case study 2) — authored for the chapter.
The two case-study epigraphs ("Counting is the sanity check that comes before the benchmark…" and "Before you enumerate a space, count it…") are teaching maxims composed for this book; no external attribution.
The two-slot meeting-scheduling problem in case-study-02 (Standup/Design/Retro) is a constructed constraint problem.
The unattributed epigraphs opening case-study-01 ("The most dangerous bugs are the ones that pass every test you thought to write.") and case-study-02 ("Tell the computer what a correct answer looks like, and let it find one.") are original aphorisms written for this book, deliberately left unattributed (no fabricated source).
The workshop LP / Ramsey-lab build scenario (case-study-02) — constructed; the LP and the source distribution reuse the chapter's worked example.
Wilf, generatingfunctionology (3rd ed., 2006) is cited in further-reading.md and is the source of the "clothesline" quote already present in the Chapter 17 body (index.md, §17.5). It is a Tier-1 canonical source but is NOT in references.bib. Recommend adding a BibTeX entry (e.g. @book{wilf2006genfun}) so the bibliography can key it; until then it is included here by full citation. No fabrication: the work, the quote, and the "Snake Oil" section are all genuine.