4.3 Tricks of the Trade: Tracing a Program or Algorithm

A critical step in the design of an algorithm or program is to verify that it is correct before you spend extensive time entering or debugging it. Often a few extra minutes spent in verifying the correctness of an algorithm will save hours of testing time later.

One important technique, a hand trace or desk check (mentioned in Chapter 1), consists of a careful, step-by-step simulation on paper of how the computer would execute the algorithm or program. The results of this simulation should show the effect of each step's execution using data that are relatively easy to process by hand.

As an example, the completely refined algorithm for the smallest letter problem appears next.

Refined Algorithm

1. Read three letters into Ch1, Ch2, and Ch3.

2. Save the alphabetically first of Ch1, Ch2, and Ch3 in AlphaFirst.

2.1. Save the alphabetically first of Ch1 and Ch2 in AlphaFirst.

2.1.1. IF Ch1 precedes Ch2 THEN

2.1.2. AlphaFirst gets Ch1

ELSE

2.1.3 AlphaFirst gets Ch2

END IF;

2.2 Save the alphabetically first of Ch3 and AlphaFirst in AlphaFirst.

2.2.1. IF Ch3 precedes AlphaFirst then

2.2.2. AlphaFirst gets Ch3

END IF;

3. Display the alphabetically first letter.

Table 4.2 shows a trace of the algorithm for the data string THE. Each step is listed at the left in order of its execution. The values of variables referenced by a step are shown after the step. If a step changes the value of a variable, the table shows the new value. The effect of each step is described at the far right. For example, the table shows that the step

Read three letters into Ch1, Ch2, Ch3 stores the letters T, H, and E in the variables Ch1, Ch2, and Ch3.

Table 4.2
Trace of First Letter Algorithm

Algorithm Step		Ch1	Ch2	Ch3	AlphaFirst	Effect


			?	?	?	?

1.  Read three letters	T	H	E			Reads the data

2.1.1  If Ch1 precedes Ch2					Is T < H ?
								value is false

2.1.3  AlphaFirst gets Ch2 			H		H is first so far

2.2.1  If Ch3 precedes AlphaFirst				Is E < H ?
								value is true

2.2.2  AlphaFirst gets Ch3			E		E is first

3.  Display AlphaFirst						Displays 
								E is the
								first letter...

The trace in Table 4.2 clearly shows that the alphabetically first letter, E, of the input string is stored in AlphaFirst and displayed. In order to verify that the program is correct, it would be necessary to select other data that cause the two conditions to evaluate to different combinations of their values. Because there are two conditions and each has two possible values (true or false), there are 2 x 2, or 4 different combinations that should be tried. (What are they?) An exhaustive (complete) desk check of the program would show that it works for all of these combinations.

Besides for the four cases discussed above, you should verify that the program works correctly for unusual data. For example, what would happen if all three letters or a pair of letters were the same? Would the program still provide the correct result? To complete the desk check, it would be necessary to show that the program does indeed handle these special situations properly.

In tracing each case, you must be very careful to execute the program exactly as it would be executed by the computer. A desk check in which you assume that a particular step will be executed a certain way, without explicitly testing each condition and tracing each program step, is of little value.

Example 4.4

In later chapters, you will see that it is useful to be able to order a pair of data values so that the smaller value is stored in one variable (say, X) and the larger value is stored in another (say, Y). The following IF statement rearranges any two values stored in these two variables as just described. If the two numbers are already in the proper order, the statement sequence is not executed.

    IF X > Y THEN  -- switch X and Y 
        Temp := X; -- Store old X in Temp
        X := Y;    -- Store old Y in X
        Y := Temp; -- Store old X in Y 
    END IF;

The variables X, Y, and Temp must, of course, all be the same type. Although the values of X and Y are being switched, an additional variable, Temp, is needed for storage of a copy of one of these values. The trace in Table 4.3 illustrates the need for Temp, assuming X and Y have original values of 12.5 and 5.0, respectively. If Temp were not used, one of the values would be lost; be sure you understand why this is so.

Table 4.3
Trace of IF Statement to Order X and Y

Statement Part		X	Y	Temp	Effect

			12.5	5.0	?
IF X > Y THEN					12.5 > 5.0 is true
  Temp := X;				12.5	Store old X in Temp
  X := Y;		5.0			Store old Y in X
  Y := Temp;			12.5		Store old X in Y

Exercises for Section 4.3

Self-Check

Provide sample data and traces for the remaining three cases of the alphabetically first letter problem. Also, test the special cases where two letters are the same and all three letters are the same. What is the value of the conditions in the latter case?
Trace Program 4.1 when Hours is 30.0 and Rate is 5.00. Perform the trace when Hours is 20.0 and Rate is 4.00.