Tuesday, December 14, 2010

What is an algorithm?

Q: Why does no one implement my algorithms?
A: Because almost invariably there is a step that says: "By exhaustive search over a space S of size some-huge-constant, compute some optimum".

I've been mistaken all along. I should not write "by exhaustive search" but simply "compute some optimum over S". Who am I to tell a programmer that he absolutely must use exhaustive search? If he finds a better way to compute the optimum, so much the better. In the section analyzing running time, I could always state: "Using exhaustive search for example, the optimum over S can trivially be computed in constant time."

The theorem is the interface between me and the complexity theorist (who does not care how the problem is solved algorithmically, but only that the problem is solved and about the related structural insights).

The algorithm is the interface between me and the hypothetical programmer who might some day be interested in implementing my algorithm (and who does not care about why, in the analysis, the algorithm works). That's what should drive what to specify and what not to specify in the description of the algorithm.

If I mix in some critical ideas with some steps where I just threw in the first thing that came to my mind to solve that subproblem, how is he supposed to separate the wheat from the chaff and know which of my instructions should be followed carefully and which ones are open for him to play with and optimize?

1. Hi Claire! I hadn't known you were blogging. Congratulations -- I for one will be a regular customer.

I both agree and disagree with a lot of this post, so I'll express some of my point of view. At a high level, rather than point out the issue of how we specify solving subproblems, I'd suggest there's a more significant problem: most theorists who do algorithms intend for their audience to be (primarily) complexity theorists rather than the hypothetical programmer, and write accordingly. The issue you point out is one example of that issue, but there are many others -- I've often argued that perhaps the most important is that theorists don't themselves implement their algorithms, and that both fails to inspire confidence and hides the possible utility of a new algorithm.

Also, just a quibble, but there are many programmers -- or at least non-theory researchers -- who would care very much to understand, to a significant degree, why an algorithm works. They understand that they may have to tweak it for their own setting, and understanding can help with that. That's one good reason (among others) to write a high-level explanation of the proof of your algorithm before delving into deeper mathematical details.

2. Nevertheless, the point is very true that theoreticians will merely throw in the first thing that comes to mind as long as the O() bound is safe. I've lost track of the number of times some student has come to me with a theorem asking, "why is the bound 153.25 times some term" (or some other bizarre number) and my only answer was, "because the authors didn't bother to think too much about the numbers".

3. Michael, my larger question is: "What is a principled approach to good writing?"

As a guideline I am proposing to write an algorithm as if I was presenting it to someone who was as familiar with algorithms as I am, but who was going to implement it, and whose primary goal would be to get the minimal information necessary and sufficient for implementation. That's my "hypothetical programmer".

Of course this may be largely moot since nobody reads anything by anyone anymore anyway.