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

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

[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

[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

[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

[Anonymous Coward]

A pseudo machine is actually a very good idea. It lets you present the ideas that you want to present in a fashion that is clear-cut and precise, without relying upon a given platform being available however many years down the track.

Case in point: the first volume of TAOCP was published in the late 1960s. How many systems that were available in the 1960s are still available? None. Even IBM's mainframes have undergone architectural changes between then and now, although they do (or at least should; I don't follow that area closely) maintain backwards compatibility.

With MIX (and now MMIX), though, this isn't an issue. You can take the code from the old volumes and run it on an appropriate emulator without any problems whatsoever.

The goal of TAOCP is to educate. Not to train. The former teaches you to use your brain and apply the concepts to whatever platform you are using. The latter teaches you how to do things on one platform; move you to something different, and you're hosed.

Re:Many own, few read

[fm6]

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

How does it stop c&p? Nobody studies Knuth without a MIX or MMIX emulator at hand.

Besides, if you're stupid enough to study CS without actually reading the code, you have no hope of even BSing your way through a course.

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

Good that you spend all your effort twidling bits, instead of understanding the algorithm?

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

So instead he has to update it for the machine architecture of the decade.

Re:Many own, few read

[gowen]

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

No. Very bad. This just means that the algorithm and the implementation get confused in the readers head. When learning algorithms, the algorithm should be be written in as high a level language as possible, preferably natural language of the student.

Which one of these better explains the bubble sort algorithm:

i) start with the first item on the list
ii) if their places of that item and the next should be exchanged, exchange them
iii) move down the list one place
iv) repeat from (ii)
v) when you reach the bottom of the list, start again from the top, but ignore the bottom element

for (i=0; i<n-1; i++) {
for (j=0; j<n-1-i; j++)
if (a[j+1] < a[j]) { /* compare the two neighbors */
tmp = a[j]; /* swap a[j] and a[j+1] */
a[j] = a[j+1];
a[j+1] = tmp;
}
}

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.

No, I'm New Here

[New Here]

No, I'm New Here

Re:Nifty from the Knuth

[HyperChicken]

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

Re:Additional information is online

[wdr1]

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

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.

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:Nifty from the Knuth

[Anonymous Coward]

Reading it does no good: you have to understand it.

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