Knuth's Volume IV Preview Available Online

ahto writes: "The first section of volume 4 of Knuth's The Art of Computer Programming is available for peer review (and the $2.56 finder's fee for every typo is still there :)." Knuth's series-in-progress made a lot of people's lists when it came to assembling the perfect collection of library books for computer science; now you have a chance to make the next one better. If you can find any mistakes, that is.

Knuth Books and software patents !!

Knuth books are the material proof that software patents are stupid. I mean 99% of what you need to create a software is in Knuth Books; every useful algorithme, sorting, searching, tables look up, indexing methods are there, all the basic.

It's the proof that nearly everything has been said in that field, and patenting software is in fact patenting "the function" and not "the organ" !

Not a preview of Volume 4

This isn't really a preview of Volume 4: Combinatorial Algorithms. It's an "Addendum to Volume 1 (tutorial on MMIX)" as stated on Knuth's TAOCP page under Errata for Volume 1. Knuth's TAOCP page = http://sunburn.stanford.edu/~knuth/taocp.html

typo on page 1!

ok, so it took me about 20 secs to find #1. Did he even proof read it at all? Could become kind of expensive for him...

But then again, it was in 7.2.1, not 7.2.1.1, so maybe it doesn't count?

TAOCP and Thanks For All The Fish

Knuth's books were both joy and pain to read. The mathematical depth, the connection of math to algorithms and algorithms to code, all of those were wonderful. But man was that appallingly ugly spaghetti code for the pseudocode parts and a baroque ugly machine model and assembly code for MIX. It would have been *much* more usable, as well as much more accessible, if the pseudocode had been written somewhat cleanly, perhaps in ALGOL (a language designed years earlier for expressing algorithms, that had structured programming conventions like loops instead of Knuth's jump-in-or-out-of-the-middle and test-at-the-bottom goto colas), and for the places where explaining in low-level assembler is useful (which it often was), using some relatively clean design instead of something deliberately complexified. MIX is basically even less readable than the PDP-10 assembler in HAKMEM [cmu.edu] (jargon entry) [astrian.net] MIT doc.

Not only do these things make the book unnecessarily hard to read when you're learning stuff for the first time, because you have to pay attention to the complexity of the coding style instead focusing on the ideas that the code is expressing, but it makes it even harder to use as a reference book when you're no longer in the midst of an undergraduate heavy reading phase and just trying to find out about the kinds of algorithms that apply to the problems you're solving.

If you were writing something like this today, it's a tossup whether the right language to use for the assembly portions would be the ugly but well-known and widely available Intel 8086 assemblers, or Java Bytecode which are a simpler model for a virtual machine.

Cool

Hmm, 2.56 per error. Guess I'll get to reading!

What about Vol. 5 / 6?

I have the first three volumes (the dedication is classic), but looking in the jacket I saw more than just the first 3 volumes listed. I recall seeing a volume on parsing (volume 5) (?) Maybe it was in a nightmare b/c I have a CLI project coming up :P

For a moment there...

I thought this was the fourth -edition- of "The C Programming Language," not the fourth -volume- of "The Art of Programming," and found myself wondering...

If the first edition is the Old Testament, and the second edition is the New Testament, then the third -might- be called the Book of Mormon...then what would be the fourth edition?

These are the questions which keep me up late at night...

It's the writing!

I've always thought that the truly amazing thing about Knuth's books is the writing. Few writers, be they technical writers, journalists, or novelists, write as clearly.

Wait, is this really the fourth volume??

I thought that the first three published were actually volumes 4 through 7, and that now he's going back to start with Episode 1. I mean Volume 1.

Either way, he's been writing it long enough that you could subtitle it "The Phantom Menace"

-JTB

TeX and Mr. Knuth

Another one of Knuth's major contributions is the creation of the TeX text formatting package.

The mathematical expression output of TeX is incredibly elegant and has yet been matched by any other text formatting package, especially the (comparably) utter filth produced by Microsoft.

In a pre-TeX world, mathematical typesetting was extremely costly and time consuming. TeX had in fact revolutionized the world of creating scientific documents. It is to mathematic/scientific writing what C is to software development. Its use is widespread that in most universities, it is absolutely required that any kind of academic paper in a science faculty be produced with a TeX-derived formatting package.

The coolest thing is, inventing TeX is something Knuth hardly mentions, let alone brags about. It seems to me that Knuth considers TeX as "something he cooked up a few years ago".

Coming soon...

In a effort to keep up with the sludge that is released every day. Dr. Knuth has annouced the following for immediate release:

• The Art of Computer Programming for Dummies.
• The Art of Computer Programming: From the Ground Up. (with Herbert Shildt)
• MAXIMUM STRENGTH! TAOCP

Seriously, though. Thank you, Doctor, for taking the time to get it right.

A good resource for learning the math?

