Another book I came across when refreshing the more practical computer science skills was Jon Bentley’s Programming Pearls (second edition), composed of columns — blog posts, I suppose, by today’s terminology — written by him for the ACM back in the 1980s. And while it is somewhat outdated in terms of technology, the strength of this little book lies in something entirely more timeless.
The book covers several topic within software construction, including programme verification, testing, and code tuning, but most pages concern the construction of good algorithms to solve a given problem. Incidentally, one of my favourite problems from the book was posed to me at a job interview, supporting the claim that the book is well-known within the software community, at least by senior staff (as a side-note, I mentioned that I’d already encountered the problem from reading this book, and funnily enough that almost seemed as good an answer as an algorithm).
The problem was this (section 2.4 and 2.8):
Given a dictionary of words, find all sets of anagrams.
The good thing is that the book not only poses interesting questions, it also discusses several solutions, comparing them in terms of time and space efficiency. For the anagram problem above there’s the brute force approach as usual, yet as soon as you remember equivalence classes and their representatives you’re close to a much better algorithm.
Another favourite was presented in chapter 8:
Given a array of
nintegers (positive and negative), find a maximum sum contiguous subarray.
For instance, in
[ 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 ] one solution is
[ 59, 26, -53, 58, 97 ] with sum 187, obtained by removing the first two and last three elements. Again there’s the obvious brute force approach — e.g. computing the sum for all C(n, 2) pairs of indices — but by a bit of dynamic programming it’s possible to reach an O(n) algorithm that only scans the array twice.
Now, as mentioned above, the book does not just talk about algorithms but through various topics aims to improve your overall programming skills. And for that I recommend it highly: it will probably not teach you a new technology but it might improve the quality of your code.
Which brings me to a pattern I’ve noticed over the years: my technology books usually end up somewhere in the basement, mostly kept for nostalgic reasons, whereas books like this one, focusing on the fundamentals, are much more likely to still sit high on my office bookshelf, and as such still attractive to buy in dead-wood format.