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

Additional information

[HyperChicken]

The books homepage, http://www-cs-faculty.stanford.edu/~knuth/taocp.ht ml offers the fascicle for download for free. http://www-cs-faculty.stanford.edu/~knuth/fasc1.ps .gz You can still get $2.56 for each bug found, I believe.

Mirrors:
http://www-cs-faculty.stanford.edu.nyud.net:8090/~ knuth/taocp.html
http://www-cs-faculty.stanford.edu.nyud.net:8090/~ knuth/fasc1.ps.gz

Re:Additional information

[callipygian-showsyst]

This posting is a hoax! The real Don Knuth would have it in TeX format, not PostScript.

/.ed

[mrwoody]

The next volume will be:
"The Art of Being Slashdotted"

It's been a while.

[robbyjo]

It's been a while. Dr. Knuth already finished pre-fascicle 4. Get it here. It's far from done (well, according to his plan).

Nifty from the Knuth

[gateman9]

Nifty, but mainly from the whole CS angle. And it seems a bit more approachable that the third book was, although some of that has to do with the fact that I was relatively unschooled when I first read them.

It'll be a pleasure to add it to my bookshelf.

Re:Nifty from the Knuth

[HyperChicken]

Adding it to your bookshelf does no good: You have to read it.

Many own, few read

[Ars-Fartsica]

How many people have bought the entire Knuth series just to occupy the moral high ground on their bookshelf? For my money, Cormen/Leiserson/Rivest's "Introduction to Algorithms" is preferred for almost all related material you might want to investigate.

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

[Anonymous Coward]

The Knuth books are about more than the algorithms: They're about philosophy of programming.

No, they really aren't. They are about algorithms.

Knuth isn't God. His books aren't the Bible. He's just a computer science professor who wrote some books on the topic of algorithms.

Yes, the books are thorough. Yes, they are dense and information packed. But no, they aren't the be-all and end-all of Computer Science.

You may now mod me down for speaking heresy.

Re:Many own, few read

[fm6]

I seem to recall reading that TAOCP was originally intended as a single volume. The project grew, because computer science grew as fast as Knuth could write. In the late 70s, Knuth joked that people should please stop doing any research, so he could finish the series!

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!) There's some weird obsession here, possibly characterized by Knuth's abandonment of email and certainly connected with his early retirement.

It's also strange that Knuth still insists providing code for a pseudo machine. I'm a CS flunkout, so my opinion isn't worth much, but this does seem to be a thoroughly obsolete idea. Especially when you consider how many effort Knuth expends redesigning the machine!

Re:Many own, few read

[Anonymous Coward]

Using MIX/MMIX is brilliant.

First, it stops copy-and-pasters. You have to actually read the books to gain knowledge.

Second, it shows the algorithms on a low level. Very good.

Third, as he's said, he doesn't have to update his book when the "language of the decade" changes.

Re:Many own, few read

[gabbarbhai]

And for the rest, its more of a convenience thing. The way it works is, you look in CLR (Cormen, Lieserson, Rivest). If you find useful leads from there, you go follow them, or go to google or citeseer or something.

After a while, you get a little more curious (or a bit stuck with counting things down to the last epsilon), so you go look at Knuth. Finally, if nothing else works, you sit down and prove it.

Personally, Knuth, Graham & Patashnik, and Hopcroft & Ullman have bailed me out more often than AoCP

Re:Many own, few read

[Alomex]

Knuth is stubborn. That is his best and his worst attribute. He should have given up on MIX and on writing volume 4 on his own a long time ago. On the other hand if he weren't that stubborn, he would have never produced the first two volumes or the TeX formatting engine.

Re:Many own, few read

[CEHT]

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

Re:Many own, few read

[thogard]

The one exercise reducing a NP problem to a P problem has me stumped and I can't quite figure it out. Other than that, I've got most of them.

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

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

"But when will it be published?"

[RedWizzard]

But when will it be published? Bookpool does not hazard a guess."

Um, they said 2007. So what, do story submittors not bother to RTFA either these days?

Dear Knuth

[Letter]

Dear Knuth,

After Vol. 4 are you going to do some "prequels?" So 1-4 are actually, say, 3-6, and then the new Vols. 1 and 2 include new special effects capable only in LaTeX2e?

