Algorithm books on a range of topics

Question

I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. All people here have at least a Bachelor's degree in CS or a closely related field, so while I will get some basic textbook like Cormen, I'm more interested in good books on advanced topics. (I will get Knuth's 4 volumes, BTW.)

Some list of topics would be:

• Sorting algorithms

• Graph algorithms

• String algorithms

• Randomized algorithms

• Distributed algorithms

• Combinatorial algorithms

• etc.

Essentially I'm looking for good recommendations on books about major topics within CS related to algorithms and data structures. Especially stuff that goes beyond what's typically covered in algorithm and data structure classes as part of a Bachelor's degree at a good school. I know the question is quite fuzzy, since I'm looking for generically useful material. The software we develop is mostly system level stuff handling large amounts of data.

The ideal would also be to find anything that would cover fairly recent cool data structures and algorithms, which most people might not have heard about.

---

EDIT: Here are some preliminary books that I think I should get:

• Introduction to Algorithms by Cormen et al.

• Algorithm Design by Kleinberg, Tardos

• The Art of Computer Programming Vol 1-4 by Knuth

• Approximation Algorithms by Vazirani

• The Design of Approximation Algorithms by Williamson, Shmoys

• Randomized Algorithms by Motwani, Raghavan

• Introduction to the Theory of Computation by Sipser

• Computational Complexity by Arora, Barak

• Computers and Intractability by Garey and Johnson

• Combinatorial Optimization by Schrijver

A few other books my colleagues wanted that deal with techniques and algorithms for language design, compilers and formal methods are:

• Types and Programming Languages by Pierce

• Principles of Model Checking by Baier, Katoen

• Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, Ullman

• The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition by Srikant, Shankar

• The Garbage Collection Handbook: The Art of Automatic Memory Management by Jones, Hosking, Moss

Answer 1

I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked with most of them to some extent, or had them recommended by experts.

I assume that you want your people to learn what can be done, and how to do it, as opposed to learning what they can't do. In particular, I will leave out books about computability and complexity theory as such; I expect your people to have taken away the relevant messages from their undergraduate education.

• The Basics
  Even though your people have learned them at some point, expect them to look up the basics. Since sources like Wikipedia are frequently substandard or outright wrong, you want to get them proper reference texts.

  Popular choices include

  • Introduction to Algorithms by Cormen, Leiserson et al.
    Very broad introduction that covers many elementary algorithms and data structures as well as basic analysis techniques. A standard text used frequently for teaching purposes and available in its 3rd edition (so most mistakes should have been purged by now). Lots of exercises.
  • Algorithms by Sedgewick and Wayne
    Another standard text in its fourth edition. Less broad than Cormen, but with more attention to implementation details. Lots of material online, including a free course on Coursera. Lots of exercises.
  • Introduction to Algorithms -- A Creative Approach by Udi Manber
    Also rather slim a selection of topics, but presented with attention to didactics. The focus is on inductive strategies. Contains lots of exercises and solutions (or at least hints) for some. A good secondary reference if you don't like the recommended textbook because of its unusual style.
  • Concrete Mathematics by Graham, Knuth and Patashnik
    Covers discrete mathematics as relevant to algorithm analysis. Rare in its focus on computer science needs and rigor. Very high quality. Lots of exercises with solutions.

• Analysis of Algorithms In most standard text books, analysis of algorithm usually stops at the level of $O$-asymptotics and RAM model. In order to estimate real-world efficiency more reliably, it can be necessary to investigate runtime more precisely and consider effects like memory hierarchy and communication.

  • An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet
    Basic techniques for precise analysis of algorithms. Written by the pioneers of the field. Also has a free online course.
  • The Art of Computer Programming by Knuth
    The reference for high-quality, low-level, precisely analysed algorithms for a whole range of problems. Also serves as reference.

• Advanced Surveys

  • Purely functional data structures by Okasaki
    Classic and basic literature often focuses on the procedural paradigm. If you want to work in the functional paradigm, new techniques for efficient data structures are needed. This book is a detailed overview over the area.
  • Advanced Data Structures by Brass
    Sometimes, the basic techniques are not enough. This is an overview over advanced data structures, with code and many references.
  • Algorithmics for Hard Problems by Hromkovič
    Complexity theory tells us (as practitioners) not to bother looking for exact yet efficient algorithms for many natural problems. There are plenty of techniques for practically solving these problems; this text shows you how.

• Specialised Literature

  • Compilers: Principles, Techniques, and Tools aka The Dragon Book by Aho et al
    Should you ever need to build or tinker with a compiler, this is the standard text on the area.
  • Network Flows: Theory, Algorithms, and Applications by Ahuja
    Many problems can be modeled as network flow problems; this book gives you a full coverage of the field.
  • Probabilistic Graphical Models by Koller and Friedman
    Graphical models are a major tool in modeling scenarios for machine learning (among others) probabilistically. This is a comprehensive overview about the complex. There is a related free online course.
  • Handbook of Exact String Matching Algorithms by Charras and Lecrog
    String matching is an ever important task when dealing with data. This book lists most (if not all) relevant algorithms for the job, including high-level descriptions as well as implementations.
  • Analytic Combinatorics by Sedgewick and Flajolet
    The deep mathematical dive after "An Introduction to the Analysis of Algorithms" by the same authors. Not for everybody, but gold for the interested.
  • Algorithms on Strings, Trees and Sequences by Gusfield
    Should you ever have to deal with huge amounts of string data (in particular in biology contexts) this is the go-to book as it provides an overview over the relevant data structures and algorithms.

• For the Practitioner

  • Patterns for Parallel Programming by Mattson et al.
    In practice, you might want to utilise multiple machines to deal with large problems. This book is a high-level, example-driven overview over ways to do so, that is how to organise and move data and computing agents. It also addresses ways to implement them with existing tools.
  • A Guide to Experimental Algorithmics by McGeoch
    When theoretical analysis is too hard or too coarse, you have to perform experiments. This is an introduction into how to properly design experiments on algorithms.
  • The Definitive ANTLR 4 Reference by Parr
    You often need domain specific languages and tools to parse them. ANTLR is a mature and convenient compiler generator, and this is the book best suited for learning how to use it. Parr also has some other books on DSLs worth checking out.

If you want very recent material, you should consider getting your people access to journals and conference proceedings, maybe by cooperating with a university library. You can also actually let them attend conferences on topics relevant to them resp. your company.

Also, consider asking your people. Have them do their own research (including free samples or copies on the web or libraries) and they will tell you which books they consider relevant to their work. There is no use in buying stuff no one will read.

Answer 2

Here is a random collection of books on advanced algorithms based on what I consider as great book about advanced algorithms. Of course this is only my personal opinion and there are many other good books.

• Approximation Algorithms by Vijay V. Vazirani
• The Design of Approximation Algorithms by David P. Williamson, David B. Shmoys
• Computational geometry: an introduction through randomized algorithms by Ketan Mulmuley
• Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan
• Algorithms on Strings, Trees and Sequences by Dan Gusfield
• Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver

you should definitely consider the Kleinberg/Tardos book, which is just a great textbook.

Also you should know that on certain topics there are "handbooks" which give an encyclopedic overview over a field (for example the Handbook of Computational Geometry). edited by J.R. Sack, J. Urrutia. Notice that these handbooks are pricy. So buying them might help you to spend the 5k.

Answer 3

You don't specify what your company specializes in, so it's not easy to provide more than general recommendations. On the whole, I think the list you've put together is pretty good, and I wouldn't remove anything from it. Just a couple of additions and comments:

1) Cormen is a standard text. Sedgewick is another standard text. I've always gotten more out of Sedgewick but YMMV. You seem to have the budget. Buy both.

