Handbook of algorithms and data structures. (English) Zbl 0665.68001

Gonnet, G. H.

International Computer Science Series. London etc.: Addison-Wesley Publishing Company. XI, 286 p. (1984).

This handbook presents in a quite condensed style the most relevant information about data structures used for searching, sorting and related look-up problems which was available when the book was written (around 1983). The resulting catalogue is presented in a uniform and orthogonal setting: each data structure is described informally in words; the operations on it are described using either a Pascal or C code and their performance is expressed in the relevant complexity measure by detailed mathematical expressions presenting far mode details of the asymptotic analysis than is usually found in textbooks. When an average case analysis is presented not only the expected values are given but also a number of higher moments.
The first chapter of the handbook presents the naming conventions used for the information given in the sequel. The reader needs this information in order to understand what the various formulas denote. In the second chapter characteristics of data structurs and algorithms are presented, again in an extremely condensed style (using the now almost forgotten format of van Wijngaarden two-level grammars). The next three chapters deal with algorithmic problems of data manipulation: searching (including many hashing techniques), sorting, selection and priority queues. Chapter 6 deals with a few subjects from arithmetic complexity - it slightly deviates from the character of the rest of the book. The book concludes with four appendices, again containing useful information: the probabilistic models of the most important empirically observed distributions of data; the basic asymptotic expansions used for the analysis of algorithms, a list of references including 683 titles (mostly research papers) on the various subjects treated in the book and an index of terms.
The reader won’t find in the book a justification of the complexity bounds given and the details of the data structures used - that’s what the references are intended for. If you want to know more - go for the sources. In this respect the book is a catalogue and not a text book, but one which is quite useful to have. To bad that it doesn’t cover the discoveries in this area obtained since 1983.

Reviewer: P.van Emde Boas

MSC:

68-02	Research exposition (monographs, survey articles) pertaining to computer science
68Q25	Analysis of algorithms and problem complexity
68W99	Algorithms in computer science
68P05	Data structures

Keywords:

bibliography; data structures; searching; sorting; complexity measure; asymptotic analysis; van Wijngaarden two-level grammars; selection; arithmetic complexity