The first half of a two-volume work on algorithms, this book emphasizes algorithmic techniques for combinatorial problems. Chapter 1 introduces more than 30 problems, with the intent of showing the flavor of the combinatorial optimization problems studied in the remainder of the book. When a problem arises from a real world application, the authors illustrate how to identify and extract an abstract formal problem specification from its informal English description.

Chapter 2 first defines the O(), &OHgr;(), and &THgr;() notations. These formal definitions are accompanied by an informal discussion that provides a good feel for the language used to describe the efficiency of algorithms. The chapter then reviews some mathematical techniques for solving recurrence relations, which are followed by examples of worst-case and average-case analysis. A lengthy discussion of amortized analysis using the specific example of the splay tree is also provided. This chapter assumes readers have a fair amount of experience with the mathematical techniques of analyzing algorithms.

Chapter 3 concentrates on two abstract data types (ADTs): the priority queue and the equivalence class (or partition). For each, the authors discuss the choices and benefits related to various implementations. They give special attention to implementing the operations of a priority queue with a heap, and implementing the UNION and FIND operations of a partition. Finally, some variations of binary search trees (red-black trees and level-linked trees) that better accommodate operations such as range searches are presented. Algorithms in later chapters often use the ADT operations implemented in this chapter.

The first half of chapter 4 concentrates on solutions to problems of connectivity of graphs using algorithms whose basis is the graph traversal (either depth-first or breadth-first). The second half of the chapter is an introduction to computational geometry. Data structures for representing the basic objects of points, lines, and segments are introduced, as are algorithms for determining basic properties of polygons and interactions of geometric objects.

Greedy algorithms are the topic of chapter 5. The greedy method is first applied to the traveling salesperson and knapsack problems. Then the authors use the problems of minimum spanning trees, shortest paths, and Huffman encoding to illustrate that the greedy method can yield globally optimum solutions in some cases. This result prompts investigation of the more general question of mathematically characterizing the structure of problems that are solved optimally by the greedy method.

Iterative methods start with a solution and proceed to refine it in an attempt to derive an optimal solution. This approach is the subject of chapter 6. Often a greedy method is used to provide the initial solution. Problems related to clustering and the traveling salesperson problem illustrate the iterative method. The majority of the chapter is devoted to the problem of finding matchings in graphs and their relation to the network flow problem.

Chapter 7 presents algorithms that use the divide-and-conquer strategy. The mergesort algorithm is used to illustrate the basic technique. Then some geometric applications, such as merging polygons, finding the closest pair, and computing the convex hull are covered.

Chapter 8 examines five well-known sorting algorithms: Shell sort, quicksort, mergesort, heapsort, and radix sort. The authors expend a considerable amount of effort in discussing how to fine-tune each algorithm and giving situations in which each algorithm is especially applicable.

This book is meant for use as a text in an upper-level undergraduate or graduate course, or as a reference for the professional. The reader should be comfortable manipulating dynamic data structures and needs a fair amount of familiarity with the mathematics used in the analysis of algorithms to follow the analyses given.

The authors take particular care to discuss the implementation and coding of each algorithm. At times, the detail is almost overwhelming. What is unusual is that actual running programs, written in Pascal rather than pseudocode, are given. While the distance from a pseudocode description of an algorithm to its actual implementation can be considerable, pseudocode is useful because it can quickly give a feel for an algorithm that might be difficult to explain in words. Some pseudocode is presented in chapter 7, but it could have been put to good use more extensively elsewhere.

The exercises in the text, which seem varied and interesting, fall into four broad categories ranging from short-answer questions to research projects. When a question requires knowledge of a special area of combinatorics or mathematics, this requirement is indicated. Additional self-test exercises are scattered throughout each chapter, starting with chapter 2. This book reads smoothly and provides in-depth coverage of many useful methods for approaching combinatorial problems.