Tracking algorithms with pencil and paper

In the introduction to computing course the teacher might write a lot on the blackboard and, the students, a lot on paper. The computer is left for homework, some of which, called program exercises, are graded and counted for the grade at the end of the semester. Some universities include practical classes in laboratories, some does not. The tests are not computer based, but in a old-fashioned way with paper and pencil. The teacher should not ask students to write a full program to solve a complex problem with around 200 lines of code in a test, but rather smaller problems such as reading a matrix, printing numbers, basic arithmetic, etc.

In essence, reading and fixing algorithms on paper is making your brain function as a debugger.

• What good does an algorithm on paper have if there is no compiler?

Before a movie director shoots a film, an artist should have sketched the scene. Before an architect builds a 3D model of a house, a drawing on paper should have been done. Algorithm on paper is meant for you to focus on logic and not be "spoiled" by compiler warnings and errors. The compiler identifies syntax errors, but is unable to detect wrong logic. If you were expecting your program to print "Hello World" ten times, but the program printed nine, the compiler cannot detect what is wrong.

To execute algorithm on paper is the same as tracking the algorithm line by line. One way for us to do that is to use a table, where we place variables on columns and the values of each var on rows, each new row counts as a new iteration. That is a good technique for learning how algorithms made by other people function. If the algorithm is well-documented and well-written it's easy to catch how it does something. Else, to track it on paper is the only way of understanding what and how it does something.

A manual and coarse way of debugging a program is to place a printf() call before and after each variable, then you'll be able to track every variable in the program.

What comes below assumes that you know how to declare variables, know how to use loops, know C's syntax and how to compile a code

• A typical "track this algorithm" problem. Write down what is going to be printed by program below:

#include <stdio.h>

int main() {

/* USN = University Student Number */
int USN, i = 1, digit, reverse = 0, count;

printf("Type your USN: ");

scanf("%d", &USN);
count = USN;

while (count != 1) {

count = count / 10;

i = i * 10;

}

while (i != 0) {

digit = USN % 10;
reverse = reverse + digit * i;
printf("%d * ", reverse);
if (digit % 2 == 0) printf("even\n");

else printf("odd\n");
USN = USN / 10;

i = i / 10;

}

return 0;
}

Let's track it. Suppose the input is USN = 1234567.

first while
count	i	loop's iteration
1234567	1	0 (before going in)
123456	10	1
12345	100	2
...	...	...
1	1000000	6

If you are comfortable with the assignment operation, then there is no need to waste time tracking all loop's iterations from the first to the last, just write down the value of the var 'i' after the last iteration straight away.

Second while		printf				printf
i (before)	USN	digit	reverse	USN	i (after)	even / odd
1.000.000	1234567	7	7000000	123456	100.000	odd
100.000	123456	6	7600000	12345	10.000	even
...	...	...	...	...	...	...
10	12	2	7654320	1	1	even
1	1	1	7654321	0	0	odd

It's a good idea to keep the variables sorted according to the order of the operations, this way we avoid any confusion between variables or operations tracked out of order. If the variable appears twice, before and after some operation, it's good to make a good differentiation between the two states, else we might confuse the values of var in the sequence of iterations.

If you catch up what the algorithm does pretty quickly, then you can skip the tracking table and write down the output straight away. Take notice: the first loop assigns to i the value 10ⁱ, where i is the USN's number of digits minus one. The second loop reverses the USN's digits, it picks up the last digit and moves it to the first place, filling up the rest with zeros. For each digit removed, the algorithm checks whether it's even or odd.

Errors that people might commit when sitting an exam with that simple algorithm:

• In the first loop, iterate one extra time, which invariably leads to a counting error in the second loop;
• Lack of knowledge about how integer variables store non integer numbers. 1234567 / 10 is the same as removing the last digit;
• If the person doesn't understand what is the equal sign, the assignment operation, he/she will fail to track anything. In such cases is not rare to face absurd answers such as 1234567 * 10;
• Lack of knowledge about the modulo operator, specially when we have x % y where x < y;
• At each iteration, the var 'USN' loses one digit, whereas 'i' gains one. Any error related to that depicts mistakes committed when reading the code and/or during the tracking process. The person has failed to properly track the arithmetic operations done;
• The messages "even" and "odd" weren't printed properly, for some reason the person confused the values of 'digit' and 'reverse';
• A teacher can, if he/she wants, use code with bad indentation or variables with less obvious names to make tracking harder.

Errors related to functions and arrays:

• If the person doesn't understand the concept of functions and/or arrays, he/she will fail to track properly the algorithm;
• Confuse pointers and variables, or failure to understand what pointers do;
• Errors related to the index of array and matrices;
• Lack of knowledge about how recursive functions work.