Anany Levitin
INTRODUCTION TO DESIGN AND ANALYSIS OF ALGORITHM
Softcover pp. 562, plus XXIII
Pearson Addison Wesley, Boston, 2007
ISBN 0-321-36413-9

In general about the book

The discipline of algorithms design, analysis and implementation is vast and represents an important part of computer science. It covers many different application areas, types of objects to be processed, requirements, design, and analysis techniques. Accordingly, the broad field of algorithms has developed specialized many sub-disciplines and scientific literature. Because of the vastness of the field, one book cannot be a comprehensive survey. This one gives a panorama map of the landscape of algorithms, highlighting instructive examples selected from this broad field of interest. The main intent of this book is to present basic concepts and techniques selected from a wide range of algorithmic problems. It discusses aspects related to the design of algorithm, how to prove that it is correct, how to measure its performance, and to determine how its performance could be improved. It also covers the limits of computation: problems which cannot be solved efficiently and problems which cannot be solved with a computer, never mind the amount of time allowed. The material in this book is organized into twelve chapters, two appendices, a Bibliography with 152 entries, Hints to Exercises, and a comprehensive Index. A brief step through the content of each chapter will illustrate the broad coverage of this book and give rise to some specific comments:

Chapter content

Chapter 1 (Introduction, pp. 1- 40) defines the meaning of the term algorithm, and involves the reader with the fundamentals of algorithmic solving problems and data structures. Id addition, several particularly important problems such as sorting, searching, string processing and others are briefly discussed.

Chapter 2 (Fundamentals of the Analysis of Algorithm Efficiency, pp. 41- 96) is devoted to analysis of algorithms. The main topics considered here are with general framework for analyzing algorithm efficiency, asymptotic notations, mathematical analysis of non-recursive and recursive algorithms, Fibonacci numbers, empirical analysis of algorithms, and algorithm visualization.

Chapter 3 (Brute Force, pp. 97- 121) concentrates on brute-force as a simplest design strategy. Several applications of the brute-force approach, such as the problems of sorting, searching and matching, dealing with finite sets of points in the plane, and finding an element with a special property in a domain that grows exponentially with an instance size, are considered.

Chapter 4 (Divide-and-Conquer, pp. 123- 156) deals with one of the probably best-known general algorithm design technique- divide and conquer. More details related to applications of divide and conquer algorithm such as merge-sort, quick-sort, binary search, binary tree traversals, multiplication of large integers and multiplication of two square matrices, and solving problems of computational geometry (the closest-pair problem and the convex-hull problem) are given.

Chapter 5 (Decrease-and-Conquer, pp. 157- 196) focuses on a general algorithm design technique, known as decrease and conquer, which is based on exploiting the relationship between a solution to a given instance of a problem and a solution to a smaller instance of the same problem.

Chapter 6 (Transform-and-Conquer, pp. 197- 348) covers a group of design methods that are based on the concept of transformation. The main themes considered here are with presorting, Gaussian elimination, balanced search trees, heaps and heap-sorts, HornerXs rule and binary exponentiation, and problem reduction.

Chapter 7 (Space and Time Tradeoffs, pp. 249- 277) discusses space and time tradeoffs in algorithm design that are of interest for both theoreticians and practitioners of computing. Interesting details about sorting and counting input enhancement in string matching, hashing and B-trees, are given.

Chapter 8 (dynamic Programming, pp. 279- 305) describes dynamic programming as a technique for solving problems with overlapping sub-problems. The topics covered in this chapter include computing a binomial coefficient, WarshallXs and FloydXs algorithms, optimal binary search tree, and knapsackXs problem and memory functions.

Chapter 9 (Greedy Technique, pp. 307- 334) concentrates on greedy algorithm. As an approach it suggests constructing a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. Several algorithms of this type such as PrimXs algorithm, KruskalXs algorithm, DijkstraXs algorithm, Huffman tree and Huffman code, are considered.

Chapter 10 (Iterative Improvement, pp. 335- 377) discusses a problem of finding a solution to an optimization problem by generating a sequence of feasible solutions with improving values of the problemXs objective function. The main themes considered here relate to the simplex problem, the maximum-flow problem, maximum matching and bipartite graphs, and the stable marriage problem.

Chapter 11 (Limitations of Algorithm Power, pp. 379- 414) concentrates on the power of the algorithms. Topics that are treated include lower bound arguments, decision trees, P NP and NP-complete problems, and challenges of numerical algorithms.

Chapter 12 (Coping with the Limitations of Algorithm Power, pp. 415- 463) outlines several ways of dealing with difficult problems. Interesting details concerning backtracking and branch-and-bound algorithms, approximation algorithms for NP-hard problems, and algorithms for solving nonlinear equations, are given. The book also contains two appendices. Appendix A lists useful formulas for the analysis of algorithms, while Appendix B gives a short tutorial on recurrence relations.

Useful for students

Design and analysis of algorithms is an important part of computer science today. This book introduces students to advanced techniques for designing and analyzing algorithms, and explores their use in a variety of application areas. The book is well written and its organization is good. The style throughout is readable, and the explanations are clear and qualitative. It is suitable as a textbook for a course of Algorithm design for undergraduate and first year graduate students in Computer Science and Computer Engineering. This is an important book, and anyone interested in algorithms design and analysis will benefit from reading this material. All in all, I highly recommend this book.