2) I don't have a copy of "The Garbage Collection Handbook" but I do have a well-thumbed copy of Jones&Lin's earlier survey on garbage collection. If you intend to do any sort of automated memory management, you should definitely buy this one.

3) You've also got several useful books on parsing and automata theory, but you're missing the two books (three volumes) which I've found most useful: Sippu & Soisalon-Soisinen's Parsing Theory, and Dick Grune's Parsing Techniques, a Practical Guide. The first is a great overview of the theory, and the second an exhaustive overview of the practice. (By all means, get the dragon book, too. But I'll bet you'll end up using Grune more.)

4) Every library on data structures requires a copy of Okasaki's "Purely Functional Data Structures". I don't think I've ever read any book this slim with so many interesting ideas.

5) I don't own a copy of Maxime Crochemore's "Algorithms on Strings", but I wish I did. Highly practical, lots of useful ideas.

• Algorithms in C++/Java/C (select one), Third Edition by Robert Sedgewick. Two volumes. Addison-Wesley, 2001.

• The Garbage Collection Handbook by Richard Jones, Antony Hosking and Eliot Moss.

• Parsing Theory, by Seppo Sippu and Eljas Soisalon-Soininen. Two volumes: Vol . 1 Languages and Parsing; Vol. 2 LR(k) and LL(k) Parsing. Springer, 1988.

• Parsing Techniques, A Practical Guide, Second Edition by Dick Grune and Ceriel J.H. Jacobs. Springer, 2008.

• Purely Functional Data Structures by Chris Okasaki. Cambridge, 1998.

• Algorithms on Strings by Maxime Crochemore, Christophe Hancart, Thierry Lecroq. Cambridge, 2007.