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.

Banner

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.

fasical5

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.

Banner


Python Programming with Design Patterns

Author: James W. Cooper
Publisher: Addison-Wesley
Date: February 2022
Pages: 352
ISBN: 978-0137579938
Print: 0137579934
Kindle: B09D2RKQB5
Audience: Python developers
Rating: 1
Reviewer: Mike James
There was a time that design patterns were all the thing. Not so much now. But Python - does it have [ ... ]



Modern Software Engineering (Addison-Wesley)

Author: David Farley
Pages: 256
ISBN: 978-0137314911
Print:0137314914
Kindle: B09GG6XKS4
Audience: Software Engineers
Rating: 3.5
Reviewer: Kay Ewbank

This book is subtitled 'doing what works to build better software faster' - does it teach you how to achieve that?


More Reviews

Last Updated ( Tuesday, 27 July 2021 )