References for Part One

There are a large number of introductory textbooks on programming. Still, the best source for specific facts about C and examples of C programs, in the same spirit as those found in this book, is Kernighan and Ritchie’s book on the language.

The many variants on algorithms for the union-find problem of Chapter 1 are ably categorized and compared by van Leeuwen and Tarjan.

Bentley’s books describe, again in the same spirit as much of the material here, a number of detailed case studies on evaluating various approaches to developing algorithms and implementations for solving numerous interesting problems.

The classic reference on the analysis of algorithms based on asymptotic worst-case performance measures is Aho, Hopcroft, and Ullman’s book. Knuth’s books cover average-case analysis more fully and are the authoritative source on specific properties of numerous algorithms. The books by Gonnet and Baeza-Yates and by Cormen, Leiserson, and Rivest are more recent works; both include extensive references to the research literature.

The book by Graham, Knuth and Patashnik covers the type of mathematics that commonly arises in the analysis of algorithms, and such material is also sprinkled liberally throughout Knuth’s books. The book by Sedgewick and Flajolet is a thorough introduction to the subject.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, Reading, MA, 1975.

J. L. Bentley, Programming Pearls, Addison-Wesley, Reading, MA, 1985; More Programming Pearls, Addison-Wesley, Reading, MA, 1988.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, Cambridge, MA, 1990.

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1988.

B. W. Kernighan and D. M. Ritchie, The C Programming Language, second edition, Prentice-Hall, Englewood Cliffs, NJ, 1988.

D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition, Addison-Wesley, Reading, MA, 1973; Volume 2: Seminumerical Algorithms, second edition, Addison-Wesley, Reading, MA, 1981; Volume 3: Sorting and Searching, second printing, Addison-Wesley, Reading, MA, 1975.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

J. van Leeuwen and R. E. Tarjan, “Worst-case analysis of set-union algorithms,” Journal of the ACM, 1984.