display | more...
If you write an algorithm, and it's not giving you the output you expected from a given input, then it may be time to try an algorithm trace. This is a way of seeing what's going on internally in an algorithm by recording all the values of all the variables at every stage of the algorithm. This way, you can see what's gone wrong, and when.

Imagine we have an algorithm (in pseudocode):

1: INPUT A
2: INPUT B
3: INPUT C
4: FOR I = 1 TO C
5:   A = A + B
6: NEXT I
We can trace the algorithm by doing a dry-run. First, we create some input values - in the case of a real world algorithm trace, these values would be chosen because they are causing trouble, or are likely to cause trouble. As I have no specific problem to solve in this case and am simply explaining what a trace is, I have chosen largely random values.

The inputs I am providing are 2, 3 and 4, in that order. Dashes represent undefined values - it is impossible to assume values, even 0, for these variables, until we specifically assign them one.

Line no | A | B | C | I
------------------------
   1    | 2 | - | - | -
   2    | 2 | 3 | - | -
   3    | 2 | 3 | 4 | -
   4    | 2 | 3 | 4 | 1
   5    | 5 | 3 | 4 | 1
   6    | 5 | 3 | 4 | 2
   5    | 8 | 3 | 4 | 2
   6    | 8 | 3 | 4 | 3
   5    | 11| 3 | 4 | 3
   6    | 11| 3 | 4 | 4
   5    | 14| 3 | 4 | 4
   6    | 14| 3 | 4 | 4
There. What we have essentially done is recorded the values of all the variables at every stage during the execution of that algorithm. It is now possible to see, at any stage in the algorithm, what variables will have what values. This makes debugging a lot easier, because the programmer can look at the state of everything effected by the algorithm at any given time. This is also very handy in finding loop invariants, which are special constants in an iteration loop which can help the astute programmer increase its efficiency.

Log in or register to write something here or to contact authors.