The Art of Computer Programming

“The Art of Computer Programming” is the classical series of books on algorithms. Donald Knuth started working on it in the 1960’s and has presently published the first four books of the series. You might think that’s a long time for four books only – but the result proves him right in taking his share of time.

The books are exhaustive in covering their topics, with deep and long historical remarks, many exercises that show details or applications not mentioned in the text, and there are complete solutions to each of the exercises. Finally, the text itself is written in a very clear style, looking for a balance between mathematical rigour and standard language slang to bring the important issues to your memory. There are a lot of images and graphics to help you visualise what’s going on, and the typesetting is a most beautiful thing to look at. All in all: it’s a great textbook on algorithms. And what you find there will not get old. Languages come and languages go, there will be one trend after the other – but the content of “The Art of Computer Programming” will stay.

The typesetting is one of Knuth’s specialties. These books are the reason why \TeX has been invented. Knuth was not satisfied about the look of the first edition in the 60’s, so he told a student to program a typesetting for mathematical formulae as his graduation thesis. When the student struggled with this task, Knuth stopped working on his books and got to programming himself – and already five years later, \TeX did the job (Here’s a German article from the weekly magazine Der Spiegel on this and on Knuth himself). By now, \TeX is the standard way of typesetting science articles and books, it’s open source and it has a solution for every typing problem you may come across – all thanks to Knuth.

This also shows the way Knuth wrote his books: he finds a topic he wants to write about, he learns it exhaustively and than prepares it in such a way that everyone can use it. This is also what makes reading his books such a pleasure.

A couple of years ago, I dived into the chapter on random number generation, especially the “Do”‘s and “Don’t”‘s of choosing your favourite algorithm for random numbers. The part on statistical tests showed me the boundaries of the books as well: because of my background in statistics, I found the section on the basics of testing rather shallow – but then again, it’s not a book on statistical theory, it’s a chapter about testing random number generators. And on this particular topic it does what it wants to do amazingly well. The actual tests are presented down to every necessary detail, and if you want to know more, go to the exercises and to the literature mentioned in the solutions to the exercises.

Right now, I have found an interest in sorting algorithms. Not because I need to sort anything, but because this topic interested me already while hearing introductory lectures on algorithms. Of course, I learned the standard algorithms then, I know about the speed of bubblesort, quicksort, mergesort and heapsort, I can type them down in my favourite language anytime… but I have become curious about the principles behind them, and in particular a deeper analysis of these and other algorithms. Different applications call for different ways of sorting after all. So, I started working through the corresponding chapter of Knuth’s work.

In November, I believed I had found a small error in one of the exercises. I reported this to the author via e-mail, and just a couple of days later, I realized I was wrong. To be honest, I realized the remark in my e-mail was rather stupid. But now, I have received a letter by Knuth where he explains my error again to me by showing me another example, working through the algorithm for me and directing me to other parts of the book that might help me about this point. That letter was awesome! I can’t estimate this high enough, since Donald Knuth is well over 70 years old now, he is working 24/7 on finishing his series – and yet he takes the time to reply to mail that reaches him and pointing out stupid errors that people have made.

I found remarkable as well, that Knuth doesn’t use e-mail anymore (you can find reasons for this on his homepage). My mail has been printed by his secretary and he wrote his answer with a pencil on it. His secretary then mailed back the answer to me by snail mail. I’m not sure if that actually saves his time, but it most certainly doesn’t break his concentration once every ten minutes. And it gave me an autograph of the author 🙂

The plans for the rest of this series can be found on Knuth’s homepage, as well as many errata (few of them are actually correcting the contents or meaning of the text, most are tiny typos or remarks on additional literature – another proof of how good the base of the text really is). I hold up my hopes that Knuth will stay healthy for many years to come. Noone else will have the stamina to finish this wonderful set of books. And I’m looking forward to Volume 4B. Sadly, there is no date for when it will be published. Personally, I am very much interested in the final parts of Volume 4 on NP-hard problems and on recursion. That would probably come in Vol. 4C or even later. Knuth’s own hopes are to finish Volume 5 in 2020… historical evidence rather makes me doubt that…

We’ll see what comes next there. I look forward to encountering new things in these books that “will make my day”.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s