The Art of Computer Programming: Fundamental Algorithms v. 1 [Hardcover]

Chapter 1. Basic Concepts

Chapter 1 starts with a Section which considers what is an isn't an algorithm, and the properties that an algorithm must have. This section closes by offering a mathematical definition of a computational method, "by which the concept of algorithm can be firmly grounded in terms of mathematical set theory". This gives a hint as to what's next! The second Section of Chapter 1 provides a vigorous and intensive overview of the mathematics required for being a practitioner of computer science: induction, powers, logs, sums, products, integer functions, elementary number theory, permutations, factorials, binomial coefficients, harmonic numbers, Fibonacci numbers, generating functions, algorithm analysis and asymptotic representations. Phew! Three thousand years of mathematics are covered in a breathtaking 100-and-a-bit pages and are tested by an almost unbelievable 390 questions, all with answers! The third Section of Chapter 1 covers MIX, an artificial assembler language. My view is that understanding assembler is critical, not optional! To call yourself a computer scientist, or even software engineer, without having at least a working understanding of what your software is actually instructing the processor to do is akin to calling yourself a car mechanic when you don't know how the engine or transmission work! Those few ignorant "reviewers" who gripe about MIX prove that they haven't actually read the book, but wish only to associate their names with someone far more worthy than themselves because as Knuth himself admits: "... MIX is quite obsolete [and will] be replaced ... by a new machine called MMIX ... [which is] a ... reduced instruction set computer" [p124]. He goes on to admit that this will take "a long time". Being able to work with MIX, however, will prepare you to start working with many real-world commercial processors. Finally, a completely artificial construct such as MIX has far more value than creating an artificial high level language as one other reviewer has suggested. Learning the syntax and keywords for any non-trivial high level language, handling control flow, arithmetic, storage, conversion and IO, would take a much larger section than the 40-odd pages that Knuth allocates (even my 1978 edition of Kernigan and Ritchie's "C Programming Language" is over 200 pages!). MIX's application to investigating permutations is also explored in this section. The last Section of Chapter 1 looks at fundamental programming techniques : subroutines, coroutines, interpreters and IO, closing with a short history and bibliography of these techniques.

Chapter 2. Information Structures

Section 1 of Chapter 2 is a short introduction illustrating a linked list, using a hand of cards. Section 2 of Chapter 2 covers: stacks, queues, deques (double-ended queues), sequential allocation ("pushing" items on a stack), linked allocation, circular lists, doubly linked lists, arrays and orthogonal lists (rows and columns). Section 3 of Chapter 2 describes binary and non-binary trees, mathematical properties of trees (free trees, oriented trees and calculation of tree path length), and ends with a description of linked lists and garbage collection. No mention of red-black trees, though. Section 4 of Chapter 2 describes multilinked (nested) structures. Section 5 of Chapter 2 describes dynamic storage allocation and some algorithms for allocation/reallocation. Chapter 2 closes with a history and bibliography of the information structures and algorithms which it describes.

Following the Answers to the Exercises, there are two Appendices, one presenting a table of fundamental constants and numbers, the other offering an index of notations.

Throughout this book, Knuth explains the mathematics extensively, offering not just usage of the algorithms and structures which he describes, but proofs of correctness, investigations of efficiency of speed vs space, references to further material on every page and more than 900 questions (and answers). To paraphrase Gates' quote on the back "You should definitely send me a resumé if you can answer all the questions!"

The main drawback is that if you want to work through the example questions, then you need to learn MIX and get your hands on a MIX simulator. I've nothing against learning assembler, but this is 1960s assembler, not something "nice" like 68K.

Knuth is working on an updated version, but it'll praobably be years before it's ready. I wouldn't let that put me off buying these books though.

Paul Floyd