18
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Books that every library should have: * Algorithm Design by Jon Kleinberg and Éva Tardos * Introduction to the Theory of Computation by Michael Sipser * Computers and Intractability: A Guide to the Theory of NP-Completeness by M. R. Garey and D. S. Johnson $\endgroup$
    – Pål GD
    Feb 2, 2013 at 9:52
  • $\begingroup$ > * Introduction to the Theory of Computation by Michael Sipser This is a great book, but it is more about Automata and Languages, Context-Free-Languages, Turing Machines, Complexity Theory and so on. It is not much about Algorithms $\endgroup$
    – Devid
    Feb 2, 2013 at 10:41
  • 1
    $\begingroup$ Wow, this is a broad question. How do you expect to verify the quality and coverage of the selection? What is your background? What does your company work on? Do you have people with master degrees or doctorates? $\endgroup$
    – Raphael
    Feb 2, 2013 at 14:01
  • 1
    $\begingroup$ Moderator notice: please do not post single-book answers, and please explain why you're making these choices. There's a $5k budget here: explain how you would spend it! Tell us which books you think are must-have, which topics should be explored further, how you make your selection... $\endgroup$ Feb 2, 2013 at 15:21
  • $\begingroup$ Are you mainly interested in design, or also in analysis of algorithms? If so, do you want your people to get competent in theoretical analysis, or would you rather they were proficient in more practical means of evaluating efficiency? $\endgroup$
    – Raphael
    Feb 2, 2013 at 15:43

3 Answers 3

18
$\begingroup$

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.

  • 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.

$\endgroup$
3
  • $\begingroup$ And, of course, send them here with their interesting problems. :) $\endgroup$
    – Raphael
    Feb 2, 2013 at 21:03
  • 2
    $\begingroup$ What about The Algorithm Design Manual? $\endgroup$ Feb 3, 2013 at 9:51
  • $\begingroup$ @Bartek: Never heard of it, so I can't recommend it. $\endgroup$
    – Raphael
    Feb 3, 2013 at 10:04
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You say this is a "random" collection. Do you have particular reasons for recommending those books? What should the OP do with the remaining $4.5k? $\endgroup$
    – Raphael
    Feb 2, 2013 at 15:41
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.