|The Art of Computer Programming, Volume 4, Fascicle 5|
Author: Donald Knuth
I am a big fan of The Art Of Computer Programming (TAoCP) and last year recommended the boxed set of Volumes 1-4A as A Great Present for any programmer.
Click on the image to find out more.
It is a remarkable work and it is easy to come to the conclusion that few people could have created anything like it. Its incomplete status is something of an irritation, yet it is also a characteristic of the work. Can it ever be finished? Almost certainly not. Even so the current situation is unsatisfactory as fascicles, which is what Knuth has decided to call chunks of the book, stand in for further work on the main text. It's not that the fascicles aren't serious complex works, it's just they are a confusing mess and generally don't read like the earlier volumes.
Fascicle 5 is the latest one I have attempted to read and I am very disappointed. It is more dense than usual, very difficult to read despite the occasional high spot. There is also no real focus of the book beyond its separate, and only lightly-connected, parts.
The first section is called Mathematical Preliminaries - an addendum to section 1.2 in volume 1. Described as "things I didn't know about in the 1960s", mostly this is about probability theory and Martingales in particular. If you have never understood Martingales, why they are important or useful, chances are you still won't know after reading this. If you were educated in the topics well after 1960 then you probably will be wondering what the fuss is all about - nothing groundbreaking and not particularly well-motivated.
The second section is on backtracking and it is more interesting. However, it is very short and really isn't standalone - you have to read it as a follow-on to combinatorial patterns. If you have met backtracking algorithms, most of us have, then it is still surprising to read Knuth and discover there is so much more.
The third section is on dancing links - something Knuth has made his own. The basic idea is that if you have a linked structure you can make modifications to the links to alter the structure while still leaving the original, now redundant, links in place. What is the advantage of this? Simply that you can now backtrack more easily by restoring the links you didn't delete. The way that the links are changed is complex and interesting to watch, hence dancing links. If you want to have an "easy" introduction to the subject see Knuth's video on the subject:
Is this important? Probably not generally important, but you should still have the basic ideas in your toolkit. This is the largest section in the fascicle and it is almost stand-alone, but it still has ties to other parts of the work.
I can't help but mention the incredible and numerous questions. Some are simple, but a lot of them are research projects in their own right. Take a look if you are in search of a project.
My main complaint about this volume is that it should be with the other volumes and not issued on its own. The mathematical preliminaries in particular do not stand on their own.
It is time that the mess of TAoCP was tidied up, but I doubt it is going to happen any time soon. For more about TAoCP project, see Donald Knuth & The Art of Computer Programming.
|Last Updated ( Tuesday, 27 July 2021 )|