Handbook of algorithms and data structures. 2nd ed. (English) Zbl 0719.68001

International Computer Science Series. Bonn etc.: Addison-Wesley Publishing Company. XIV, 424 p. (1989).
[For the review of the 1st edition see Zbl 0665.68001.]
The present handbook outlines the fundamental concepts, ideas, methods and results appearing in searching, sorting and selection algorithms as well as in arithmetic and text manipulation algorithms. Many new results, a new chapter on text searching and an expanded bibliography are incorporated in this impressive second edition of the book. It is written at the level of advanced undergraduate and beginning graduate students and offers a coherent exposition for all those who deal with efficient algorithms, analysis of algorithms and data structures. This handbook gives an excellent survey of the state of the art in these areas.
All algorithms are described in Pascal and C followed by the known results concerning the algorithm’s running time and its space requirements in the best, worst and average case. Several hints and tips on how to use a present algorithm are often indicated. To give a feeling for how the algorithm behave, tables which show exact values of complexity measures in selected cases are sometimes presented. Each description of an algorithm ends with an alphabetical list of relevant references.
Chapter 1 and 2 present the basic concepts such as asymptotic notations, complexity measures and the description of an algorithm and of a data structure used in this handbook. Chapter 3 deals with searching algorithms including various algorithms for sequential search, for sorted array search and for hashing. This chapter finishes with a section on algorithms for recursive structures search such as various types of binary tree search, of B-trees, of index and indexed sequential files, of digital trees and of multidimensional search.
Chapter 4 is devoted to sorting algorithms. It includes all known techniques for sorting arrays and other data structures as well as for merge sorting.
The theme of Chapter 5 is the presentation of selection algorithms based on priority queues. Algorithms for the selection of the kth element are described in the last section of this chapter.
Chapter 6 has a somewhat special character and is devoted to a discussion of arithmetic algorithms for polynomial evaluation, matrix multiplication and other arithmetic functions such as multiplication/division of n-digit numbers, binary powering, fast computation of \(\pi,\ln (x),e^ x\), sin(x), etc.
The new Chapter 7 deals with text algorithms especially with text searching algorithms with and without preprocessed text.
The first two appendices at the end of this handbook present some probability distributions arising from empirical situations (Zipf’s, Bradford’s and Lotka’s law, 80%-20%-rule) and a collection of asymptotic expansions of functions and expressions commonly used in the analysis of algorithms.
The last Appendix III presents a bibliography containing 36 entries for textbooks and 1350 entries for papers published in journals.
This handbook is highly recommended for anyone interested in efficient algorithms, analysis of algorithms and data structures. It is an indispensable book of reference for all computer scientists, researchers and professional programmers.


68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting


Zbl 0665.68001