From the authors' preface: ``The study of algorithms is at the very heart of computer science. In recent years a number of significant advances in the field of algorithms have been made. These advances have ranged from the development of faster algorithms, such as the fast Fourier transform (FFT), to the startling discovery of certain natural problems for which all algorithms are inefficient. These results have kindled considerable interest in the study of algorithms, and the area of algorithm design and analysis has blossomed into a field of intense interest. The intent of this book is to bring together the fundamental results in this area, so the unifying principles and underlying concepts of algorithm design may more easily be taught.'' The book has twelve chapters. In Chapter 1 several models of a computer, the random access machine (RAM), the random access stored program machine (RASP), and the Turing machine, are considered. These models are compared on the basis of their ability to reflect the complexity of an algorithm. A high-level language called Pidgin ALGOL is introduced as the main vehicle for describing algorithms. The complexity of a Pidgin ALGOL program is related to the machine models. Chapter 2 familiarizes the reader with elementary data structures such as lists and stacks. These structures are used for representing sets, graphs, and trees. Detailed explanations of recursion and dynamic programming are given. Chapters 3 to 9 provide a sampling of the diverse areas to which the fundamental techniques of Chapter 2 can be applied. Two important related problems, sorting a sequence of elements and selecting the kth smallest element in a sequence, are considered (Chapter 3). Seven fundamental operations on sets are studied, which are characteristic of many searching and information retrieval problems (Chapter 4). In Chapter 5 are discussed some of the principal graph problems (the problems dealing with the connectivity of graphs) that have solutions that are polynomial in the number of vertices of a graph. Included are algorithms for finding spanning trees, biconnected components, strongly connected components, and paths between vertices. In Chapter 6 the asymptotic computational complexity of matrix multiplication with elements chosen from an arbitrary ring is investigated. In Chapters 7 and 8 are studied the Fourier transform, its inverse, and its role in computing convolutions and products of various types. An efficient algorithm called the FFT for computing the Fourier transform is developed. The convolution theorem is proved. An efficient algorithm for convolution using the FFT is developed, and this algorithm is applied to symbolic multiplication of polynomials and to integer multiplication. It is shown that certain polynomial and integer operations, such as division and squaring, require the same order of time as multiplication. In Chapter 9 are presented several techniques for solving pattern-matching problems of the form: let a text string x and a set of pattern strings {y1,y2,⋯} be given; locate either an occurrence or all occurrences of pattern strings in x. A remarkable theoretical result is stated, namely, that any pattern recognition problem that can be solved by a two-way deterministic pushdown automaton can be solved in linear time on a RAM. Chapters 10 to 12 discuss lower bounds on computational complexity. The material in Chapters 10 and 11 draws heavily on the concept of Turing machines. In Chapter 10 is given evidence that the class of nondeterministic polynomial-time complete problems is quite likely to contain only intractable problems (if a problem cannot be solved in less than exponential time, then the problem should be considered completely intractable). This class of problems includes the traveling salesman problem, the Hamiltonian circuit problem, and integer linear programming; all problems in the class can be shown ``equivalent'' in the sense that if one problem is tractable, then all are. In Chapter 11 are developed proofs that the emptiness-of-complement problem for two classes of extended regular expressions is intractable. Finally, in Chapter 12 the concept of computational difficulty is related to notions of linear independence in vector spaces, with techniques for proving lower bounds for much simpler problems than those considered in Chapters 10 and 11. Numerous exercises are provided at the end of each chapter.
Reviewer: Tetruashvili, M. [form MathSciNet]