The Art of Computer Programming, Volume 1

Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.

Type

Book

Intellectual base

Textbook

Year

1997

ISBN

9780201896831

Link

https://www.pearson.com/en-us/subject-catalog/p/art-of-computer-programming-the-volume-2-seminumerical-algorithms/P200000000337

Cited from

computer_science, linguistics_semiotics, mathematics

Cited by

15 citations across 14 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Algorithm
  • The well-defined finite computational procedure (Knuth, 1997)

    This sourceCanonical source for the formal definition of an algorithm via its five properties — finiteness, definiteness, input, output, and effectiveness

• Contraposition
  • This is a genuine compression of the search problem: in a setting with many candidate causes, each clean contrapositive elimination can remove a large fraction of the remaining space at once, which is the same logarithmic-style reduction that makes bisection, differential diagnosis, and the game of twenty questions effective

    This sourceAnalyzes binary search and its logarithmic reduction of a search space, the pruning structure underlying bisection.

• Equivalence Relation
  • An equivalence relation is not the same as equality-up-to-some-error-bound, the failure mode Knuth (1997) analyses in the seminumerical-algorithms context where floating-point ε-equality is reflexive and symmetric but not transitive.

    This sourceTreats floating-point representation and arithmetic, where ε-equality (|a−b| < ε) is reflexive and symmetric but not transitive (small ε-close chains accumulate to large gaps).

  • Computer science is the most operationally consequential second domain, and Knuth (1998) treats hash-based equivalence-class lookup and union-find equivalence-class maintenance as foundational algorithmic primitives in his sorting-and-searching volume.

    This sourceTreats hashing/searching (Ch. 6) and the algorithmic machinery underlying hash-based equivalence-class lookup and union-find equivalence-class maintenance.

• Hashing
  • Hashing is the structural pattern of deterministically reducing an arbitrary object to a short, fixed-size token such that the same input always yields the same token, the token is much smaller than the input, and the mapping is many-to-one — collisions are inevitable because the codomain is bounded.

    This sourceFoundational treatment of hash functions, hash tables, and universal hashing — deterministic many-to-one reduction to a bounded codomain with inevitable collisions.

• Meta-Symbolic Reflection
  • Listed in the references but not attached to a specific claim.
• Randomness
  • … noise in resistors), the statistical-mechanical ensemble averages that produce thermodynamics, and the stochastic differential equations governing fluctuating systems. Computer science and cryptography depend on randomness for pseudorandom number generators (linear congruential, as catalogued by Knuth (1997)

    This sourceCanonical reference for algorithm analysis: develops the algebra of linear and nonlinear recurrence relations as a substrate-independent mathematical apparatus applicable across computation, combinatorics, population dynamics, and physical systems.

• Recurrence
  • The same eigenvalue analysis that predicts whether a population will oscillate or stabilize applies to economic output, infection dynamics, and psychological recovery trajectories—the substrate-independent algebra of linear and nonlinear recurrences Knuth (1997) develops as a general computational tool.

    This sourceCanonical reference for algorithm analysis: develops the algebra of linear and nonlinear recurrence relations as a substrate-independent mathematical apparatus applicable across computation, combinatorics, population dynamics, and physical systems.

• Recursion
  • The call-stack as activation-record sequence
• Stack
  • A function call cannot return until functions it called have returned; an interpretation cannot pop a parenthesis level until inner levels are closed; a search cannot retract a decision until decisions made downstream of it are unwound; a person multitasking cannot resume an outer task until inner tasks complete; a legal argument depending on a precedent cannot be finalized until the precedent's status is settled.

    This sourceCanonical treatment (§2.2.1) of the stack (LIFO) data structure, push/pop discipline, and its use for procedure-call activation records and recursion.

Domain-specific

• Bombieri norm
  • For a fixed degree over real or complex variables, the Bombieri-Weyl inner product weights a multi-index coefficient by alpha-factorial over total-degree factorial; nonhomogeneous variants use separate conventions.
• Inverted index
  • Tokenization, normalization, field structure and update policy define the indexed vocabulary, and the faster query path trades for storage and indexing cost.
• Pseudorandom Number Generator
  • “Random” therefore describes selected output properties or adversarial indistinguishability, not nondeterministic causation.
• Randomness Test
  • Report the number of tests, dependence among them, multiplicity policy, sample sizes, and expected false-rejection rate.
• Tree Sort
  • In-order traversal therefore emits a nondecreasing sequence.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 4 other ways.

• https://www-cs-faculty.stanford.edu/~knuth/taocp.html ×2
• https://www.google.com/books/edition/The_Art_of_Computer_Programming/x9AsAwAAQBAJ ×1
• https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780201896855 ×1
• https://www.pearson.com/en-us/subject-catalog/p/art-of-computer-programming-the-volume-3-sorting-and-searching/P200000000345 ×1

Registry ID ref:f9c005f02780 · see in the full table