The Art of Computer Programming, Volume 3

Knuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.

Type

Book

Intellectual base

Textbook

Year

1973

Volume

3

ISBN

9780201038033

Link

https://openlibrary.org/books/OL25573192Mmatched

Cited from

mathematics

Cited by

3 citations across 3 artifacts.

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

Primes

• Associativity
  • Knuth's (1973) work on fundamental algorithms — including parsing and syntax trees — exploits associativity to balance tree structures for efficient parsing and search.

    This sourceThe searching half (Sec. 6.2.2 Binary Tree Searching, 6.2.3 Balanced Trees, 6.2.4 Multiway Trees) covers balanced/AVL search-tree algorithms that re-group and balance tree structures for efficient search; Re-sourced from the prior 'knuth-1973' (Vol. 1: Fundamental Algorithms), whose tree material is data structures (Ch. 2 Information Structures), not search/parsing. Verified.

Domain-specific

• Average-case complexity
  • … a convenient observable transfers from Quicksort has quadratic worst cases but expected n log n comparisons under suitable random-order or randomized-pivot assumptions. to A performance claim validates the workload distribution and reports high-cost tails because a favorable mean can hide rare operational failures..
• Robinson–Schensted–Knuth correspondence
  • … from A canonical instance directly demonstrates that the matrix encoding, row- or column-insertion convention, tableau semistandard rules, equal shape, weights, and inverse procedure are fixed. to An applied instance preserves the same invariant under a changed notation, scale, implementation, or empirical setting..

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? Not recorded. Neither this nor any other of the 3 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 1 other way.

• https://www.google.com/books/edition/The_Art_of_Computer_Programming/cYULBAAAQBAJ ×1

Registry ID ref:789a6b23c48c · see in the full table