Knuth's Art of Computer Programming Vol. 4

_mutators writes "bookpool.com has posted an excerpt from Knuth's long awaited The Art of Computer Programming: Volume 4. It is very short and discusses combinatorial searching. But when will it be published? Bookpool does not hazard a guess."

Comments

Still Waiting

[Detritus]

When I bought Volume 3, about 20 years ago, it included a postcard that the buyer could mail to the publisher, to be added to a mailing list for notification when Volume 4 was published. I sent in the postcard.

I'm still waiting.

Re:Still Waiting

[Surazal]

You should really let us know if the notification comes when the book is released. I wanna see how good they keep their customer records. ;^)

Re:Still Waiting

[Animats]

In 1967, you could order and prepay for all six volumes, to be delivered as published. At a good price, too. I wonder how many people are still waiting.

Re:Many own, few read

[cecom]

While I was growing up in Eastern Europe, it was completely impossible to find any of the volumes. They weren't available for sale and almost all copies had been stolen from the libraries (well, not exactly "stolen" but many people forgot to return the book and would much prefer to pay the library fine).

I eventually managed to get a hold of "Searching and Sorting" for a couple of days and I tried to read it. Needless to say, I didn't get far. One needs months to consume the whole thiing :-)

When I moved to the US, the first thing I did was to buy the series. I couldn't believe that it was actually available in stores! I have to admit though, I still haven't read the three volumes completely - ah, I miss the enthusiasm of my youth.

Didn't somebody say that one should never attempt to read the whole thing ? One should turn to a specific section and read it only when the need arises. That makes me feel better :-)

Question

[Spy der Mann]

Is this the same Knuth that wrote along with Morris and Pratt the famous string matching algorithm?

Re:Question

[Anonymous Coward]

Maybe his only realy valuable contribution to CS

Well I am not sure that's entirely true. He ushered in the 'field' of analysis of algorithms and suggested the use of the O-notation (of course he didn't 'invent' the notation). Also, I believe a lot of the parsing theory used in compilers actually stems from Knuth's early work. His contribution to theoretical CS is rather sizeable in my opinion (which is certainly biased being a student in his Dept.) and you should be able to discover that for yourself too if you have enough enthusiasm to probe into Theory.
ItA is popular because its a very decent book which is a lot more accessible to a larger population. TAOCP is a MUCH tougher read (but at the same time an order of magnitude more comprehensive).

Re:Many own, few read

[CEHT]

Reading all volumes is one thing. Try reading them and finish all the exercises is another.

There's a fun bit in

[multiplexo]

The Atrocity Archives by Charles Stross where one of the characters reveals that the reason why Knuth hasn't released volume 4 is that it contains a hack that allows you to solve non-deterministic polynomial (NP) problems in polynomial time. This is such a huge secret that the world's intelligence agencies, who already know how to do this, have an agreement with Professor Knuth where as long as he doesn't publish volume 4 they won't render him metabolically challenged (i.e, "dead".

The Atrocity Archives is a way cool book, I heartily recommend it to /. geeks. Stross used to work as a programmer/sysadmin so it's a lot of fun if you've ever worked in IT.

Re:Many own, few read

[fm6]

There was a version in between called MIXMaster.

Your other comments rest on the assumption that you can only talk about algorithms by writing code in an actual executable language. But lots of CS books don't do that. They rely on pseudo-code, or they compare implementations in various high- and low-level languages. Even TAOCP is written so you can skip over the MIX parts.

Besides, if the code examples are obsolete in 10 years, so what? Most textbooks require major revision after that long. (Not to be confused with the pseudo-revisions done every year so that new textbooks don't have to compete with used ones.) And that's in standard disciplines that change relatively slowly. Nothing changes as quickly as CS!

The more I think about it, the more I'm convinced that Knuth had what seemed like a good idea 40 years ago and can't let it go. (Actually, two of them; the other was that he could write a single comprehensive CS textbook.) That inability to see the flaws in a pet idea seems to be all too common among computer people.

Re:Many own, few read

[artakka]

I had a very similar experience. I finally managed to find all three volumes in a small bookstore in Latvia where we were spending our honeymoon. I spend the rest of the honeymoon reading volume 1.

This was in 1985 and I am still married to the same person.

Re:Many own, few read

[Zeinfeld]

I used to assume that Knuth simply acknowledged that CS had gotten too big to be summarized by a single introductory text. But it turns out that he's still working on it, even as the size of the project continues to grow. ("Volume 4" will actually be 4 volumes!)

I first met Knuth before I started my doctorate, that was almost twenty years ago. Volume 4 was already notoriously overdue at the time.

I don't think that Knuth's objective is suited to a book any more. The most appropriate form for an encyclopeadia would be a peer moderated Wiki. But that is not Knuth's point the most appropriate medium for describing algorithms is not assembler.

I think that the role of books in the field has to be different now. We do not need exhaustive catalogues of 'stuff'. What we need is the best, most relevant 'stuff'.

Take parsing for example. All students are still taught yacc and bottom up parsing as if it was the greatest thing. In fact it does not work for natural languages and it is too flexible for computer languages.

LISP does not have an LR(1) parser, it has a FSR with a minor extension to balance brackets. XML does not have an LR(1) parser either. In fact there is not much difference between XML and LISP when you look at parser design, the only differences are that the brackets get pointy and there is a strange need to repeat the first item of the list at the end...

What we really need is a book that shows students how they can apply the theory to actually do really useful stuff. The yacc approach teaches them to stay down at the level of the weeds, it does not teach building larger scale abstractions.

Re:Apples to oranges.

[chialea]

>The limitations of word are not so much due to the model (what you see is *only* what you get) than the implementation.

I've personally never seen a good wysiwyg equation editor. I've used several, and the pain and suffering I went through made me swear off everything but LaTeX. I personally don't see how you could use as many symbols as LaTeX gives you access to in a quick way, using a GUI. On top of that, MS Office has implementation problems. If I wanted my mathematical symbols to turn into freaking FLOWERS and LEAVES and STARS, I would have put them in that way.

(And by the way, I use TexShop. It's a little slower than using a makefile for final production, but you can script it if you really care. Usually I need to run BibTex once a week, at most, so it's not an issue.)

Lea