Recommended books on Algorithms

Good algorithm descriptions. Covers the major areas in reasonable technical detail, with several alternative algorithms presented for classification, prediction, association rule induction and cluster analysis.

If you're looking for something more readable than Knuth, then Sedgewick fits the bill. Cited is the 3rd edition based on C++, which I'm less familiar with than my much older edition which used Pascal for examples.

The advantage of Sedgewick is his readability and wide range of topics. I've used an earlier edition of this work to find and implement many useful algorithms.

Warning: later editions aim to be more comprehensive — I think readability suffers a little as a result. Personally I prefer the older editions.

If you are a computer science professional you probably already own these books.

Need to know the computational complexity of Quicksort? The worst case performance? The conditions under which the worst case performance will occur? A method of choosing a random record from a sequential file of unknown size? How to multiply large numbers efficiently? How to sort with limited memory? How to sort with less comparisons than N logN?

It is rare, indeed that you can't find the answer you need in Knuth.

These are reference books, however. Don't expect to work through them and answer all the questions at the end of each chapter. (Some of the questions are literally PhD topics!) If you are serious about computer science, you should have a working knowledge of what is in these books so that you can refer to them when necessary. And, of course, you should have them in easy reach so that you have the answers when you need them!

Strictly a specialist book. The title says it all.

There are lots of algorithms out there to do lots of things... But what are the most interesting and important algorithms in Computer Science?

I think Dewdney's book answers this question, and does it in an entertaining and thoughtful way. This is not a book from which to implement algorithms (there isn't always sufficient detail for that), but it is a readable book with which to acquaint yourself with some of the most important problems and solutions in computer science.

Note: if you didn't major in computer science, this book contains the key algorithms you should know and probably missed.

I can still remember vividly reading the first edition of this book, as well as the column on which it was based. Bentley tackles pratical programming problems he has encountered, moving clearly from problem to solution (and explainingsome of the pitfalls) in the way only a seasoned professional can.

Key parts of problem solving is solving the right problem and choosing the right solution. You can't help but improve both skills reading this book.

An area which Knuth doesn't really cover is computational geometry.

This introductory book explores some of the basic algorithms in computational geometry, dealing with convex hulls, point enclosure, polygon clipping, hidden surface removal, line intersection, closest points, range searching with grids, quadtrees, etc.

The topics are covered clearly, and well explained. (The introductory chapters of this book also contain one of the best descriptions of complexity measures and "Big-O" notation I have come across.)

Note. One of the reviewers on Amazon.com comments that this book omits some recent and faster algorithms for performing some key tasks. This may or may not be important for you.

What's a book about tying a tie doing in a list of recommended books on algorithms?

The answer is that this book clearly demonstrates how to analyze and solve a complex problem. Fink and Mao develop a mathematical notation for different tie knots, identify key criteria related to aesthetics and tie length, then use those criteria to generate all possible tie knots, identifying the 13 with the greatest aesthetic qualities.

The book also contains an entertaining history of ties: you'll certainly want to try some different tie knots after reading the book.

If you just want to find intersections of lines, intersections of lines with planes, and so forth then something like Laszlo is overkill.

This older title gives you what you need, including consideration of all the degenerate conditions which have to be taken into account, and which are often omitted from more cursory treatments of the topic.

This book is out of print and can be a little hard to find. The library of a company I worked for used to have a copy, and it proved an invaluable reference.

This is a useful introductory text on systems analysis. Most books in this category are too academic: systems analysis is a pratical art. Rather than give lots of theoretical example, this book gives typical solutions for common corporate functions, along with explanations of why the design is the way it is and not what you might have thought it should be.

Worth a read if you're new to the art, as it will definitely save you from making some easy mistakes.

We all know that we should write readable code, and we've all been cursed when faced with reading somebody else's monstrosity (or even sometimes one of own). However, there are surprisingly few books on the subject.

This book explains the basics of writing readable code, with examples in C++, Javascript, and Python. It covers naming conventions, choosing good names, making your code "pretty", comments, brevity versus simplicity, and many other topics (on which you have probably had impassioned debates with colleagues) in a light-hearted, not-too-prescriptive way.

