The Art of Computer Programming Books in Order

Knuth establishes the mathematical and conceptual foundations for studying algorithms, then examines basic information structures. Through detailed analysis, programs, and exercises, the volume develops methods for understanding efficiency and organizing data that support the later books in the series.

This volume examines random-number generation and computer arithmetic, connecting programming techniques with numerical analysis. Topics include statistical testing, floating-point and multiple-precision calculation, rational and polynomial arithmetic, and the mathematical reasoning needed to evaluate their correctness and efficiency.

Knuth compares algorithms for ordering data and locating information in tables and files. Internal and external sorting, search trees, digital methods, and hashing receive detailed quantitative treatment, showing how data organization and practical constraints affect the choice of an efficient algorithm.

Knuth turns to combinatorial searching, studying efficient operations on bits and the generation of objects such as permutations, partitions, and trees. Binary decision diagrams and extensive exercises extend the mathematical analysis of algorithms into problems with vast numbers of possible configurations.