The Art of Computer Programming, Volume 1¶
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.
Cited by¶
9 citations across 9 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.
- The well-defined finite computational procedure (Knuth, 1997)
- Meta-Symbolic Reflection
- Listed in the references but not attached to a specific claim.
- Randomness
- 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.
- Computer science and cryptography depend on randomness for pseudorandom number generators (linear congruential, as catalogued by Knuth (1997)
- 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.
- 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.
- Recursion
- 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.
- 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.
Domain-specific¶
- Pointer
- Every classical dynamic data structure — linked list, binary tree, hash table with chaining, directed graph — is built on this primitive: each node stores one or more pointers to other nodes, allowing the structure to span non-contiguous storage and to be modified in place by redirecting pointers rather than copying data
This sourceKnuth's treatment of linked allocation, in which list and tree nodes at arbitrary locations are joined by link fields and updated by changing links.
Supported in partVerified against the source
- Every classical dynamic data structure — linked list, binary tree, hash table with chaining, directed graph — is built on this primitive: each node stores one or more pointers to other nodes, allowing the structure to span non-contiguous storage and to be modified in place by redirecting pointers rather than copying data
- Running total
- Topological Sorting
- The output is any one valid linear extension of the partial order encoded by the DAG; the procedure is well-defined if and only if the graph is acyclic, because a directed cycle is exactly the local obstruction that no linear extension can resolve.
This sourceDefines topological sorting as embedding a partial order in a linear order and states that such an ordering is always possible for a partial ordering.
Supported in partVerified against a saved copy of the source
“The problem of topological sorting is to embed the partial order in a linear”
- The output is any one valid linear extension of the partial order encoded by the DAG; the procedure is well-defined if and only if the graph is acyclic, because a directed cycle is exactly the local obstruction that no linear extension can resolve.
Verification¶
Does it exist? Confirmed. This work's ISBN resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 9 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:f9c005f02780 · see in the full table