Letter

I DO read them!

[nomadic]

How many people have bought the entire Knuth series just to occupy the moral high ground on their bookshelf?

That's absolute nonsense. I often will take one of his volumes off the bookshelf, put La Boheme on the stereo (the Pappano recording, of course) , pour myself a glass of Le Montrachet '78, and peruse Prof. Bluth's delightful words. You shouldn't be bitter just because you're too uncouth to understand them.

Re:Kill Yr Idols: Donald Knuth

[bkazez]

"So in other words, Knuth produced a product that gives you results that look distinctly worse than if you'd used MS Word, while forcing you to learn a massive amount of practically useless contorted macro language."

I tend to agree with most of the remarks about the quality of TeX's output, but I strongly disagree with the notion that TeX output looks worse than Microsoft Word. Although the font will be normal, although the linespacing will be more standard (even though the pica of extra spacing that's mentioned in this article doesn't exist in TeX), all one has to do is whip out Microsoft Equation Editor and see how it compares to TeX's equations. There's absolutely no comparison -- TeX wins easily.

Question

[Spy der Mann]

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

Re:Question

[rsidd]

Well, there's been cases of repeated last names in science... I just never thought that a person both prominent and low-profile (who in here has studied information theory and text searching algorithms?) would appear on a popular site such as /.

Well, here's another reason he'd appear on Slashdot: he wrote TeX, which is even today the best free typesetting system. And it beats every commercial typesetting system for typesetting mathematics, which Microsoft, Adobe and others don't have a clue about after 20 years of research (indeed, most scientific publishers use TeX/LaTeX). You'll find it on your linux box: among other things, GNU TeXinfo uses it for printable manuals.

And yes, that's still the same Knuth -- he wrote TeX because he was unhappy with the publishers' typesetting of TAOCP.

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:You can already buy some of it

[antispam_ben]

And I'll bet Knuth doesn't slip nearly as bad as Longhorn.

Whichever's out first, I bet Knuth is a lot more stable.

The Childe Knuth

[iJames]

Man. At this rate, he's never going to get to the Dark Tower.

Re:Kill Yr Idols: Donald Knuth

[jjoyce]

if he spent most of the time like a typical "hacker", drinking Mountain Dew and masturbating

Hey now, that was a pretty low blow. Many of us hate Mountain Dew.

If TeX is too hard....

[the_womble]

....and it is for me,

use Lyx, very good quality output - as printout, PDF or HTML and easier to use than MS Word.

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:Additional information is online

[wdr1]

Without Knuth there would be no Google. 'nuff said.

Re:Kill Yr Idols: Donald Knuth

[adam31]

By my calculations, this method is approximately 2,522,880 times more efficient than Knuth's

Why are you getting so worked up about an improvement by only a constant factor?

Theoretically, the methods are equivalent... In fact, as the number of Knuth's books goes to infinity, the overhead of having to call the typesetters each time will overcome the one-time expense of writing the typesetting language.

Eh, mediocre at best.

[Grendel Drago]

