Algorithms Illustrated

February 26th, 2010 by Sergio de Biasi

Mathematicians are (in)famous for the habit of describing the most complicated theoretical constructs without giving a single example (or very few or obscure ones). Computer scientists are a bit less inclined to this sin, but still commit it, specially as we venture deeper into the realm of theory. So it often happens as I’m reading a paper on a new data structure, or algorithm, or idea, that I’m deciphering paragraph after paragraph of seemingly arbitrary definitions and although I follow the algebra and the logic I am still wondering what is actually going on. Then after sometimes almost going insane trying to come up with a concrete meaningful example of an actual object with the desired properties, I think : “Oh, so THAT is what it was all about.”

To make this more concrete, consider the following text : “Consider a function on the natural numbers that we will call S(n), which for all elements in its domain is defined as the smallest element in the domain which is still greater than the argument. Now, consider the function SS(m,n) defined recursively as SS(m,0)=m and SS(m,n)=SS(S(m),SI(n)), where SI(n) is the inverse of S. Finally, consider the function SSS(m,n), defined recursively as SSS(m,0)=0, SSS(0,n)=0, and SSS(m,n)=SS(SSS(m,SI(n)),m).”

Now, if you are a mathematician or computer scientist, maybe you were able to figure right away what I’m talking about. That is almost certainly however because you already know what I’m talking about, you are familiar with these ideas and this structure. SSS is simply multiplication. Now, of course it is often necessary and even desirable to express certain ideas within a certain formal conceptual framework, for a series of technical reasons. But it is my opinion that this should not come without an accompanying explanation of the motivation and meaning for these ideas, a discussion of the reasons for the structures under consideration being defined in this particular way to start with, and last but not least, illustrative examples of what it is that is being described. Not doing it comes at the cost of leaning towards the unintelligible.

Unfortunately, this is not the tradition in academic journals, and in fact “explaining too much” is for some reason implicitly (or sometimes even explicitly) frowned upon. A paper with actual detailed examples has a high probability of being considered too “text-bookish”. So too many times coming up with crucial insights is “left to the reader”, when a single detailed example would have sufficed to clarify the whole concept. Of course when actually reading such papers, it’s very difficult to understand them without in the process coming up with such examples ourselves, which can lead to varying degrees of despair depending on how the paper was written. As elegant as it might be to concoct the shorter and most concise definition that captures the structure you are describing, this is by far not an efficient and useful way to communicate ideas to most human readers, specially not those who are not already familiar with what you are talking about.

After we do decode such papers, however, all the intution and intermediate intellectual scaffolding that we built to get there stays only within ourselves, and other readers have to go through the same (in my view often unnecessarily) laborious process. So I thought to myself – maybe I should share and write about some of the ideas and insights which I had while trying to understand. And of course in the process I may sometimes wander to different directions. Anyway, here it is. Algorithms Illustrated.

Leave a Reply