Product Details

• Amazon Sales Rank: #114719 in Books
• Published on: 1997-07-17
• Original language: English
• Number of items: 1
• Binding: Hardcover
• 672 pages

Amazon.com
This magnificent tour de force presents a comprehensive overview of a wide variety of algorithms and the analysis of them. Now in its third edition, The Art of Computer Programming, Volume I: Fundamental Algorithms contains substantial revisions by the author and includes numerous new exercises.

Although this book was conceived several decades ago, it is still a timeless classic. One of the book's greatest strengths is the wonderful collection of problems that accompany each chapter. The author has chosen problems carefully and indexed them according to difficulty. Solving a substantial number of these problems will help you gain a solid understanding of the issues surrounding the given topic. Furthermore, the exercises feature a variety of classic problems.

Fundamental Algorithms begins with mathematical preliminaries. The first section offers a good grounding in a variety of useful mathematical tools: proof techniques, combinatorics, and elementary number theory. Knuth then details the MIX processor, a virtual machine architecture that serves as the programming target for subsequent discussions. This wonderful section comprehensively covers the principles of simple machine architecture, beginning with a register-level discussion of the instruction set. A later discussion of a simulator for this machine includes an excellent description of the principles underlying the implementation of subroutines and co-routines. Implementing such a simulator is an excellent introduction to computer design.

In the second section, Knuth covers data structures--stacks, queues, lists, arrays, and trees--and presents implementations (in MIX assembly) along with techniques for manipulating these structures. Knuth follows many of the algorithms with careful time and space analysis. In the section on tree structures, the discussion includes a series of interesting problems concerning the combinatorics of trees (counting distinct trees of a particular form, for example) and some particularly interesting applications. Also featured is a discussion of Huffmann encoding and, in the section on lists, an excellent introduction to garbage collection algorithms and the difficult challenges associated with such a task. The book closes with a discussion of dynamic allocation algorithms.

The clear writing in Fundamental Algorithms is enhanced by Knuth's dry humor and the historical discussions that accompany the technical matter. Overall, this text is one of the great classics of computer programming literature--it's not an easy book to grasp, but one that any true programmer will study with pleasure.

Book Info
Volume 1 begins with basic programming concepts and techniques, then focuses on information structures. DLC: Electronic digital computers.

From the Back Cover

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming.

—Byte, September 1995

I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up.

—Charles Long

If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing.

—Bill Gates

It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers.

—Jonathan Laventhol

This first volume in the series begins with basic programming concepts and techniques, then focuses more particularly on information structures—the representation of information inside a computer, the structural relationships between data elements and how to deal with them efficiently. Elementary applications are given to simulation, numerical methods, symbolic computing, software and system design. Dozens of simple and important algorithms and techniques have been added to those of the previous edition. The section on mathematical preliminaries has been extensively revised to match present trends in research.

Customer Reviews

Painful
Yes, I know, we devs should all pay homage to the great Knuth. I don't dispute it. But I also don't want to read a textbook. That's what this is. And unless you're writing low level algorithm libraries, you have no business reading this book. 'Cause if you can't grasp the basics already, this book will do more to scare the crap out of you than anything else.

For the hardcore only!

Algorithms, Data Structures, Computing Machine, Analysis
This is a classic book on algorithm analysis and also in programming techniques. The first one for which author create a hypothetical computing machine (he call it MIX), his own style to describe algorithms, a machine operation instruction and data representation, an assembly language (he call it MIXAL) for map algorithms and data structures into reality.

In another sense: it's a self-contained book.

Each chapter includes a historical review of concepts and methods.


Important topics
----------------
* Section 1.2. Mathematical basement for algorithm performance analysis. Includes a review of Numbers, Powers, Logarithms, binomial coefficients, and also an example of algorithm analysis using "Kirchhoff's first law" for inputs/outputs (flow to/from each step).

* Section 1.3. Description of the hypothetic computing machine (MIX): memory word, registers, comparison and overflow indicators, input/output device names, machine instruction format, machine instructions.

* Section 1.3.2. Description of the assembly language (MIXAL). Includes an interesting figure on relation between machine instruction codes and assembly language representation.

* Section 1.4.1. Introduce concepts of subroutine and co routine. Co routine is described as a team of sub-programs ideal for multi-pass algorithms (the kind used for processing a stream input).

* Section 1.4.3. Introduce in the field of interpretive routines and simulators. The author tells you how good programmers are at the same time good machine designers (as is the same today with virtual machines and little languages as Java). It includes a simulator program for the hypothetical MIX computing machine. You will learn how a state machine or sequential machine is implemented using a so called Control Routine (complement this reading with section 5.1 of "Computer Organization & Design" by Patterson and Hennessy - see my review for that book).

* Section 2.2.5. Describes the use of doubly linked list data structure by using a discrete simulation example (author use previously reviewed concepts like coroutine and control routine). You learn how the idea of coroutine is a base for discrete simulations. Also, author use what he call a "pseudo parallel procedure": a WAITLIST. This kind of procedure was used during 1960s and 1970s as a multi-task procedure.

* Section 2.3.2. Describe binary trees. The highlight of this section is a "Differentiation" algorithm. The author uses an algorithm to traverse a tree in post-order with each node representing a symbol. He then implements the algorithm using a control routine like the one implemented in Sections 1.4.5 and 2.2.5. The control routine includes a "Jump Table" for processing each node.

In resume, the book describes important topics for past and present programmers. I recommend you to read "Computer Organization & Design" by Patterson and Hennessy as an intro. Then read this one. Also you can complement this read with "Fascicle 1." by Donald E. Knuth, which describes an advanced MIX computing machine called MMIX (a 32 bit hypothetical RISC machine similar to DLX machine used on "Computer Architecture: A Quantitative Approach - 2d edition" by Patterson and Hennessy. Also, "The Art of Computer Programming, Volume 3" will very useful (Balanced Trees algorithm for example, as a "self-reshaping" structure).

Just try sorting and searching with out this book.
This book has saved my bacon several times through the decades. Once I needed to actually build a database package from scratch instead of using a commercial package.

I almost did not buy it when all I saw in it was mostly math. But I was desperate and it paid off. Turns out you could not explain it any other way. I use it primarily for balanced trees. I may try some thing more exotic later.

The set also looks impressive in the library.