From: nmm1@cus.cam.ac.uk (Nick Maclaren)
Newsgroups: comp.theory,sci.math,ucam.comp.misc
Subject: Practical algorithm references
Date: 31 Jan 1995 11:33:43 GMT
The following is a list of books on general-purpose algorithms for the
practical programmer (or 'software engineer'), who is interested in using
algortithms rather than studying them. It interprets 'general-purpose' as
meaning basic data management and related techniques. It gives my personal
view of what the books are best suited for, which is not necessarily what the
authors wrote them for! Corrections of factual errors will be welcomed. This
document is available via anonymous FTP from cus.cam.ac.uk in the file
/pub/misc/docs/algorithm.books.
Books on general algorithms that I would recommend for practical programmers:
-----------------------------------------------------------------------------
Aho, A.V., Hopcroft, J.E. and Ullman, J.D. The Design and Analysis of
Computer Algorithms. Addison-Wesley (1973).
This is a standard computer science textbook, but is very practical and has
clear examples of code in `pidgin Algol' (which would be easy to convert to
almost any programming language). Its coverage of basic data structures is
good, and it contains fewer digressions than in most other books. Its main
fault is that it is rather dated, and so is missing some important modern
algorithms.
Aho, A.V., Hopcroft, J.E. and Ullman, J.D. Data Structures and Algorithms.
Addison-Wesley (1983).
This is almost entirely about data structures and data management, and contains
only a few algorithms as such. It is probably the best introduction to basic
data handling, which is the core of almost all serious programming, and
includes modified Pascal code for clarification. Its main fault is that the
example code is rather eccentric, and should not be used as a basis for
programming.
Cormen, T.H., Leiserson, C.E. and Rivest, R.L. Introduction to Algorithms.
MIT Press (1990).
This is the specialists' standard reference on basic algorithms, and has
detailed coverage of most aspects and a long bibliography. It assumes only a
reasonable amount of mathematics, and has clear examples in an Algol-like
`pseudocode'. It is the most comprehensive of the books mentioned here. Its
main faults are that assumes considerable background knowledge and does not
distinguish theoretical points from practical ones; these features may confuse
non-specialists.
Gonnet, G.H. and Baeza-Yates, R. Handbook of Algorithms and Data Structures
in Pascal and C. Addison-Wesley (1991).
Do not confuse this with the first edition (by Gonnet alone) - the second is
much better. The title is still extremely misleading, it scarcely mentions the
basic data structures (such as stacks and lists) and it assumes a fair
mathematical background. However, it has good coverage of hashing, searching
and sorting, though little else; few other books describe hashing in any
detail. In a sense it starts where Aho, Hopcroft and Ullman (1983) leaves off.
Its main fault is that it takes a rather narrow view of what is important in
computer science and programming.
Horowitz, E. and Sahni, S. Fundamentals of Data Structures. Pitman (1977).
This covers most of the basic data structures and algorithms, with clear
examples in a description language SPARKS. It is more restricted in scope and
has more figures and examples than the other books mentioned here, and is
clearly intended for the average student (rather than the `natural'
programmer). Its main faults are that it is a little limited and not well laid
out for the person who just wants to look something up.
Knuth, D.E. The Art of Computer Programming. Addison-Wesley. Vol. 1
Fundamental Algorithms (2nd ed., 1981), Vol. 2 Seminumerical Algorithms (2nd
ed., 1981), Vol. 3 Sorting and Searching (1973).
This is a standard reference on programming methodology and algorithms,
covering almost all aspects and starting from scratch. It is one of the best
books for non-specialists to use, for that reason. Its main faults are that
its approach and notation are idiosyncratic, and there are several long and
confusing digressions (e.g. minimum-comparison sorting and whether random
sequences can exist).
Sedgewick, R. Algorithms. Addison-Wesley (1983). Algorithms in C.
Addison-Wesley (1990).
This is a standard computer science textbook, but is reasonably practical and
covers almost all of the basic algorithms. "Algorithms in C" includes some
rather crude examples of C code, which should not be used in real programs;
there is also Algorithms in Pascal. Its main fault is that it tries to cover
too many areas and skimps on the descriptions in many places; non-specialists
may miss important points.
Books on more specialist algorithms:
------------------------------------
I may produce a list of some of these later. There are some very good ones
around, as well as much rubbish, but one needs to be a polymath to be able to
understand even their introductions! There is one book that I cannot avoid
mentioning, because it is so often recommended.
Press et al.: Numerical Recipes [in C etc.]
This is the computer equivalent of "Remove your Tree Stumps with Home-made
Explosives and Save Dollars". Most of the algorithms described are appropriate
and reliable, though some are definitely unsafe, but almost all have a few
restrictions on the input that they will handle correctly. The book neither
warns about such restrictions, nor includes code to check for them - as is
well-known to numerical analysts, this can easily lead to wrong answers without
warning. These comments apply to both editions.
Books on algorithms that I would NOT recommend for practical programmers:
-------------------------------------------------------------------------
Most of these are quite good, and I WOULD recommend them for other purposes
(such as teaching or for background reading). It is just that I feel they are
not oriented as references for most programmers, except possibly those who want
to read up on the theory behind the practice. Some programmers will prefer
them to the books in the previous section. A couple of them should be avoided.
Baase: Computer Algorithms
This is perhaps the clearest introduction to the theory and notation of
algorithms, and assumes very little mathematical background. However, it
scarcely mentions stacks and trees, its selection of algorithms is
representative rather than practical, and its descriptions give principles
rather than products. It was written for an undergraduate course in
algorithms, and should be very good for that.
Brassard and Bratley: Algorithmics Theory and Practice
This doesn't pretend to be a practical reference, and assumes a good background
in basic computing and mathematics. While it is clearly laid out, its
structure is most odd and it describes only general principles; it also gets
considerably more obscure towards the end. It was written for graduate and
senior courses on algorithmic theory, and is probably quite good for that
purpose.
Gonnet: Handbook of Algorithms and Data Structures
The title is about as misleading as it is possible to be. It contains very
few (though important) types of algorithm and data structure, yet implies that
it is fairly complete. More seriously, its approach is definitely bizarre
(e.g. lists and trees are described as special cases of priority queues!), and
it drops the reader into its concise descriptions with minimal background
information. If the reader can avoid getting confused by these aspects, its
standard is fairly high, but the second edition is much better in all respects.
Harel: Algorithmics: The Spirit of Computing
It doesn't pretend to be a practical reference (and isn't), but attempts to
describe the `philosophy' of computing. If a non-specialist wants to know what
the specialists are talking about, this is the book to read. The style is
rather irritating in places, however.
Kernighan and Plauger: Software Tools [also Software Tools in Pascal]
This describes how to write some simple tools in Ratfor (mostly for handling
text), but is mostly about elementary programming and there is little about
algorithms. Error checking and portability are completely ignored. It uses
the original, catastrophic version of Quicksort, and comments about its
problems only in an exercise. In addition, the Pascal book misses the whole
point of Pascal, and the first example contains 3 gross non-portabilities.
Manber: Introduction to Algorithms a Creative Approach
This is interesting but not very practical. It describes how and why many
different algorithms are the way they are. On the other hand, its basic data
structures are extremely limited (e.g. no stacks or doubly linked lists),
algorithms are described in a sometimes confusing pseudo-Pascal and historical
developments are mixed in with current methods. It is probably a good book
for anyone who needs to know the reasons behind developments.
Moret and Shapiro: Algorithms from P to NP (vol. I - Design and Efficiency)
This contains clear Pascal code of some important algorithms, but it organises
them by algorithmic type (not purpose) and has almost no introductory text. It
is thoroughly confusing as a practical reference book, and would probably
baffle the average first- or second-year student. It was written for graduate
and senior courses on algorithmic theory, and is probably quite good for that
purpose.
Purdom and Brown: The Analysis of Algorithms
The title means just what it says. This is perhaps the best book on the theory
and practice of the analysis of algorithms, but it is not very useful as a
reference of actual code. It is not easy reading and needs some mathematical
background, but is not a mathematical treatise. It is aimed at people who
develop and analyse algorithms, rather than people who just use them.
van Leeuwen (ed.): Algorithms and Complexity
For mathematicians and masochists only, and of little practical relevance, but
extremely interesting to specialists. One of the few books on this topic that
doesn't stop at NP completeness. It is also expensive!
Wilf: Algorithms and Complexity
This is perhaps the most readable introduction to mathematical complexity
theory, and contains detailed descriptions of a wide range of interesting
algorithms. It does not pretend to be a practical reference, and isn't. It
was written as a mathematics textbook, but it keeps its mathematics simple
enough for most scientific readers.
Wirth: Algorithms & Data Structures [Modula-2 version].
This does not describe stacks or mention doubly-linked lists, and includes
list-merge only as an out-of-store sorting technique! The way that it uses
Modula-2 means that the examples are thoroughly confusing (even if you know
that language). It also goes on at great length about completely impractical
methods, and omits very important ones.
Books that I have not been able to obtain
-----------------------------------------
These have been recommended, but they are not available in Cambridge, and I
did not feel energetic enough to order them.
Lewis and Denenberg
Melhorn (3 volumes)
I am grateful for comments and suggestions from the following people, but all
views, omissions and errors are my own.
David Mix Barrington
DJ Ierardi
Jerry Kuch
Arthur Norman
Paul Purdom
Sandeep Kumar Shukla
Stefan Slucks
A Staines
Jacques Verriet
Guy Vidal-Naquet
Nick Maclaren
University of Cambridge Computing Service
January 1995