Tag Archives: CLRS

Book: Programming Pearls

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 n integers (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.

Book: Programming Interviews Exposed

In my preparation for potentially taking on a general software developer role, Programming Interviews Exposed was recommended to me on several occasions and hence gave it a shot. It’s not too bad a read, and would most likely recommended it in the future, despite is having a few glitches; at the very least, it serves its purpose as a good source of concrete problems to solve.

Overall the book has the decent “Wrox feeling” I remember from way back in the days of secondary school reading Professional ASP.NET and Professional C#, and later Beginning Visual C++ 6 in the early university days (fond memories of a world opening up): on the surface the paper feels the same, even a few pages with faded print, and the contents is the same easy-to-read-yet-with-good-substance. It contains some good non-technical advise as well, so for its price I don’t see why anyone looking for a job in this area (and perhaps a bit rusty in the practical areas of computer science) shouldn’t pick up a copy.

The trees do not grow all the way into Heaven though, as the Danish saying goes, and there are a few place with room for improvement; for the interested here’s my two cents.

First of all, the writing follows the idea that the reader could have come up with every step of reasoning the authors take by just thinking the right way (and not letting much room for the use of prior knowledge). When coming up with a proposal, this approach may seem a bit strange yet it still teaches you the tricks. However, in analysing a solution they often skip arguments that could potentially teach you something. As a concrete example, the two-pointer solution for detecting cycles in a linked list (page 60 in the third edition) seems more like a useful trick to know than something I would have come up with in an interview situation; fair enough I’ve now learnt it. However, they give no argument to the claim that it has a linear running time; while I may not see the obvious, coming up with a proof was a useful exercise, taking me a car ride and the use of modular arithmetic to find. In short, you’ll need to look elsewhere for brushing up on proving and analysing algorithms (go Cormen et al.!).

Secondly, the given solutions sometimes seem to ignore standard mathematical thinking, and simply brute force their way through, in turn making it more confusing (at least to me) than it has to be. One concrete example is the problem of generating all combinations of characters in a string (page 116 in the third edition), which has a simple mathematical formulation in the form of the power set that also leads to an easy recursive implementation. Yet they do not follow nor mention this approach, instead doing a lot of hand-waving to end up with something that works but leaves me less certain about its correctness (their solution leaves out the empty string for instance, which may or may not be an error, but at least we know when the goal is a well-known concept such as the power set).

Thirdly, they do not always follow the official Java code conventions, which honestly seems a bit silly after several companies have highlighted the importance of this during interviews. For instance, the following code (page 93 in the third edition):

public void foo(String str) {
    int i, length;
    Character c;

    length = str.length();
    for (i = 0; i < length; i++) {
        c = str.charAt(i);
        // do first scan ...
    }
    for (i = 0; i < length; i++) {
        c = str.charAt(i);
        // do second scan ...
    }
}

goes against both the advise on initialisation at the point of declaration (length) and declaring local indices within their for-loop (i). Although a bit contradictory, it also goes against the advise given in Effective Java (Item 45 in the second edition) of not declaring a variable before use (c). To me, rewriting the code to this:

public void foo(String str) {
    int length = str.length();
    for (int i = 0; i < length; i++) {
        Character c = str.charAt(i);
        // do first scan ...
    }
    for (int i = 0; i < length; i++) {
        Character c = str.charAt(i);
        // do second scan ...
    }
}

seems both safer and easier to follow.

That was a lot of bashing actually; let me just make sure to express that overall I enjoyed reading the book, and almost all problems in it are interesting and with an entertaining side; of the latter I especially liked the pancake sorting algorithm. So, getting a copy is not a bad idea!

If curious, my programming solutions are available at the progin project on GitHub.