Computing on Paper - 1

When I taught some graph and sorting algorithms the first couple of times the larger part of my energies went into understanding the algorithms as given in text books and rewriting them as mapcode theorems with proofs. The third time around, I asked myself afresh how best I could teach them. Dr. S. Durga Bhavani generously shared with me her teaching methods and references.

Would like to record here some of my observations now.

One should look at all algorithms from two different points of view. As algorithms we can work out on paper and as algorithms we have to get a machine to process. The levels of complexness differ. (The word 'complexity' has a definite technical meaning in relation to algorithms. So I am choosing a different noun form of 'complex' that is also allowed by the dictionary.)

The algorithms we learned as children for the arithmetic operations are a marvel of design. They use a two-dimensional paper data structure in which we can write to the left or right or above or below. Their design is chosen to balance what we keep in our minds and what is written down. In case the output we compute is not the 'book answer', what we have written down is enough to help us work through it again and find where the mistakes occurred. Can we design such formats for the algorithms we teach in computer science courses?

In the last month I have found that this is possible in principle. The surprise was that the paper complexness of the algorithms I looked at is far less than their machine complexness. Actually, they are not even as complex as the school arithmetic algorithms. It is perhaps a good idea to teach students to work out some examples on paper in the paper format with oral instructions from the instructor. It takes just a few minutes and three to four examples to understand the logic and the method of execution of the algorithm. After this initiation the instructor can pose the problem of converting the paper algorithm to a machine algorithm. The advantage is that the students have a good gut level comprehension of what they are trying to get the machine to do.

Will put up some paper algorithms for sorting in my next post.