9 algorithms that changed the future - John MacCormick: Book Review
Date: 2013-08-13 20:00:45

== The Book

http://www.amazon.co.uk/Nine-Algorithms-That-Changed-Future/dp/0691158193/ref=sr_1_1?ie=UTF8&qid=1376332180&sr=8-1&keywords=9+algorithms+that+changed+the+future[9 algorithms that changed the future (the ingenious ideas that drive today's computers)] by John MacCormick

== My Thoughts

I came across this book while idly browsing http://www.foyles.co.uk/[a book store] and since I've found most introduction to algorithms books very dry I thought it'd be interesting to see what one aimed at the general public would be like.

Overall it was an enjoyable read and I quite like the pattern that the author used for each algorithm, which was:

* Describe the problem that it's needed for.
* Explain a simplified version of the algorithm or use a metaphor to give the general outline.
* Explain which bits were simplified and how the real version addresses those simplifications.

The first step is often missed out in algorithms books which is a mistake for people like me who become more interested in a subject once a practical use case is explained.

Although the title claims 9 algorithms I counted the following 8 which made the cut:

* http://en.wikipedia.org/wiki/Search_engine_indexing[Search Engine Indexing] - this chapter covers how you'd go about writing the part of a search engine which works out which pages are applicable for certain search terms. It effectively describes http://lucene.apache.org/core/[Lucene].
* http://en.wikipedia.org/wiki/PageRank[Page Rank] - this chapter described Google's PageRank which was particularly timely for me as I've recently been http://www.markhneedham.com/blog/2013/08/05/javajblas-calculating-eigenvector-centrality-of-an-adjacency-matrix/[playing around with some similar algorithms]. The author works step by step through the algorithm using a simple example covering it very throughly. The best thing I've seen on the web is http://williamcotton.com/pagerank-explained-with-javascript[PageRank explained with Javascript] although that is slightly more technical than the book. I didn't realise that Sergey Brin and Larry Page had published a paper back in 1998 titled 'http://infolab.stanford.edu/~backrub/google.html[The Anatomy of a Large-Scale Hypertextual Web Search Engine]' which explains the initial PageRank algorithm in more detail.
* http://en.wikipedia.org/wiki/Public-key_cryptography[Public Key Cryptography] - this chapter mostly covers http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange[Diffie-Hellman key exchange] which I realise is quite well explained on wikipedia as well.
* http://en.wikipedia.org/wiki/Error_detection_and_correction[Error-Correcting Codes] - I took the http://en.wikipedia.org/wiki/Checksum[checksums] included in somewhat for granted but in this chapter MacCormick goes through the problem of data getting lost or corrupted in transfer and iterates through potential solutions. The further reading from this chapter is 'http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf[A Mathematical Theory of Communication]', http://en.wikipedia.org/wiki/Hamming_code[Hamming code] and http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction[Reed-Solomon error correction].
* http://en.wikipedia.org/wiki/Pattern_recognition[Pattern Recognition] - this chapter covered a variety of machine learning algorithms initially focusing on digit recognition - something that Jen Smith and I spent http://www.markhneedham.com/blog/tag/kaggle/[a chunk of time working on last year for the Kaggle problem]. The three algorithms covered are http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm[nearest neighbours], http://en.wikipedia.org/wiki/Decision_tree[decision trees] and http://en.wikipedia.org/wiki/Artificial_neural_network[neural networks], all of which we attempted! I recently came across the concept of http://deeplearning.net/tutorial/lenet.html[convolutional neural networks and deep learning] which I've yet to try out but are apparently even more accurate than plain neural networks.
* http://en.wikipedia.org/wiki/Data_compression[Data Compression] - I imagine data compression would be one of the more familiar algorithms on this list since everybody knows how to 'zip up a file' and send it around. The author covers lossy algorithms such as 'http://bitdepth.thomasrutter.com/2010/02/02/how-jpeg-and-mpeg-picture-compression-algorithms-work/[JPEG Leave it Out]' which reduces image quality as well as size, as well as lossless algorithms such as http://en.wikipedia.org/wiki/LZ77_and_LZ78[LZ77], http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding[Shannon-Fano coding] and http://en.wikipedia.org/wiki/Huffman_coding[Huffman coding]. The latter is covered in https://class.coursera.org/algo2-2012-001/lecture/preview[Stanford's Algorithms II] and I think the explanation there is actually easier to understand than the book's.
* http://en.wikipedia.org/wiki/Database[Databases] - this section mostly focused on how http://en.wikipedia.org/wiki/ACID[ACID] compliant relational databases work and covered things like the http://en.wikipedia.org/wiki/Write-ahead_logging[write ahead log] and index lookups. The recommended reading from this chapter is http://www.amazon.co.uk/Transaction-Processing-Concepts-Techniques-Management/dp/1558601902/ref=sr_1_1?ie=UTF8&qid=1376421544&sr=8-1&keywords=transaction+processing+jim[Transaction Processing: Concepts and Techniques]. Given the fact that many of the popular websites that people use tend to use NoSQL stores these days I thought there might be some mention of that but it was left out.
* http://en.wikipedia.org/wiki/Digital_signature[Digital Signatures] - this chapter ties in quite closely with the one on public key cryptography. It focused on signing of software with a digital signature rather than the signing of emails which is what I expected the chapter to be about. The http://en.wikipedia.org/wiki/RSA_(algorithm)[RSA algorithm] is described and the link between the difficultly of http://en.wikipedia.org/wiki/Factorization[factoring] large numbers and the security of the algorithm is explained.

I enjoyed the book and I've got some interesting articles/papers to add to my reading list. Even if you already know all the algorithms I think it's interesting to hear them described from a completely different angle to see if you learn something new.