Towards the end of the book, I thought initially that the book seemed to be delving too far into specific structured programming techniques. But then I remembered that structured programming techniques were the answer invented to deal with unreadable code, and this line of approach didn't seem unreasonable.

It's not a reference book. It's a quick read, and you will probably read this book once or twice and (hopefully) learn something from it rather than retain it as a reference book for future use.

It's often tempting to ignore program optimization: modern CPU's are fast enough that for applications which involve trivial amounts of computation, optimization is rarely necessary.

However, for scientific and technical computing, where computations can take hours or days to complete, or for applications involving media processing, optimization is essential. Once an efficient algorithms has been chosen, the next problem is to get that algorithms to run as fast as possible on a modern computer architecture. This is where this book comes into its own.

The author, Darryl Grove, provides a good overview of of modern multi-core computer architectures, and in particular the trade-offs associated with multiple cores, multiple threads, and multiple caches. He then explains how these impact the efficiency of programs, and how simple changes to program code and data structures can cause a program to run significantly more or less efficiently on a given architecture.

One thing I particularly liked about this book is that it recognizes the strengths and weaknesses of current compilers: it is increasingly rare that an assembler programmer can outdo the performance of compiler produced code, and the maintainability of such code (as well as its portability) is often suspect. However, optimizing compilers have their limitations and require hints and language extensions to be able to make effective use of available parallelism.

A good section of the book therefore covers OpenMP, a widely implemented set of features/pragmas available in C, C++ and other languages which enable a program to be optionally parallelized for improved performance while still preserving the ability to revert to single threaded mode. (OpenMP features are available in Microsoft Visual C++ compilers, as well as in the open source gcc compiler). Before reading this book, I wasn't aware how easy OpenMP makes parallelizing many common computations. In particular, there is a good section demonstrating how the addition of a single pragma can distribute the execution of a for loop across multiple threads and, in the cases considered, provide near linear speed-ups up to the number of cores available.

The section on locks and synchronization provides some cautionary examples of unintentional race conditions for create-your-own lock schemes. (Tip: compiler optimization and code re-ordering may and probably will totally destroy your intended semantics) , and a good overview is provided of the wide variety of primitives available in Windows, OS X, Solaris, and Linux.

Finally there is a good section on the constraints to application scaling, including the use of library code, hardware constraints, and operating system constraints.

I would therefore highly recommend this book if you need to write compute-intensive code which will run in a multi-core environment.

When writing SQL its quite common to "steal" somebody else's example: but is that example a good example or a bad example? Is it efficient? Will it scale? Or will it cause problems with the database structure later on? Without a reasonable knowledge of SQL in practice, it's quite difficult to tell good examples from bad examples.

Bill Karwin's book examines "antipatterns" for SQL — code that is commonly used but generally shouldn't be. He outlines cases where the antipattern is a legitimate approach, as well as alternative solutions which will eliminate some of the problems which the original code creates.

If it's only to learn the best ways to choose a random record from a large data set (SELECT * FROM table ORDER BY RAND() LIMIT 1 isn't one of them), then it's worth reading this book.

Most books about hacking and software vulnerabilities are terrible. This one is actually quite good.

The reason most books are terrible is that they concentrate on specific vulnerabilities and don't draw general lessons. The information they give therefore relates to very specific vulnerabilities which are generally long-fixed by the time the book appears in print. They offer little of interest either for the hacker, or for the software designer or programmer who must design a secure system. You can probably find a dozen such books discarded in your local thrift store.

This book is actually one worth having.

The authors provide general observations of classes of errors, along with examples of when these errors have been made in the past, and how to identify such errors in a design or source code. It's not a perfect book: too much of the early chapters are spent demonstrating particular coding errors in a variety of computer languages , and perhaps some of the later chapters are too cursory as a result — but it's one of the few books on the topic that I expect to be worth keeping and re-reading in more than a year's time.