The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth done in the 1970s has remained state-of-the-art up until today. It is amazing to me that so many of the theoretical developments of the time have survived decades of the obsolescence cycles that have eliminated all of their original implementations.

What fraction of the content of TAoCP have been eclipsed by later research? If an algorithm is found in TAoCP, what are the odds that a better one is out there in today's literature?

  • 3
    $\begingroup$ Can you be a bit more specific as to what you're asking here? I.e., is there a particular technical question that we can address? I find the question very broad and vague, so I am not even sure what a good answer would address. Surely you're not expecting a percentage? $\endgroup$ – Andrej Bauer May 20 '19 at 20:42
  • 2
    $\begingroup$ An answer might look something like a list of subjects along with a vague indication of how likely it is that Knuth's coverage of that subject will have been superseded. It is a soft question for sure, and although the answer is not technically subjective any answer probably will be. I mean "superseded" in a very strict sense, for example if Knuth said the best known algorithm is $O(n^2)$ but an $O(n)$ one has been discovered since. $\endgroup$ – Display Name May 20 '19 at 21:32

Matrix multiplication exponent has been improved and integer multiplication has recently reached speculated optimal complexity.

Perhaps Han`s sorting applies if correct (on which there was a post here).

Note Knuth`s book is his view.

Modern view is richer. For example I doubt Knuth has spent much time on $NC$ algorithms for perfect matching or derandomization of primality or linear programming or counting algorithms.

So perhaps the algorithms he studies probably on whole not much more progress. However the analogy to mathematics that mathematics problems open in classical view does not mean mathematics has not moved forward holds in algorithms.


Not the answer you're looking for? Browse other questions tagged or ask your own question.