Oh, come on. Adequacy has produced some good trolls (though I can't remember any from the top of my head), but this... is just sloppy.

like, for example, page numbering starting on a number other than 1

\pageno=10

I didn't know how to do that. I googled for it. No nine megabytes of C code involved. And a real troll would have seized on TeX being written in WEB, the Pascal-like "literate programming" language that Knuth designed himself. A real troll would have further complained that most hacking is really done using TeX's own macro system, which can be weird and baroque a lot of the time.

And how did "Knuth" become "Bluth" halfway through? If it's a joke about the Mormon animator, follow it through.

And dear god, man, there may be better ways of separating content and presentation---standards-compliant HTML with CSS, anyone?---but MS Word is not it. I've seen documents that have gone through many hands, serious works that involve difficult formatting... and it ain't pretty. Word is simply not a serious typesetting tool. Talk about InDesign or QuarkXPress if you want to go on about that.

LaTeX also allows the use of standard PostScript fonts with a quick

\usepackage{times}

in the preamble, but I kinda like the cm fonts myself.

Also, I'm not sure where the complaints about needing to edit incomprehensible jargon to correct typos came from. Text is represented as... plain old text. When is it any other way? Math is hard to read if it's badly written or you're not used to it, but it's no worse than it has to be, to my eyes.

Is it a sign of the incredible good design of TeX that the Adequacy people couldn't find very many real flaws to harp on? Or does Adequacy simply suck ass? I fear it to be the latter; I have plenty of nits to pick with TeX, but this reads like it was written by someone who heard of TeX once, and decided to write a rant about it. Frickin' weak.

--grendel drago

Re:Eh, mediocre at best.

[tootlemonde]

However for the vast majority of day to day office work, documents are often formatted and reformatted till the 'Aha!' feeling comes.

There was a time when a typewriter was adequate for day-to-day office work. Word processors solved the main problem of typewriters, which was the difficulty of making corrections and revisions. The first word processors used printers that were little more than high-speed typewriters.

Elaborate typography resulted from the invention of cheap laser printers. However, even then, typography was more of a by-product. The main advantage of laser printers was speed. The speed of the laser printer further augmented the main function of word processors by allowing even faster corrections and revisions.

Typography has added an extra level of corrections and revisions. I suspect that today more time is spent fiddling with the typograpy than the content of the document. The reasons is that in the distant past, typesetting lent authority to a document because it suggested that it was important enough to go to the enormous extra trouble and cost of having it typeset. The typeset appearance is now the minimum standard so that a document without a typeset appearance has almost as little appearance of authority as a handwritten version.

In terms of efficiency, the optimal use of a word processor would be with a monospaced font with bolding, italicizing and different font sizes kept to a minimum. Such documents could be formatted in a markup language like Tex or HTML almost as efficiently as in a WYSIWYG processor. The small loss of efficiency would be recovered by the extra flexibility of managing the document as text in version control and content management systems and by making it easier to re-publish it in different formats (e.g. pdf, Web pages).

Moreover, by using style sheets to mark up the document, a document formatter would automatically apply the enhanced typograpy, giving the required appearance of authority.

The missing ingredient is a standard for the appearance for day-to-day documents, which would allow for the definition of style sheets. The absence of such a standard in most corporations indicates that corporations probably don't really understand document management.

The absence of the standard also appeals to another human frailty: the desire to put your own typographical stamp on the appearance of a document even when you did not create the content.

Re:Kill Yr Idols: Donald Knuth

[chthonicdaemon]

I have to say, as a LaTeX user for about three years, and having done my Masters and soon my PhD using LaTeX, that I cringe each time I am forced to use Word (or any word processor for that matter).

It is true that LaTeX has a steep learning curve, but I wouldn't call \section an unintuitive way of inserting a section heading. You say (La)TeX output is ugly? I assume you have never seen the excessive spacing Word frequenly add s between words (and sometimes even between letters!). I assume you have never had to wrestle a figure into place only to have it wrap around to the next page (if you used paragraph or character anchors) or stuck on a page it shouldn't be (if you used page anchors). Those figures cause ugly half-open pages. By the way -- if you hate the default font, just change it! Use Times New Roman (or even some sans-serif monstrosity, if you feel daring) and everything will look a bit more familiar.

I wouldn't advocate the use of (La)TeX for casual users who 'just want to type and select pretty fonts', but for anything more than a few pages, Word falls on its face.

Spoiler

[HiggsBison]

Quicksort shoots first.

Apples to oranges.

[Grendel Drago]

Comparing TeX to PS or PDF doesn't really make sense. PostScript and PDF are output languages, while TeX is a typesetting program. It's like comparing the merits of Photoshop versus JPEG.

I don't think anyone really writes PS directly, unless they're l33t hackers. (There is that tiny snowflake program that prints a different snowflake every time. That's pretty darn nifty.

But little to do with typesetting. You'd want to compare TeX to Adobe InDesign or QuarkXPress, I suppose. Comparing it to MS Word is a frickin' joke.

--grendel drago

Re:Apples to oranges.

[HuguesT]

You really want to compare Word and (La)TeX, they are both document preparation systems that provide you with outlines, tables, figures, indexes, tables of content, equations and general typesetting facilities (styles, fonts, etc).

MS-Word is the archetypal "WYSIWYG" typesetting system, with all of its seemingly low-barrier-of-entry appeal. It is completely state of the art. The limitations of word are not so much due to the model (what you see is *only* what you get) than the implementation.

People have written whole books in Word and even swear by its facilities (e.g. indexing, outline view, etc)

In contrast TeX is more of a "what you mean is what you get" system. It enforces the rules of the Chicago Book of Style for you in a relatively straighforward manner. You enter the data structure of the document, it produces something up to publishing standards immediately. It is incredibly productive but not of obvious usage to anyone. In TeX to produce a document you have to find an editor, a command line and invoke the TeX compiler (yes I do know about things like LyX, TeXShop and the like, they are but a crutch to the TeX afficionado, although they might lower the barrier of entry somewhat).

In Word you just type away. You *will* make stylistic mistakes that TeX would not allow you to get away with, but it does look easier at first glance, and even long-time TeX users have to fight with the system to sometime get the result they would like to see (like "put that damn figure on *this* page, not the other page, dammit!") although what TeX does is usually the correct,proper way.

No prize for deciding which is the eventual winner however, except in the category of "ease of use for single-page, no frills documents", and even then...

TeX is not meant for desktop publishing though. You would not be able to put together a glossy magazine in TeX without considerable efforts, and so doesn't really compare with Quark or Indesign.

For DTP the free alternative is Scribus.

Re:Apples to oranges.

[rssrss]

People have written whole books in Word and even swear by its facilities (e.g. indexing, outline view, etc)

Most of us swear at Word's facilities.

Steve Jobs has read them...

[deunhido]

"It's a pleasure to meet you, Professor Knuth," Steve said. "I've read all of your books."

"You're full of shit," Knuth responded.

From folklore.org

Re:Kill Yr Idols: Donald Knuth

[aquin]

but for anything more than a few pages, Word falls on its face

You have to consider: it is called Word. It could have been called Sentence or Paragraph or even Book.
But it is called Word...

Re:Knuth isn't God..

[unknown_host]

Richard M. Stallman, Linus Torvalds, and Donald E. Knuth engage in a discussion on whose impact on Computer Science was the greatest.

Stallman: "God told me I have programmed the best editor in the world!"

Torvalds: "Well, God told *me* that I have programmed the best operating system in the world!"

Knuth: "Wait, wait - I never said that."

Photo of the cover!

[Admiral Burrito]

Here's a photo of the cover.

Re:Knuth isn't God..

[mountain_penguin]

while Dijkstra was still trying to find the shortest path to the conference

Re:Knuth isn't God..

[808140]

while Dijkstra was still trying to find the shortest path to the conference

Yes, apparently he was told just to go to the conference, but he considered that advice harmful.

Re:Kill Yr Idols: Donald Knuth

[daniel_mcl]

"It's a Turing-complete language, you see, highly useful for people who want to solve the Halting Problem..."

As will be learned in an introductory course in computer science, a key property of the Halting Problem is that it cannot be solved by a language which is only Turing-complete (isomorphic to a Turing machine). There is thus a strong inclination to believe that you do not, in fact, know what the halting problem is and have just inserted a term which you have at some point heard used in conjunction with Turing machines into your essay in a failed attempt to impart a touch of intellectual sophistication. This calls the rest of the piece into question as well; how many times did you gamble on something you didn't understand an manage to produce a brief allusion which is not visibly incorrect?

"... results that look distinctly worse than if you'd used MS Word..."

If your assertion is that Times New Roman and Courier are better-looking than Computer Modern, you're putting yourself at odds with industry and academia alike. It's a noble attempt to take up the mantle of Gallileo, but you must remember than in order to be persecuted for being right one must first be right.

TeX is the best mathematical typesetting system available today, and is used for all major mathematical journals for this reason. As TeX is generally used to produce postscript output, it's quite easy to make use of any postscript font one wishes, but computer modern should really suffice in most cases.

"Like Schubert's Unfinished Symphony..."

The first movement of Shubert's unfinished symphony stands on its own, almost as a sort of program piece, and this is why the symphony is so popular. Nobody expects a third movement, and indeed very few particularly care for the second.

Having shown a complete lack of the most basic knowledge in relation to mathematics, computers, music, literature, and several other areas of knowledge, you should strongly consider returning to school and completing your high school degree in order to help you form coherent, relevant essays if you wish to further pursue book criticism.