The Art of Computer Programming, Volume 3¶
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
Cited by¶
6 citations across 6 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- 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.
- 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
- Equivalence Relation
- 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.
- 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.
- 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.
- 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.
Domain-specific¶
Mechanisms¶
- Adjacent-Swap Sequence
- Its cost, though, is quadratic in disorder: a sequence with many inversions needs many swaps, and crawling a far-displaced element across the whole structure can be dramatically more expensive than a single global sort.
This sourceRelates adjacent-exchange work to inversion count, which can grow quadratically with disorder.
- Its cost, though, is quadratic in disorder: a sequence with many inversions needs many swaps, and crawling a far-displaced element across the whole structure can be dramatically more expensive than a single global sort.
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Not recorded. Neither this nor any other of the 6 citations of this work carries a recorded support check.
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 3 other ways.
- https://www-cs-faculty.stanford.edu/~knuth/taocp.html ×1
- https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780133488845 ×1
- https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780201896855 ×1
Registry ID ref:78137d5cd648 · see in the full table