The Art of Computer Programming, Volume 4, Fascicle 5

Author: Donald Knuth
Publisher: Addison-Wesley
Pages: 320
ISBN: 978-0134671796
Print: 0134671791
Audience: Knuth fans
Rating: 4
Reviewer: Mike James
Another portion of TAoCP. Do you need to read it?

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:

Yoda's (Donald Knuth) Xmas Lecture

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.

To keep up with our coverage of books for programmers, follow @bookwatchiprog on Twitter or subscribe to I Programmer's Books RSS feed for each day's new addition to Book Watch and for new reviews.


Programming Rust

Author: Jim Blandy and Jason Orendorff
Publisher: O'Reilly
Date: Aug 2016
Pages: 400
ISBN: 978-1491927281
Print: 1491927283
Kindle: B077NSY211
Audience: Systems programmers
Rating: 4
Reviewer: Mike James
Rust - it's a hit language of the moment. The language we all love to love. So what could be bet [ ... ]

SQL Server 2017 Query Performance Tuning, 5th Ed

Author: Grant Fritchey
Publisher: Apress
Pages: 966
ISBN: 978-1484238875
Print: 1484238877
Kindle: B07H49LN75
Audience: DBAs and developers
Rating: 4.7
Reviewer: Ian Stirk

A popular performance tuning book gets updated for SQL Server 2017, how does it fare?

More Reviews

Last Updated ( Tuesday, 27 July 2021 )