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.