I do developement in both Windows and Linux in C, Perl, VB, and Java. I have been programming on various systems from childhood, but I am self tought. I have picked up Knuth and I find the math a bit intimidating. I never remember having to study in math class in high school, but ihas been about 5 years sinse I have really studied. Can anyone point me at a good reference to get up to speed on the kind of math encountered in this series? I am very, very interested in learning, but I am not sure where to start. I have your basic advanced high school math background. Any suggestions?

Is it only available in TEX format?

and is there a way to save diagrams and expressions using latex2html

knuth is how old?

I'm not sure how old mr. knuth is but I hope he's able to complete his task. I admire greatly his project. the way that the science of computing advances faster than any other science would seem to make something like this nearly impossible. as it is Mr. knuth already has plans to go back over the previous volumes to update them for new technology. eventually you approach a point where anything you write down is obsolete the next day. even with something as fundamental as the algorithyms he describes is in need of update.

This leads me to think about what might happen once knuth has passed on. I'm in no hurry for him to die mind you but the text are more important or he wouldn't bother devoting so much of his life to them. something like this begs to be continued beyond the author. I think the majority of you know what I'm leading to. Open sourcing the books once mr knuth is no longer able to maintain them, I'm not trying to be greedy. I would eagerly pay for them (once I feel I'm at a level where I felt i had a chance of understanding them) I'm only worried that unlike the other works described on Mr knuths page (einstein and relativity, feynman and QED, etc...) TAOCP would quickly become useless to future generations. I don't think I, or mr knuth, or anyone else here would like that to happen.

Re:knuth is how old?

Here is Don Knuth home page, it answers some of you questions. He has retired from his job, and has decided not even have an email address, as he wants to finish his Encyclopaedia. He considers it rightfully as the work of his life.

http://www-cs-faculty.stanford.edu/~knuth/

Interesting Metric

Ask your average Windows programmer about Donald Knuth. Then, ask your average Unix/Linux programmer about Donald Knuth. I think you will notice an interesting pattern emerge. IMHO, if you haven't read Knuth's work, you aren't a programmer.

recommendations of other books

If you don't get the hang of Knuth's books (I don't), here are some alternatives that serve both as good introductions and excellent references:

• Abelson and Sussman: Structure and Interpretation of Computer Programs. This book covers a lot of ground when it comes to programming, implementation of programming languages, and the use of abstraction in software development.
• Cormen, Leiserson, and Rivest's algorithm book is an excellent modern exposition of algorithms and concepts in algorithm development.
• Russel and Norvig's "AI -- A Modern Approach" is an excellent textbook covering logic, search, and AI.

Also very relevant to modern computer science are the following books:

• Duda, Hart, and Stork's "Pattern Classification" is also a book computer scientists should know, but rarely do.
• Strang's "Introduction to Applied Mathematics" covers elementary material in applied math that every scientist (computer or otherwise) should know by heart.
• Gershenfeld's "The Nature of Mathematical Modeling" is a neat, if somewhat quirky, book at the intersection of mathematical modeling and computer science.

If you have recommendations of other introductory books with a similar style, say on automata theory, string algorithms, number theory, combinatorics, etc., please do share them.

Speaking of algorithm texts...

I would really really like to see a text that treats algorithms such as markov chain monte carlo, simulated annealing, evolutionary algorithms, genetic algorithms, etc. in one volume. They all seem related in some way, and it would be nice to see a book treat them all comprehensively in a way that is still useful for application. Does anyone know of such a text? I guess maybe it's better to buy separate texts on each topic.

It Does Exist!

Man, all this time I thought volume 4 was an urban legend.

How do I view it?

Winzip just opens it and asks what kind of files I want to add to the archive!?!?

There an html or pdf or gasp text version floating around anywhere?

*wonders why you need to gzip files when apache's mod_gzip does it for you* =)
Yes, I run win98 at work

Help, please?

Yes, I'm lame when it comes to text formatting. I am a PDF/RTF/Word (yuck)/ASCII kind of guy.

Can someone please advise me as to either one of the following? Thanks in advance.

• A .ps reader for Windows andLinux/KDE
• A .ps => RTF or .ps => PDF conversion utility (I have a licensed copy of Acrobat Exchange 3.0 but don't really know how to use it beyond printing PDF documents)

I own The Art of Computer Programming vols. I, II, and III. I bought the first two back in 1987 while attending the university; the third I bought two years ago. I fondly remember saving my pennies to buy the first two; I can't wait to have a look at IV.

Cheers!

E

Mistakes or Typos?

If they're paying for mistakes, can I claim a prize for his dissing "goto"?

If they're only paying for typos, nevermind.

This is great

Knuth's books are timeless. Java, C++, C, Fortran... it's all pretty irrelevant. If you spend some time with Knuth's books it reduces the rest of the books on programming to piddly details that need little time.

How do I unzip this file?

Okay, I'm new to gzip--and a Windows 98 user.

How do I read the .gz file? I tried using Winzip 8.0, but got the message

Cannot open file: it does not appear to be a valid archive.

Then I found www.gzip.org [gzip.org] and downloaded the Win98 executables. But I can't seem to get them working on my computer. Moreover, the documenation says explicitly that Winzip handles all .gz files: well, not the fasc2a.ps.gz file.

Then I downloaded win-gz [hiwaay.net] and ran it. Win-gz claimed that the file (fasc2a.ps.gz) was not gzipped and refused to unzip it.

Thinking that the file might have somehow become corrupted on download, I downloaded the file a second time. The results were the same.

Does another Win98 user have constructive suggestions for gunzipping?

A Reader's Guide to TAOCP?

Knuth's TAOCP has amazing depth of the subjects it covers, but it's a harder read than it has to be. Lets start with the decsion to use abstract assembly instead of psudocode or a C like language. It would also be nice to have more explaination and background reguarding the problems list, partularly the more difficult and unsolved ones.

I would love to see someone publish a reader's guide to TAOCP to help more programmers get more out of this great treasure. Like the Reader's Guide to Keynes' General Theory of Employment, Interest, and Money has helped economics students understand a similar masterpiece in their field.

Programmers should be able to understand the material, but a tall glass of water makes the pill a lot easier to swallow.

Finders fees

So, what's the finder's fee converging to? TeX was heading for pi, METAFONT for e...

I reviewed volumes 1 to 3

Here's my brief review of The Art of Computer Programming [dannyreviews.com].

Danny.

Finder fee?

(and the $2.56 finder's fee for every typo is still there :)."

Man! I wish that was availiable for Slashdot.. I'd be rich!

Re:Finder fee?

Man! I wish that was availiable for Slashdot.. I'd be rich!

You don't get paid for any typos that you make yourself.

True Type Fonts!

I assume it will be available as a MS-Word doc. After all, he just loves those True-Type Fonts!

Notes on the text

This is not a draft of volume IV. This is a draft of a section of one chapter in volume IV, namely section 7.2.1.1.

Dr. Knuth writes: "This is a section of a long, long chapter on combinatorial algorithms. Chapter 7 will eventually fill three volumes (namely Volumes 4A, 4B and 4C), assuming that I'm able to remain healthy."

This particular section deals with generation of combinatorial patterns and was released for public review in hope to winnow the most egregious errors before it's released; the subject is so extense that Dr. Knuth felt this was one of the best ways to improve this 67-page section.

I've read the first four or five pages and it's impressive, as always. Heavy on the math from the first page. Either way this will make for very enjoyable reading (if you're in hyper-nerd mode).

Cheers!

E

$2.56?

I think the reward is actually higher than that now. For those who don't know, Knuth offered to pay 2^n cents for the nth error. I vaguely recall reading that he paid out the $10.48 reward.

Pretty damn gutsy thing to offer. Imagine if there'd been 30 errors...

Forth edition?

I am so happy to see new books being written about the Forth programming language, and by Knuth no less!
I was begining to worry that Forth was a dead language.

(Score:-1, Really Bad Pun)

Knuth's MMIX VM could compete with .NET/Java...

MMIX is a 64bit VM instruction set and is as good an abstact machine as any other. We don't need garbage collection built into the op codes as the JVM and .NET VM has. We just need a uniform virtual machine in which we can target gcc's code so we can run the code on any machine. There is already a port [bitrange.com] to Knuth's MMIX already in GCC. Does anyone know of a VM that jits MMIX?

*sniff*

Oh my, oh my.

I've been following the saga of volume 4 for twenty years or so now. In the early 1980s I got a math degree at Caltech, and during my stay there I developed a deep love of combinatorics and combinatorial algorithms that stays with me to this day.

I even had the opportunity to ask Knuth (who gave a talk there circa 1983) about volume 4, and it was clear that he hadn't given up on eventually returning to TAOCP.

The Knuth books have always had a treasured place on my bookshelf, but I never stopped hoping that I might someday see Volume 4. Yes, yes, it's only the first fascile. I've known about the fascile plan for the last few years, but it's still something quite different to see the first one. On my screen. Not next millineum, not next year, not next month or week or day, now.

*sniff* It's enough to almost make a geek cry.

--j

TAOCP's Legend

It's been a long wait since the first three book of TAOCP came out (in the 80's I suppose). Knuth said it would be a 7-volume series. We always wait for the rest to come out. Here's volume 4. You could check out [stanford.edu] what will come out for volume 5-7. The contents for volume 4 is there too (including the erratas of vol 1-3).

He said that he'll spend his retirement to write the rest. Wow. Check out his homepage [stanford.edu], probably you could help him [stanford.edu]. If you could give him a "significant suggestion", he'll reward you for 32c. If only ask slashdot offer the same prize for each highly modded post. :-)

Caveat emptor: His book is not for the faint-hearted. It's full of math & logic -- but it's wonderful.

don't rely just on Knuth

Knuth is clearly very smart, and his books have a lot of neat nuggets in them. But I think both the perspective and the presentation are very old-fashioned. I'm not just talking about MIX or his pseudocode, but also the kinds of problems he chooses and the depth to which he covers topics that really aren't relevant to most people anymore.

Knuth's volumes probably should be on your bookshelf. But for learning about algorithms, I think you are better served with a more modern textbook, which focuses on teaching techniques and approaches. And for any particular specialty (string matching, combinatorial algorithms, etc.), there are also lots of books that are more relevant and more complete.

other formats??

is it available in any other formats beyond postscript?

thanks.

Re:Knuth books = martian != programming

Back when he started people had to know this stuff in order to be able to program.

These days with wizards and even libraries the average "programmer" can't really program, all they do is paste a bunch of stuff together.

I would say that less than 1% of today's programmers could do the hard core stuff like design an efficient file storage system or a compiler.

Extended trilogy

Hopefully it won't be as disappointing as another Trilogy extension that we all know and have come to despise.

Careful. There's a damn fine extended trilogy most of us know and love, written by Douglas Adams.

Now if Knuth told us that he'd originally conceieved the 4th book before the first 3, or that he was getting special effects or merchandising consults to work with him, well, yes, then it would be time to worry...

trilogies ?

another trilogy extension

Ursula le Guin's Earthsea trilogy [amazon.co.uk] ?
(if you're the age I am, and read the first three long ago, then go and find the more recent fourth book - very different, and well worth the read)

TAOCP is a 7 volume set - always has been. He just took his time getting around to >3.

OTOH, Trilogy [trilogy.com] (capitalised) and CML should be burnt at the stake. 8-(

Re:Sad that he's never learned while loops

how many assembly style languages, a la MIX (or the RISC based MMIX) have a while loop structure? On a fundamental level, GOTOs or jump instructions are neccessary. Granted, utilizing them in a high level OO language is no good. But to truly understand and see the algorithm just a couple of steps above the machine.. they simply must be there...

Re:Sad that he's never learned while loops

I studied Volumes I and III for my Ph.D. comprehensive exams. They are incredibly dense. You can spend an evening trying to understand a three-line answer to one of his 30 point questions. (Or that's how long it took me, anyway.)

I agree with the comment about gotos. I didn't really understand many of those algorithms until I translated them to more conventionally structured code.

Re:Knuth books = martian != programming

Knuth does computer science, which is kind of programming for mathematicians, not martians, (while both groups might share some characteristics :-)

However I still wait to see someone who had time to work through all three existing volumes, and completed the tackable exercises.
So as a course for computer science, I think this series is a failure, as it covers simply too much. Perhaps one should regard it more as a encyclopedia.

Re:Sad that he's never learned while loops

> I think somebody ought to submit every single "goto" in his book as a typo, and claim a few hundred bucks. I grew up on gotos, yet I find it astoundingly harder to comprehend an algorithm expressed in that fashion.

<sarcastic>
Yep. And he should use the libc and malloc.

Hrmmm, no. He should use a garbage collected language, as memory managment would obscure the algorithm.

And, well, he should use all those nifty things that are present in all 'modern' languages. Lists, arrays, hash tables, strings.

Templates. Yep, templates too. I am sure that many algorithm would be simpler with templates.

Maybe he should use perl. There are so many nifty things that can be done with a couple of perl lines.

Of course, nobody would really know what is going on inside, but, well, the algorithm would be much easier to understand.
<sarcastic>

Seriously, Knuth want his readers to fully understand what a computer is at the software level. As soon as you throw high level constructs in that, you are weakening the point. No computer knows hot to do a (real) loop at the fundamental level, so his formal representation is not going to include loops.

Maybe, in 20 years, C will be totally outmodded. C++ too. May C# will have crunched java. Maybe C# will have morphed in yet-another-basic from Redmond. Maybe impertive langugaes will be mostly dead, and we will writing formal specification in an XML-like language. Or maybe emacs will finally be the OS, and lisp the language of choice. Or prolog. Or functional languages will have won so many competitions that only the fools would not use them.

And Knuth will still be working on TAOCP. At least I hope. And he will still be using an abstract machine language, because he talks about what the machine *really* are...

If it is too hard for you, there are plenty of books out there that don't use assembly.

Cheers,

--fred

Re:all hail the Jewish masterrace!!

Most people forget that the Jewish people and the Palestinian people are actually the same people; at some point eons ago a group of jews broke away from the "pure" jewish religion and gradually through the ages islam came to be. The Jewish shunned them, naturally.