These are some of the books we've found interesting or useful.
Multicore Application Programming: for Windows, Linux, and Oracle Solaris (Developer's Library)
Darryl Gove, Addison-Wesley Professional , 2010.
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.
SQL Antipatterns: Avoiding the Pitfalls of Database Programming (Pragmatic Programmers)
Bill Karwin, Pragmatic Bookshelf , 2010.
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.
Computational Geometry and Computer Graphics in C++
Michael J. Laszlo, Prentice Hall
An area which Knuth doesn't really cover is
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,
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.
A Programmer's Geometry
Adrian Bowyer, Butterworth-Heinemann
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.
The Art of Readable Code (Theory in Practice)
Dustin Boswell, Trevor Foucher, O'Reilly Media , 2011.
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.
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.
Bundle of Algorithms in C++, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Pts. 1-5)
Robert Sedgewick, Addison-Wesley Professional
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
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.
24 Deadly Sins of Software Security: Programming Flaws and How to Fix Them (Networking & Comm - OMG)
Michael Howard, David LeBlanc, John Viega, McGraw-Hill Education , 2009.
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.
Data Mining: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems)
Jiawei Han, Micheline Kamber, Jian Pei Professor, Morgan Kaufmann , 2011.
Good algorithm descriptions. Covers the major areas in reasonable
technical detail, with several alternative algorithms presented
for classification, prediction, association rule induction and cluster
The Art of Computer Programming, Vols. 1-3
Donald E. Knuth, Addison-Wesley Professional
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!
The New Turing Omnibus: Sixty-Six Excursions in Computer Science
A. K. Dewdney, Holt Paperbacks
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.
Data Mining for Association Rules and Sequential Patterns: Sequential and Parallel Algorithms
Jean-Marc Adamo, Springer
Strictly a specialist book. The title says it all.
Data Model Patterns: Conventions of Thought
David C. Hay, Dorset House
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.
Programming Pearls (2nd Edition)
Jon Bentley, Addison-Wesley Professional
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.
The 85 Ways to Tie a Tie: The Science and Aesthetics of Tie Knots
Thomas Fink, Yong Mao, Fourth Estate Ltd
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
The book also contains an entertaining history of ties: you'll certainly
want to try some different tie knots after reading the book.