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."

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:Many own, few read

[Anonymous Coward]

CLR is an excellent book for classroom teaching, and a reasonable place to go as a first reference, but it has very shallow coverage of most topics. Pick a topic that Knuth and CLR both cover, and for 25% of your questions both will cover, for another 50% Knuth will but not CLR, and for the remainder neither.

Of course, Knuth is somewhat out of date. And covers a much smaller set of topics. But frankly CLR only covers a small proportion of topics too, relative to all the things one might want to explore in CS - or even in algorithms.

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 :-)

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. ;^)

Question

[Spy der Mann]

Is this the same Knuth that wrote along with Morris and Pratt the famous string matching algorithm [uci.edu]?

Re:You can already buy some of it

[Anonymous Coward]

Longhorn could be delayed by 20 some years and it would still have slipped less than this volume. My CS professor last semester was constantly complaining about the fact that he's been waiting since he was a senior in high school for the next volume.

Re:Dear Knuth

[johnnyb]

I actually wrote my own book as sort of a prequel to TAOCP. TAOCP assumes that you already have experience with some sort of assembly language. My book doesn't assume anything:

My book teaches programming using assembly language on Linux [cafeshops.com]

Re:Many own, few read

[CEHT]

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

So who is Art, anyway? How does Mad Magazine fit?

[Anonymous Coward]

I did read once that the "Art" in "The Art of Computer Programming" is actually another programmer. IIRC it was in one of Peter van der Linden's books.

The same story also claimed that Professor Knuth was also a contributor of some note to Mad Magazine.

There's a fun bit in

[multiplexo]

The Atrocity Archives [amazon.com] 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: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:Nifty from the Knuth

[Anonymous Coward]

There was an episode of the old Steven Spielberg-prodcued TV series, Amazing Stories, that had exactly this plot. A man would instantly gain knowledge from his surroundings. He was a janitor at a local university, and (for example) would become a chemistry expert after being in the chemistry lab.

One day he went into the library and suffered as the weight of all human knowledge was jammed into him.

In the end, aliens came and collected all the knowledge out of his brain. They'd made him a knowledge sponge so that they could learn about Earth.

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: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

[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.

The Art of Wasting Time

[Anonymous Coward]

Didn't he publish "The Art of Computer Programming" in 1968, when he was still at Caltech (according to the preface to the first edition, which was written from Pasadena, California) , just before he arrived at Stanford?

Over thirty years later after finishing the third volume, he's almost finished with its successor. That's way too long, pretty inexecusable, and bordering on the laughable.

The greatest computer scientist in the world created, in the intervening years from third volume to retirement, the ...TeX.

A typesetting language.

Not HTML.

Not the World Wide Web.

Not the Internet.

A typesetting language so that nerdy graduate students could have an excuse for not socializing or doing original work while they fiddled around for hours using TeX to pretty-print their papers. After all, they are "working on the computer", aren't they?

Is this what Arthur C. Clarke thought we'd be doing in the year 2001? I don't seem to remember that "Dave" was conversing with the computer HAL via TeX formatted files. HAL was able to comprehend people just by READING THEIR LIPS, for crying out loud.

By contrast, consider a 27 page Ph.D. thesis written by a guy named John Forbes Nash back in 1950 at Princeton University. With no TeX in those days, the double-spaced typewritten thesis has hand-written mathematical formulae and Greek symbols scribbled among and in between the lines. That thesis would win Nash the Nobel Prize in economics in 1994. If I recall correctly, you can see an actual-sized reproduction of the entire thesis, complete with hand-written scribbles, in the book The Essential John Nash . (Somehow, the hand-written stuff makes you feel as if Nash is sitting in the room with you, and -- corny as it sounds -- closer to his genius, as if you peeked inside his diary or something. )

You don't need TeX to be successful; you just have to have good ideas, and you need to be spending time developing those good ideas rather than iteratively kerning your fonts.

Just what did Knuth do?

http://www.epinions.com/content_73675148932 [epinions.com]

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