Author: Paolo Ferragina
Publisher: ‎Cambridge University Press
Pages: 326
ISBN: ‎978-1009123280
Print:1009123289
Kindle: B0BZJBGTLN
Audience: Admirers of Knuth
Rating: 5
Reviewer: Mike James

Algorithm engineering - sounds interesting.

Who isn't interested in algorithms? Well, if the truth be told, a great many programmers. Basically we all want to know how to do something, but delving into the details of fundamental algorithms - not so much. It is often considered the preseve of nerdy computer scientists and yet understanding the way algorithms behave as the task gets bigger is fascinating and worth a look - but if it is your first look this isn't the book for you.

This is a second-level book that examines algorithms in terms of both time and I/O operations. This means that we not only examine the time-complexity of algorithms, but the I/O -complexity, something that is more practically relevant, but mostly ignored.

It is also worth saying that while "Pearls" features in the title this is not a book in the model of the classic "Programming Pearls". This doesn't make it a worse book, but you might be expecting short general pearls of wisdom whereas what you actually get is something that need quite detailed study.

The book starts of with a warm-up a look at the problem of finding the subset of an array of integers that has a maximum sum. You can see already that the type of algorithm being discussed is more towards the combinatorial than mathematical or geometric. This is not a problem as the main thrust of the book is how you analyse an algorithm, rather than the algorithms explained. This said I enjoyed trying to figure out for myself what a good algorithm might be - but again if this is not the sort of thing you like to do then this book will be wasted on you.

The next chapter is on random sampling - something you might have thought was easy but in this case the samples are taken from a sequence being read in or generated in real time.

Chapter 4 is on List ranking and is about working out how far each item is from the start of the list. Next we have a longish chapter on sorting atomic items starting with merge-based sorting. The final chapter is on finding set intersections and is quite short.

This is a good book but you have to be the right reader to appreciate it. If you like, even a little bit, anything by Donald Knuth, then this is book you will enjoy and learn a lot from. It isn't an easy read and there is a lot of math notation if not deep mathematics. Its real value is that, if you think that the analysis of algorithms stops at time-complexity this will open your eyes to a bigger world.

To keep up with our coverage of books for programmers, follow @bookwatchiprog on Twitter or subscribe to I Programmer's Books RSS feed for each day's new addition to Book Watch and for new reviews.