Tuesday, July 8, 2008

Breadth-First Numbering: An Algorithm in Pictures

I've always enjoyed the mathematical tradition of “proofs without words”, so I wanted to see if something similar could be done with an algorithm. Of course, an algorithm is typically more complicated than a mathematical identity, so it's not surprising that an algorithm typically can't be captured in a single picture. Instead, I've found the idea of a commutative diagram to be a useful pictorial shorthand, where the short way around the diagram gives a high-level view of the operation, and the long way around gives more detail. Here is an attempt to describe my breadth-first numbering algorithm from ICFP 2000 using this idea.

Wanted

Rules

Example

3 comments:

CH Gowri Kumar said...

Cool. I have tried to do similar things here: Visualizing algorithms and data structures

Stephan Schroevers said...

Way cool. For those interested, the paper is online (Postscript, other formats here).

kragen said...

This reminds me of Aardappel, a programming language in which you write programs in the form of such before-and-after diagrams — sort of. It's free software, you should play with it.