patternModerate
Algorithm books on a range of topics
Viewed 0 times
algorithmbookstopicsrange
Problem
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 b
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 b
Solution
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
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.
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.
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.
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.
Basic techniques for precise analysis of algorithms. Written by the
pioneers of the field. Also has a free online course.
The reference for high-quality, low-level, precisely analysed
algorithms for a whole range of problems. Also serves as reference.
-
Advanced Surveys
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.
Sometimes, the basic techniques are not enough. This is an overview over
advanced data structures, with code and many references.
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
Should you ever need to build or tinker with a compiler, this is the
standard text on the area.
Many problems can be modeled as network flow problems; this book gives you
a full coverage of the field.
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.
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.
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.
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
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 Paralle
Context
StackExchange Computer Science Q#9413, answer score: 18
Revisions (0)
No revisions yet.