![[p1]](pi12.gif)
rating, with being a book that has little to offer, being a book with marginal impact, having significant contribution, and being a book that must reside on the serious developer's shelf.
Tom is a consultant specializing in the integration of modern software-development methods into technical organizations. He has over 15 years experience as a research scientist, has written a commercial numerical package, and is a registered mechanical engineer living in Albany, Oregon. Tom can be contacted on CompuServe at 70511,652.
Algorithm: A set of well-defined rules for the solution of a problem in a finite number of steps.
Books on algorithms are important tools for the professional software developer. However, as can be seen from the definition, the breadth of issues covered under the heading of algorithms can make the selection of the proper book difficult. Topics can cover numerical applications, business applications, data structures, searching, sorting, optimization, and many others. Some generic characteristics seen in algorithm-related books (ARBs) include: How algorithms are designed, why a particular algorithm is chosen, what measures are used to assess algorithm effectiveness, construction considerations, instances of the algorithms, application examples, test cases, reliability issues, comparisons with other algorithms, and data-structure dependence. ARBs also have an associated level of difficulty that can range from introductory through intermediate and advanced, to specialized-advanced (where you, the author, and three others in the world are interested in the topic). The tone can vary from practical to academic, and the presentation, from well written to just plain poor quality.
Clearly, the selection of a book on algorithms is situational, depending on your needs of the moment. A lot of books are collecting dust on my bookshelves because their characteristics don't meet my current needs. We should take the opportunity to use our analytical skills to determine our needs and then compare those needs to the characteristics of the available books. This can help make our investments in time and money work for us. To supplement your needs assessment, here is my analysis of two relatively new books. Like movie critics who rate films from one to four stars, I will use a rating, with being a book that has little to offer, being a book with marginal impact, having significant contribution, and being a book that must reside on the serious developer's shelf.
Any book that purports to be "detailing the best algorithms ever devised for a wide range of practical problems_" has a huge challenge ahead of it just to live up to the propaganda on the jacket. Unfortunately, Programming Classics: Implementing the World's Best Algorithms, by Ian Oliver, falls far short of the hype. Even though it does cover a wide selection of applications, the coverage is spotty, sometimes shallow, and generally incomplete. In trying to limit the complexity of the presentation, Oliver has also limited its usefulness. On numerous occasions he resorts to hand waving such as: "_is beyond the scope of this book_," "We will not analyze in detail_," "Do not use this algorithm unless you know what you are doing," and "Given the mathematical sophistication needed for dealing with eigenvalues, no discussion of the reasons why the algorithm works will be given." Oliver has mistakenly tried to keep the presentation at an introductory level while introducing intermediate-level algorithms and concepts.
The lack of detailed discussion on the theory of operation of many of these algorithms leaves you to accept Oliver's choice for the implementation based on faith alone. If you have to modify, debug, or optimize the functions, the presentation in this book is generally inadequate. The inconsistency in the amount of detail is illustrated by the adequate coverage of sorting methods, including performance comparisons and application-specific suggestions, while the section on arithmetic is devoid of explanation.
In the poorly explained section on arithmetic, rational methods are introduced and a warning is given:
"_the methods will fail when integer overflow occurs. For certain practical applications it will be necessary to implement the algorithms in multiple precision arithmetic. The algorithms for multiple precision calculations are beyond the scope of this book."
What Oliver doesn't say is that the methods generally fail after only a few operations due to overflow, and the
use of greatest-common-denominator (GCD) reduction is only temporarily effective at preventing the overflow. His presentation also skirts the fact that this implementation only works for toy problems if multiple-precision arithmetic is not used.
The author uses his own generic language, reminiscent of Ada, to define his "code" examples. His intent was to produce a broadly targeted representation that was language independent. Instead, it will be difficult to translate some of the code to older languages such as Fortran, Cobol, or C. The example code exhibits problems with initialization, typing, character/byte access, parameter passing, memory usage, and other implementation issues. Since these issues are addressed in a generic way, it is almost assured that few real languages will come close to mapping transparently to his representations, forcing the users to modify their implementations without a clear understanding of the algorithm-design issues. If Oliver was serious about producing reliable code for readers to use directly, he should have chosen specific target languages so the syntax questions could have been dealt with in his implementations.
I rate Programming Classics , for poor execution of a fundamentally good concept, useful only as the first place to look to find references to more complete explanations of the problems to be solved. While this book could be useful to experienced designers looking for a reference that gives terse overviews and points to other sources for details, it will be a hazard for the inexperienced designer looking for a quick method to solve a poorly understood problem.
Algorithms from P to NP is a careful, academic text designed for graduate students, upper-level undergraduate students, and computing professionals prepared to use rigorous mathematical analysis in problem solving. If you aren't comfortable with set notation, discrete mathematics, data structures, calculus, and algebraic expression of problems--pick another book. Algorithms from P to NP, Volume I, Design and Efficiency, by Moret and Shapiro, is clearly designed as an advanced textbook to be used in a classroom setting with an instructor and does an excellent job in that context. It also serves as a good refresher and reference for those who have been through similar advanced courses. I particularly liked the presentation and felt that Moret and Shapiro did a good job of leading the student through the solution process; however, it is industrial-strength analysis and not for the faint-of-heart. But it is worth the effort. The authors expect you to recognize standard algebraic notation, but introduce specific concepts with which you might not be familiar--a spanning tree, O-notation, generating functions, and directed graphs. The exercises range from simple examples to thesis-level assignments.
Algorithms from P to NP concentrates on combinatorial optimization problems and takes a thorough, depth-over-breadth approach. Moret and Shapiro start with several traditional problems such as the knapsack problem (filling a knapsack with the optimal mix of things for a camping trip) and the traveling salesperson problem (traveling through a series of cities while optimizing time or distance). These problems are revisited throughout the book in generic instances as the problem-solving approach is modified and expanded to encompass extensions of the problems. You're given more tools to deal with increasingly difficult examples of the problems as the book progresses.
The reference to a "stack of punch cards," which most graduate students have never seen, dates the origin of some of the examples while demonstrating the timelessness of the problems. Throughout the book, there is just enough nerd humor (my favorite kind) to liven up a graduate course in algorithms. The basic approach of the book is one that I am comfortable with: "The study of algorithms cannot be dissociated from the study of problems." Their approach is to start with problem solving and then show how the solutions map naturally into an algorithm for the effective solution of the problems. They spend time reviewing methods for assessing algorithm run time, but they deal only peripherally with the concept of reliability. This limited discussion of reliability is probably related to the focus on combinatorial problems, as opposed to numerical issues. Algorithms from P to NP discusses not only the theoretical, asymptotic behavior of the algorithms, but also the application and implementation issues that impact performance. The language used for example code is Pascal, and the code examples have been used and tested in classroom situations.
The name of the book reflects the concentration in this volume on problems that have solutions which, as a worst case, require "Polynomial time" (O(Nk), where N is the number of items and k is some constant) for their completion. These are represented as P-problems. The second volume deals with NP-complete problems (problems for which no solution has been found that can be completed in polynomial time). NP-complete problems are an ongoing subject of research, and are generally solved by approximation methods.
I rate this book , for concise, clear explanations of problem-solving issues. A serious textbook for serious study of combinatorial issues. Don't pick this book up for light reading!
(For reviews of 14 ARBs dealing with numerical issues, refer to my "Building Blocks" column in the former Computer Language magazine, November, 1992.)
Programming Classics: Implementing the World's Best Algorithms
Ian Oliver
Prentice Hall, 1993, 386 pp. $38.00
ISBN 0-13-100413-1
Algorithms from P to NP, Volume I: Design and Efficiency
B.M.E. Moret and H.D. Shapiro
Benjamin/Cummings Publishing, 1991, 576 pp. $41.95
ISBN 0-8053-8008-6
Copyright © 1994, Dr. Dobb's Journal