Browse Books

Reviewer: Harvey Cohn

Each of the 40 chapters in this textbook is based on one day's log from a semester of lectures; the logs were kept by the author's students at Cornell. The author has blended the best features of three classic books [1– 3]. Some instructors using the book may wish for more of a particular topic, for instance geometry or numerical algorithms, but a course must be selective. The list of chapters seems like a list of topics in algorithm analysis required of a Ph.D. student. The topics include searches and sorts, transitive closure and Kleene algebra, heaps, union-find, flow optimization, and matching. Then comes the principal motivation, complexity. The central feature is NP-completeness as applied to Boolean algebras and tree operations. These ideas are brought up to date by chapters on parallel algorithms and the NC-class (the analogue of the P-class). Likewise, the hypercube and the Gray representation introduce state-of-the-art research. The last 10 chapters deal with familiar classical algorithms—such as rank, arithmetic, fast Fourier transforms, and primality—presented as quick overviews, some with an original touch. In summary, every computer scientist should have this textbook available as a reference for its coverage. This book provides the next best thing to having attended the lectures. It includes sets of problems and solutions, and 111 references to the literature. These would be necessary for anyone pursuing a topic in depth.