34
votes

Is there an encyclopedia of algorithms similar in style to the Handbook of Mathematics? It seems useful to have large numbers of them available in one place. I know the Art of Computer Programming is considered a good source but it does not seem encyclopedic so much as instructive.

Moderator Note

We're looking for long answers that provide some explanation and context. Don't just list a book: please explain why you're recommending a book or resource. Answers that don't explain anything will be deleted. See Good Subjective, Bad Subjective for more information.

2
  • 3
    stackoverflow.com/questions/6781096/… Commented Aug 19, 2011 at 3:24
  • A little Googling would go a long way toward answering this question. At the very least, it would provide a list of good candidates which you could then use to ask a more focussed question. Commented Aug 19, 2011 at 16:37

9 Answers 9

Reset to default
41
votes

I'm not sure if this is what you're looking for but NIST has the Dictionary of Algorithms and Data Structures. It's a pretty comprehensive dictionary for data structures and algorithms (doh) and usually a good to place to look when I find something I never heard about before.

2
  • Your answer is pretty much exactly what I'm looking for. Extra points for being free. Commented Aug 20, 2011 at 23:28
  • Funny thing is, over the past few days the NIST DADS is closed until further notice because of the US Government's shutdown! And then when heard thousands of developers scream at once... Commented Oct 6, 2013 at 21:49
11
votes

The Skiena book is a good reference also: http://www.algorist.com/

The book covers everything from background through different problem areas (data structures, searching/sorting, graph problems, combinations/permutations/heuristics) and even the issues of P vs NP-complete problems.

The particularly relevant section of the book to this question is a catalog of ~70-75 different algorithms, the types of inputs they generally require, the overall description of the problem a particular algorithm solves, and specific examples of applications (for example, the section on suffix trees discusses its usage of tries, and its applicability to substring and searching). Where possible the author also identifies existing implementations for various common languages (c, c++, Java, and some others.)

1
  • That's the closest to an algorithm encyclopedia that I can think of. Excellent book! Commented Aug 20, 2011 at 9:14
8
votes

Structure and Interpretation of Computer Programs and the Art of Computer Programming are the closest I've seen to what you seek.

SICP walks through common data structures and algorithms. While it's not encyclodpedic, it is pretty good a covering a wide swath of territory in a limited amount of space.

What can be said about The Art of Computer Programming that hasn't been already. Be careful when you pick it up, you might go to it for a specific topic and hours later realize that you've read a volume from cover to cover. It's a great way to really take your programming to the next level.

3
  • 5
    SICP is a wonderful book, but I don't think it's a reasonable suggestion for someone looking for "an encyclopedia of algorithms." SICP doesn't attempt to be anything like that. Furthermore, the OP wrote that ACP "does not seem encyclopedic so much as instructive," so it should be clear that SICP is not what he or she is looking for. Commented Aug 19, 2011 at 14:50
  • Great book, but not encyclopaedic. Commented Aug 19, 2011 at 15:19
  • Pretty sure I said that it's not encyclopedic but gives a good tour of algorithms. "While it's not encyclodpedic, it is pretty good a covering a wide swath of territory in a limited amount of space." Yup that's what I said. Commented Aug 20, 2011 at 23:34
8
votes

Cormen, Leiserson, Rivest, Stein - "Intoduction To Algorithms"

Introduction to Algorithms, more commonly known as CLRS, is the standard algorithms textbook at a large number of universities. It covers a range of algorithms for a variety of applications, including sorting, searching, graph theory and basic numerical computation. It also includes a detailed discussion of Big O, Big Omega and Big Theta notation. A common criticism is that it doesn't really prepare one to design new algorithms, but as an encyclopedia or dictionary of algorithms, its is more than adequate.

I should also note that CLRS also gives advice on which algorithm to use when, and doesn't just present a generic index of algorithms and data structures. It's useful when you have a task that you want to accomplish and want advice on how best to go about it. There are better resources for when you know how you want to do what you're doing and you just need pseudo-code.

— from comments by @quanticle, below

4
  • 4
    Can you expand your answer to include what about this book meets this question's goal? Commented Aug 19, 2011 at 7:34
  • 2
    Introduction to Algorithms, more commonly known as CLRS, is the standard algorithms textbook at a large number of universities. It covers a range of algorithms for a variety of applications, including sorting, searching, graph theory and basic numerical computation. It also includes a detailed discussion of Big O, Big Omega and Big Theta notation. A common criticism is that it doesn't really prepare one to design new algorithms, but as an encyclopedia or dictionary of algorithms, its is more than adequate. Commented Aug 19, 2011 at 18:50
  • 1
    I should also note that CLRS also gives advice on which algorithm to use when, and doesn't just present a generic index of algorithms and data structures. It's useful when you have a task that you want to accomplish and want advice on how best to go about it. There are better resources for when you know how you want to do what you're doing and you just need pseudo-code. Commented Aug 19, 2011 at 18:54
  • Hint to Dmitry: just copy @quanticle's comments into the body of the answer to make your answer 1000% more awesome. Commented Aug 19, 2011 at 20:53
5
votes

In graduate school in Physics I really enjoyed Numerical Recipes in C. It does not cover all algorithms, of course, but gives excellent explanations of many that are incredibly useful in the sciences:

http://www.nr.com/

The book covers how to solve:

