[ ERCB Home |
New |
Feature |
Brief |
DDJ |
Letters |
Links
]
A Clear Look Through Bleary Eyes
at Two Books on Algorithms
Review by Tom Ochs
Copyright (C) Dr. Dobb's Journal, April, 1994
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 p
rating, with p being a book that has little to offer, pp being a book with
marginal impact, ppp having significant contribution, and pppp being a book
that must reside on the serious developer's shelf.
Programming Classics
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 p, 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
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 ppp, 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
Electronic Review of Computer Books
Created 5/1/96 / Last modified 6/4/96 / webmaster@ercb.com