computer science, math, programming and other stuff
a blog by Christopher Swenson

Algorithm styling?

So I've started to come across the algorithm-heavy portion of the book, and starting to come across some issues. Specifically, how should I properly typeset algorithms?

My requirements are that the algorithms should be

• Clean
• Precise
• Not heavy with obscure symbols
• Generic

This means things like the Knuth style (as he uses in The Art of Computer Programming, which is widely copied) and the Cormen, et al. style (as used in the monolithic Algorithms, 2nd ed., also widely copied are out). Knuth's still has some good pointers, but it seems like there is too much there (such as a small summary of the step at the beginning, along with step numbers with the letter of the algorithm in front). I like how verbose he is: others seem too compact. And with Cormen, there is too much use of symbols, and computer programming pseudo-code.

My current solution is some kind of hybrid between normal prose text and a normal algorithmic style, though I avoid using symbols like ← and &lfoor;x⌋ in exchange for phrasing like "Set x to ...", even more so than Knuth. Though computer scientists and strong programmers might find the way a bit clunky, I find breaking every step down into more discrete steps, with explanations at each step to be potentially helpful to a confused reader. However, I also want things to be minimalistic when possible: the meat appears immediately, so that it is possible to stream through it with your eyes very quickly.

For example, let's take a simple algorithm, computing the sequence 1 + 2 + 3 + … + n, in each of the three methods.

Cormen, et al., might write:

Sum-to-n(n)

1  x ← 1
2  s ← 1
3  While xn
4  xx + 1
5  ss + x
6 Return s

Whereas a Knuthian way might be:

Algorithm A (adding the series of m numbers). This algorithm outputs the sum of all the integers between 1 and n.  K1. [Initialize.]. Set x ← 1, s ← 1.
K2. [Test for loop end.]. If x = n, terminate. The sum will be s.
K3. [Loop through.]. Set xx + 1, ss + x.
K4. [Repeat.]. Go back to K2.

My proposed way is similar, but with a little less stuff in it:

The following algorithm illustrates how to sum up the integers from 1 to n, inclusive of 1 and n.  1. Set x = 1, and s = 1. These will represent the current number to be added and the working sum, respectively.
2. If x = n, then we can stop, and the sum will be s.
(a) Set x = x + 1, s = s + x. We are incrementing the counter variable x and updating our sum.
(b) Go back to step 2.

Out of the above, Knuth's looks best on this web page, but I think that mine can look better with wide margins, and provides for a little less ambiguity.

And happy belated 4th of July to everyone!