Linear equations

  1. Linear Equations
  2. Interpolation and Extrapolation
  3. Integration of functions
  4. Function Evaluation
  5. Special functions including gamma function, beta function, factorials
  6. Random numbers - including a good explanation of what this means
  7. Sorting algorithms
  8. Finding roots and nonlinear equations
  9. Minimization and maximization of functions
  10. Eigensystems
  11. Fast Fourier Transforms
  12. FFT and spectral analysis
  13. Statistical description of data
  14. Modeling of data
  15. Integratoin of ordinary differential equations
  16. Two point boundary problems
  17. Integral equations and inverse boundary thory
  18. Partial Differential equations
  19. "Other" algorithms such as CRC checks and data compression

So it's all very mathematical, good for scientists as well as for people designing physics engines for games. And it does not just give the algorithms but explains the whys behind them so that you can use them correctly. Not your typical coding text, but exactly what you need when you need it.

I relied on it heavily when using the downhill simplex method in multidimensions (an amoeba walk) for data analysis. Still has my pencil marks in it. Ahh, good times!

1
  • 1
    Can you expand your answer to include what about this book meets this question's goal? Commented Aug 19, 2011 at 7:35
4
votes

If you're looking for an "encyclopedia of algorithms," it'd be hard to go wrong with Encyclopedia of Algorithms. I can't say that I've read it (at $399, it's cheap for an encyclopedia), but the blurb looks promising:

The Encyclopedia of Algorithms provides a comprehensive set of solutions to important algorithmic problems for students and researchers, including high-impact solutions from the most recent decade.

Someone already cited Steven Skiena's The Algorithm Design Manual, but I don't think anyone has yet mentioned Skiena's associated web site, The Stony Brook Algorithm Repository. From the web site:

This WWW page is intended to serve as a comprehensive collection of algorithm implementations for over seventy of the most fundamental problems in combinatorial algorithms.

The book is more than just a catalog of known algorithms; it's also a sort of tutorial (in the best sense of the word) on how to decide which algorithm to use to best suit your problem and situation. The repository, on the other hand, is more encyclopedic in nature. It doesn't necessarily contain a lot of detail about how to implement each algorithm yourself, but it does explain what the algorithm does and how it works in general, readable terms often taken from the book, and it provides links to actual implementations for each algorithm.

2
votes

The Rosetta Code Wiki is a great collection of implementations of common algorithms in several languages. It's not entirely academic, but quite informative and fun to flip through.

In their own words:

Rosetta Code is a programming chrestomathy site. The idea is to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another.

Its main advantage over other resources (like the NIST Dictionary of Algorithms and Data Structures) is that it allows you to look at several implementations for different languages. Which can be helpful for various purposes (comparing expressiveness, verifying feasibility in a language or another, etc...).

For instance, the QuickSort page provides (as of 2013-10-07) at least 89 implementations.

4
  • would you mind explaining more on what it does and why do you recommend it as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange Commented Oct 6, 2013 at 20:50
  • @gnat: Usually would agree, but how is that different that a "book-ref only" answer? Also, I think "collection of implementations of common algorithms in several languages" covers pretty much what it does. It's also as (or as little) detailed as the accepted answer, if you look close enough :) Commented Oct 6, 2013 at 21:09
  • @gnat: anyways, added some more. Commented Oct 6, 2013 at 21:44
  • @AnnaLear: sorry, I think your edit was perfectly right to keep my post short and on track, but it seemed fitting to put the comparison back in with regard to the changes at gnat's request. Commented Oct 6, 2013 at 21:45
0
votes

While there are excellent and timeless instructive books on the subject, I hardly think, you will find such an encyclopedia.

  • An encyclopedia on mathematics covers millennia of research. Algorithms on the other hand are barely studied for a century (speaking on a larger scale). The whole field of computer science is barely understood by anyone and most things are still moving quickly. If there were an encyclopedia on this right now, I guess you could throw 90% out the window in 10-20 years. And of the 10% worth keeping more than half was already printed half a century ago. The vast parts of the handbook of mathematics will be up to date in a hundred years from now.

  • Mathematics is pure and self-contained. This hardly applies to "the field of algorithms". It actually can hardly be thought of as a field, because a field usually operates on a well defined problem space, while algorithms actually only operate within a more less well defined solution space.
    So if one were to compile an encyclopedia on algorithms, it is not really clear what to include, if your really want it to be comprehensive. Graph theory? Linear algebra? Numerical analysis?

IMHO, right now the best resource that fulfills the role of an encyclopedia, is "the internet" (behold). The point of an encyclopedia is to have an indexed, comprehensive, searchable repository of knowledge (on some topic). Personally, I find both this list and this list quite overwhelming. Also in other answers, numerous excellent algorithm databases have been linked.

So while you can't expect the same level of quality as you would expect from an encyclopedia that fills your bookshelf, you do get the level of timeliness required to compensate for the youth of the field you want to know about.

0
votes

As far as extant sources, I think Wikipedia is the closest thing to what you're looking for. To wit, it might be useful to create a more defined "algorithm template" on Wikipedia for this purpose, but that's something to be discussed with Wikipedia editors and not here.

A quick note on The Art of Computer Programming: when it is completed it is to include a "summary" volume and although that won't help you now, it might be approximately what you're looking for. TAOCP is encyclopedic for what it does cover, but it isn't complete yet and Knuth's personality is such that he isn't going to include things unless he's exhaustively researched them.