Alla oleva löytyi verkosta. Pistin sen www:hen tekijän luvalla. --AV

Omia lisäyksiä:

J. H. Kingston: Algorithms and Data Structures, Design, Correctness, Analysis, Addison-Wesley 1998
Kohtuullisen kokoinen (380 s.), aihevalinnaltaan onnistunut ja pikaselauksen perusteella esitystavaltaan sopiva kirja: ei liian teoreettinen, eikä liian pinnallinen. Kiinnittää huomiota algoritmien oikeellisuuteen, mutta sopivan epämatemaattisella tasolla. Kiinnittää huomiota myös abstrakteihin tietotyyppeihin ja rajapintoihin.

Practical algorithm references

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.

[AV 28.8.1998: ks. myös lisää kritiikkiä.]

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.

I am grateful for comments and suggestions from the following people, but all views, omissions and errors are my own.

Nick Maclaren [nmm1@ucs.cam.ac.uk]
University of Cambridge Computing Service
January 1995