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

ISBN

9780201038033

Link

https://openlibrary.org/books/OL25573192Mmatched

Cited from

computer_science, mathematics

Cited by

7 citations across 6 artifacts.

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

Primes

• Associativity

  • This sourceTree and information-structure algorithms exploit associativity of underlying operations to re-group/balance computation trees

  • 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

• Commutativity

  • This sourceTree-balancing and parsing algorithms exploit associativity of underlying operations (concatenation, expression composition) to permit re-grouping of computation trees for efficient evaluation and search; foundational treatment of how associativity in computational structures enables optimization and balanced data-structure design.

• Complexity (Time/Space)
  • The distinction between worst-case, average-case, and amortized complexity variants

    This sourceFoundational treatment of algorithm analysis — worst-case and average-case asymptotic analysis and how cost scales with input size — supports D30-137, D30-142, D30-150. CITATION-FIX: the file dated the 2nd edition '1976'; it was published 1973. (See flag: 'amortized' analysis at D30-137 postdates this volume — Tarjan 1985.)

• Idempotence

  • This sourceTree-balancing and parsing algorithms exploit associativity of underlying operations (concatenation, expression composition) to permit re-grouping of computation trees for efficient evaluation and search; foundational treatment of how associativity in computational structures enables optimization and balanced data-structure design.

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

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 3 other ways.

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

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