This is an excellent introduction to a fundamental area of computer science: algorithms. It covers a significant number of algorithms rigorously, including techniques for their design and analysis.
This is the second edition of this excellent and very successful book. A new author has contributed, and three new chapters have been added, while two chapters and some sections have been removed. Many new problems and exercises appear in this edition, and many parts of the book have been revised and rewritten.
The book is very well written. The description of the algorithms, in English or pseudocode, is easily understandable. The book can be read by anyone who has limited programming experience and basic familiarity with mathematics, since all the mathematical and algorithmic techniques needed are included. Numerous problems, and exercises that range from simple to advanced, are also included; more advanced material is marked with a star. Extensive references and a bibliography are provided. It should be noted that the authors chose not to provide answers to problems and exercises.
The content is divided into eight parts. The first part provides “Foundations” for the design and analysis of algorithms. It consists of five chapters where algorithms and their role are introduced, and simple algorithms for sorting (insertion and merge sort) are presented and analyzed. In addition, asymptotic notations, and methods for solving recurrences and probabilistic analysis, are introduced alongside randomized algorithms.
The next part consists of four chapters and deals with “Sorting and Order Statistics.” It includes the presentation and analysis of heapsort and quicksort, and the proof of a performance lower bound of comparison sorting methods, as well as the presentation and analysis of non-comparison sorting methods. This part also presents algorithms and bounds for the problem of finding the ith smallest element.
The third part is on “Data Structures,” and consists of five chapters. It presents essential data structures: stacks, queues, linked lists and rooted trees. Moreover, it introduces and analyzes the use of hash tables and binary search trees for dynamic-set operations. It also presents red-black trees for dynamic-set operations, and augmented forms of red-black trees for order statistics and interval maintenance operations.
The next part deals with “Advanced Design and Analysis Techniques.” It consists of three chapters that cover two methods for dealing with optimization problems (dynamic programming and greedy algorithms) and amortized analysis, a technique for analyzing algorithms performing a sequence of similar operations.
The fifth part is on “Advanced Data Structures that support dynamic set operations. It consists of four chapters that present B-trees (disk resident structures), mergeable heaps, binomial heaps and structures for disjoint sets. Amortized analysis is among the analytical tools used in this part.
The next part is an introduction to the topic of “Graph Algorithms.” In its five chapters, the representation of graphs, applications of depth-first search (topological sort and decomposition to strongly connected components), and the computation of minimum-weight spanning trees of shortest paths and of maximum flow, are examined.
The seventh part presents a collection of “Selected Topics” that extend topics appearing in the previous parts. It consists of nine chapters. These chapters deal with several algorithmic issues. Specifically, they present a parallel model of computation along with a suitable sorting method, efficient algorithms for operations on matrices, linear programming, the Fast Fourier Transform, number-theoretic algorithms, string-matching techniques, some computational geometry topics, an introduction to NP-completeness, and approximation algorithms for NP-complete problems.
The last part is an appendix entitled “Mathematical Background.” It consists of three sub appendices, where material on the evaluation and bounding of summations, definitions and properties of sets, relations, functions, graphs and trees and principles of combinatorics and probability theory are presented. This complements Part 1, and is useful as reference material.
This could be recommended as a textbook for undergraduate or graduate courses in algorithms and/or data structures. Due to its extended size, only selected chapters or sections would be included in a one-term course. It can also serve the computer science professional very well as a handbook on algorithms and their design and analysis. Potential readers of this excellent book should keep in mind that due to its inevitably large size, it is rather difficult to physically handle (for example, to carry in a briefcase).
