9 Algorithms that changed the Future by John MacCormick
I thought this book was really good. It is isn’t very technical but explains several interesting algorithms using simplified examples in a way that makes the algorithm very clear. In some cases, various technicalities are missed out, but the general idea behind the algorithm is explained brilliantly.
What makes the book even better is the fantastic choice of algorithms that the author has picked. The chosen algorithms really are things that we have our computers do every day. Indexing web pages so that they can be efficiently searched and page ranking are the two algorithms that are covered first. Public key cryptography, used to secure web connections, and digital signatures, used for ensuring that a program we download really came from the expected publisher, are both covered really well. Transferring data across the internet relies on data compression and some use of error correcting codes. Most of the data stored around the world is stored in databases, so its important that the consistency of transactions can be maintained.
There are two other algorithms that are covered that don’t really fit into this pattern. There is a discussion of algorithms for pattern matching, in particular using neural networks to learn from examples in a scenario where there is no real algorithm. And a very good chapter on computability, covering the proof that there are things that a computer cannot do.
The author emphasises the clever ideas behind the algorithms, and really communicates a love for computer science without the book becoming too technical at any stage.