Combinatorial Algorithms - Donald L. Kreher and Douglas R. Stinson

A bit of a funny book, this. It discusses algorithms to do with combinatorics, as one might expect! It's a real grab-bag, though. It starts with things like subsets, permutations and partitions, and the counting and enumeration thereof. It then moves into various forms of heuristic search for problems with are otherwise exponential, and then goes weird, talking about algorithm for representing groups, isomorphisms on graphs, and basis reduction. It finishes off by showing a way to break the Merkle-Hellman knapsack cryptosystem system.

Reading through it, it feels like it's going all over the place, but at the end it feels like there's a structure - they wanted to write on a few advanced structures, but needed to build everything up first. The bits at the end get pretty hardcore. The full graph isomorphism stuff is pretty funky, and the chapter on basis reduction brings in LLL, albeit without really introducing it well.

I think this is the weakness of the book - it's just not presented well. There's a lot here, in the rambling path it takes, but mining it can be painful. This ranges from the ugly layout through to the awful pseudocode, through to the strangely ill-paced prose. There are some nice examples, but it's mixed in with an otherwise quite dodgy exposition. Admittedly I'm spoiled by the clarity of Cormen et al's Introduction to Algorithms, but even comparing this book to some maths texts, it's dodgy. It may not be as terse as those, but it's still a bit less readable.

Overall, it's still a good book. The topics are interesting, there are algorithms in here which'll save you effort if you're working on Project Euler, and it's challenging and different. I'm just disappointed by the presentation.

Posted 2009-07-29.