thomas@ektools.UUCP (Thomas B. Kinsman) (12/22/88)
The following is a bibliography generated by a recent request to the net for reference books on algorithms in general. No names will be mentioned, but replies came from many countries around the world. Several people that I consider influential in our field responded. Thanks are expressed for all who responded. People generally mentioned Knuth. However, Knuth was frequently mentioned as a lower priority choice when priorities were men- tioned. Many expressed difficulty with the way algorithms were given in Knuth. Others suggested that Knuth's method of presentation leads to a better understanding of the method of implementation. Sedgewich was a popular first choice. However, no one mentioned that there is now a second edition of this book. Note: This was not a scientific survey. Votes were cast for a reference by mentioning it in a positive way. In the case where prioritized lists were received, no weights were assigned. Ti- tles, Authors, etc... were taken on good faith. The existence of references was NOT CHECKED. Some people just responded by mentioning authors. Referring to a book as "Smith, and Jones" is not always helpful, especially if Smith and Jones ARE really married to each other and have jointly written several books. I did my best to figure out which book was intended, without killing myself in the process. Some respondents just mentioned titles. Some books are so closely related, i.e. the "Numerical Recipies in..." series, that they were grouped together. At any rate, this is just an information source for your consideration. Neither I, nor my company, recommend any of them. The following sources of inform- ation are some you may wish to know about: A more verbose list is posted to the news group "comp.misc". ~~~~~~~~ ~~~~~~~~ ~~~~~~~~ General Quotes: "...you judge the utility of a reference handbook by the condi- tion (the more battered the copy, the more it's been used)..." "...my world is design, and I spend much of my time explaining the crucial distinction between an active (design) model of something, and the thing itself. Many fail to accept the distinction when faced with deep simulations running off a rich (near-complete) model...." "...The need to go to an algorithms book comes rarely, but when it does, ..." "Truthfully, though, it is often the case that the applications-specific algorithm that I need (eg. vision/image oriented for example) appears in any textbook that gives a thorough and rigorous treatment on that subject." "...It's really difficult to pick a first, because this is nearly always context-dependent..." "...hunt around other peoples desks or wander through the load of sources we have on our system..." "...For *all* cases once I've written the code, I don't analyze it by seeing if I've copied the book correctly, I do that independently with a friend, line by line, so we know the result will be more or less provably right..." Source: "Algorithms" Author: Robert Sedgewick Votes: 19 Misc: Addison-Wesly, 1983. Misc: The examples are in Pascal, which is close enough to C that I can lift large chunks of code straight out of the text. "...general purpose..." "...if I had to just pick one book..." "...broad but fluffy..." "...elementary level but if it has what you're looking for it will be easy to understand..." Source: "The Art of Computer Programming" Volume 1/ Fundamental Algorithms Volume 2/ Seminumerical Algorithms Volume 3/ Sorting and Searching Author: Donald E. Knuth Votes: 39 Misc: Reading, Massachusetts, 1968: Addison-Wesley Publishing Co. Misc: "(Of course, Knuth writes in assembly language, so there is some level of translation involved.)" "...for data structures..." "...it isn't very pretty, but the information is there..." "...I use the tombs for system stuff like hashing codes and sorting..." "...I always go to [this]..." "...general purpose..." "...if I'm feeling really masochistic then I'll check one of the Knuth books." "...I would like to say that I use Knuth, but that has not been the case..." "...the Bible for such a situation..." "...still the classic reference as far as I know..." "...I've seen no other book on algorithms that is worth 1/10th as much." "...I would like to say that I use [this], but I don't..." (Did not vote for knuth.) "...often very out of date...MIX assembly language decipherment isn't always that much fun :-)..." "...the last place I go..." "...The volumes are accurate, comprehensive, well written, well indexed; they provide ample pointers to further literature. Tradeoffs between different approaches are analyzed..." "...Anything that came from Bell Labs (NJ). Not Knuth's series, though. Find the latter almost impossible to read..." "...No question. Knuth..." "...You have to be joking. Knuth's 'The Art of Computer Programming'..." Source: Data Structures + Algorithms = Programs Author: Wirth Votes: 6 Misc: "...a good book for practical situations..." (it was a text book in a class years ago). "...slightly easier to read, and includes quite a bit of Modula-2 code..." "...A notorious book is [this] ETH students have moaned for years about the bugs there, especially with some of the tree and linked list stuff. Disgusting..." Source: The Theory of Parsing, Translation, and Compiling Author: Aho and Ullman Votes: 2 Source: Compiler Design Author: Hopcroft / Ulmman / Sethi Misc: These are the "dragon" books. Source: Principles of Compiler Design. Author: Aho, Hopcroft, & Ullman. Votes: 4 Misc: The "dragon" book. Source: Compiler Design Author: Aho, Sethi & Ullman Votes: 3 Misc: This is the second Dragon book. Source: Intro to Data Structures and Algorithms. Author: Aho, Hopcroft, & Ullman's Votes: 2 Source: Data Structures and Algorithms Author: Aho, Hopcroft, and Ullman Votes: 7 Misc: "It's a great little book of basic algorithms and data structures. Nothing too outrageous, though. My copy is almost worn out." Source: Design and Analysis of Computer Algorithms (?) Author: Aho, Hopcroft, and Ullman Votes: 6 "...I am very careful to avoid assuming that previously used techniques are the best ones for a problem..." Source: Intro to Formal Languages, Automa Theory and Computation. Author: Hopcroft & Ullman Source: Handbook of Algorithms and Data Structures Author: G.H. Gonnet Pub: Addison-Wesley, 1984 Votes: 4 Misc: "I often look at [this book]. It is useful in itself (with code in Pascal and/or C) but also full of references-- to 23 textbooks and 683 papers to be exact." Source: Writing Efficient Programs Author: Bentley Source: Programming Pearls Author: Bentley Source: Numerical Recipes in C, the art of scientific computing. Numerical Recipes in FORTRAN, the art of scientific computing. Numerical Recipes, the art of scientific computing. Author: W.T. Vetterling S.A. Teukolsky W.H. Press B.P. Flannery Pub: Cambridge, Cambridge University Press, 1988. ISBN 0-521-35465-X Votes: 8 Misc: "...It doesn't matter which language, really. I'm a C programmer, but before the C version came out, I found the FORTRAN version useful." "...you probably can see that I do a lot of floating point number crunching, rather than sorting and hashing and table searching stuff." "...for numerical stuff..." Source: Structure and Interpretation of Computer Programs Author: Abelson & Sussman Votes: 2 Misc: "...you probably can see that I do a lot of floating point number crunching, rather than sorting and hashing and table searching stuff." Author: Bender and Orszag Misc: "...you probably can see that I do a lot of floating point number crunching, rather than sorting and hashing and table searching stuff." Source: "Artificial Intelligence Programming" Author: Charniac, Reisbeck, Mcdermott, & Meehan Misc: "...It's not the most fundamental book, but I've found [it] to be the book that establishes the leap from 'Let's Learn Lisp!' to Lisp in the Real World - filled with all sorts of ideas, and permanently beside my terminal." Source: Recursive Techniques in Programming Author: D.W. Barron, Misc: New York, 1968: American Source: Fundamentals of Data Structures Fundamentals of Data Structures in Pascal Author: Horowitz, & Sahni Votes: 5 Misc: "...my personal favorite..." Source: Principles of Data Structures and Algorithms Author: Horowitz & Sahni Votes: 2 Misc: "...for general data structures..." Source: Fundamentals of Computer Algorithms Author: Horowitz & Sahni Source: Computers and Intractability: A Guide to the Theory of NP-Completeness Author: Michael R. Garey, & David S. Johnson. Votes: 2 Misc: "...Perhaps not an algorithm catalog in the strict sense, but I find it useful in problem solving..." Source: Combinatorial Optimization: Algorithms and Complexity Author: Christos H. Papadimitriou, & Kenneth Steiglitz Misc: "fairly new but looks like its full of interesting stuff. I looked at several similar ones and bought this." Source: Computer and Job-Shop Scheduling Theory Author: E. G. Coffman, Jr. (Ed.) Misc: "A collection written by several recognizable people." Source: Algorithms in SNOBOL4 Author: Gimpel Source: "Factorization Methods For Discrete Sequential Estimation" Misc: "useful for estimation algorithms." Source: Heuristics Author: Pearl Misc: "...if the problem is NP complete..." Source: Data Structures and Network Algorithms Author: Tarjan Misc: "...for network problems..." Source: Graphs and Network Algorithms Author: Tarjan Misc: "...for combinatorial algorithms and recursive structures..." Source: Priciples of Database and KnowledgeBase Systems, Author: Ullman Votes: 2 Author: Teorey, & Fry Misc: "...for data base work..." Source: Implementations of PROLOG Author: Campbell Source: The Computer Modelling of Mathematical Reasoning Author: Bundy Source: Anatomy of LISP Author: Allen Source: Natural Language Understanding Author: Allen Source: Any number of articles in CACM. Collected Algorithms of the ACM (CALGO). Comm. of ACM TODS (Transactions on Database Systems) Votes: 5 Source: LispCraft Author: Wilensky Source: Lisp Author: Winston Source: Prolog programming for AI Author: Bratko Source: Data Structures Author: Reingold, & Hansen Source: Data Structures Author: Standish Votes: 2 Misc: "...understandable level with good Knuth style specifications. Quite complete also..." Source: The Unix Programming Environment Author: Kernighan, & Pike Source: Software Tools Author: Kernighan Source: Matrix Computations Author: Holub, & Van Loan Misc: "...for numerical analysis..." Source: Artificial Intelligence Author: Winston Misc: "...for AI work, either of the books by Winston..." Source: Fundamentals of Interactive Computer Graphics Author: Foley, & Van Dam Votes: 2 Misc: "...for graphics stuff..." Source: Computer Algorithms Author: Sara Baase Source: The Art of Prolog Author: Chris Date Misc: "...Relational Databases..." Author: Ullman, Liskov, & Guttag, Sowa Misc: "...Data structures/abstraction..." Source: How to Solve It by Computer Author: Dromey R.G. Misc: Prentice/Hall International Series in Comp. Sci. Source: Recent journal article(s) I've read on that problem. Source: ...the SIGARCH world...