Next / Previous / Shipman's Home Sweet Homepage / Site map

Shipman's software books: Knuth's ``The Art of Programming''

This series comprises the three most densely packed guides to the art of programming in my library:

  1. Knuth, Donald E. Fundamental algorithms. Addison-Wesley, 3rd edition, July 1997. ISBN 0201896834.
  2. Knuth, Donald E. Seminumerical algorithms. Addison-Wesley, 3rd edition, November 1997. ISBN 0201896842.
  3. Knuth, Donald E. Sorting and searching. Addison-Wesley, 2nd edition, June 1998. ISBN 0201896850.

These are the bibles of practice for serious career programmers. All the basics of data structures and algorithms, the bedrock on which our software castles are built.

The first volume connects programming to its mathematical foundations, then discusses what programs are and what is common to all of them and some of the ways they vary. The data structures described in the second half should be part of every coder's everyday toolkit. If you are serious about programming, you should know most of these in your marrow, and at least know about the rest.

The second volume develops the various forms of numeric representation and their consequences. The use of fixed-point is uncommon, but Knuth makes a very good case for its superiority in a surprising number of situations.

As for the third volume, it saved my life and my career once. I was working at Tandem in the late 1970s and had finished the machine emulator and the text editor shipped with the first system. For my next project, I was assigned to write a sort package. ``But I don't know anything about sorting!'' I protested. My boss, Mike Green, just told me to go start reading the third volume of Knuth.

The few days I spent reading the introductory material on sorting and searching have been some of the most valuable reading time I've ever spent. Any programmer who takes work seriously should read this section for a veritable firehose of useful techniques with application everywhere.

Quickly it became clear to me that the section on external sorting was directly germane to my project. Knuth clearly described a number of algorithms and their implications for performance. After a little consultation with my boss on what performance limitations to optimize (at that time and with that technology, it turned out that disk seeks dominated the performance equation), I decided that ``replacement selection'' was a good candidate. The program came up pretty easily and its performance was fine for our customers' needs.

That episode made a believer out of me---these volumes are the good stuff!


Next: Shipman's software books: Object-oriented software construction
See also: Shipman's reading list: software design
Previous: Shipman's software books: Selye's work on stress
Site map
John W. Shipman, john@nmt.edu
Last updated: 1999/05/09 19:33:22
URL: http://www.nmt.edu/~shipman/reading/knuth.html