×

An introduction to the analysis of algorithms. Foreword by D. E. Knuth. (English) Zbl 0841.68059

Amsterdam: Addison-Wesley. xv, 492 p. (1996).
For years research in computer science was focused on the design of effective algorithms, usually aimed to bound worst-case performance. Even then it was known that to obtain more precise average-case performance bounds requires more complete understanding of the algorithm, compared with merely producing its working implementation. Over the years techniques to obtain results for such essential characteristics have emerged, and mathematical analysis of algorithms matured to the point where it can be included into the standard computer science curriculum. The book reviewed provides excellent introduction to the area.
The book is organized as follows. After introduction three chapters are given, with primary focus on developing basic concepts and techniques. Chapter 2 concentrates on fundamental mathematical properties of various types of recurrences, and four general methods to develop exact or approximate solutions – change of variable, repertoire, bootstrapping, and perturbation – are studied.
In Chapter 3 basic treatment on generating functions is given. Ordinary and exponential generating functions are defined, as well as bivariate and probability ones, and various techniques to manipulate generating functions are explained. Generating functions are shown not only as an analytic tool for solving recurrence relationships, but also as a tool providing a way to count combinatorial objects systematically. In Chapter 4 (Asymptotic approximations) some methods of deriving approximate solutions to problems, or of approximating exact solutions are presented. Application of basic concepts and techniques introduced in these chapters is illustrated in the next 4 chapters. There, properties of combinatorial structures, their relationships to fundamental algorithms, and analytical results are given. Trees (Chapter 5), permutations (Chapter 6), strings and tries (Chapter 7), and words and maps (Chapter 8) are covered in this part of the book. In all chapters essential ideas and results are clearly explained and presented, and references are given for more details. Clarity and readability of exposition, together with a number of exercises and references to related literature makes the book excellent textbook in a course on “Mathematical analysis of algorithms”, as well as a reference or basis for self-study.

MSC:

68Q25 Analysis of algorithms and problem complexity
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
PDFBibTeX XMLCite