State and output

To determine what an algorithm does, follow its instructions in order using the data you are given. At any point, the values currently held by its variables are its state. Output is different: a value becomes output only when an OUTPUT instruction is reached.

In this lesson, SET total TO 7 assigns the value 7 to total. For an instruction such as SET total TO total + 3:

1. read the current value of total on the right;
2. calculate 7 + 3;
3. replace the old value of total with 10.

It is an assignment, not an algebra equation, and the old value is no longer held by that variable.

Worked example: a value is not automatically output

1  SET counters TO 7
2  SET counters TO counters + 3
3  OUTPUT counters - 4

The variable counters finishes with the value 10, but the algorithm outputs 6. Line 3 calculates 10 - 4 for display; it does not assign the result back to counters. In every Output column in this lesson, - means no output at this point, not zero.

Building a trace table

A useful trace table makes time visible. Its rows identify when each recorded value applies, so an intermediate value cannot be confused with the final one.

Use this method:

1. Mark every supplied input and initial value.
2. Follow one instruction at a time; never do several passes mentally at once.
3. For an assignment, calculate the right-hand side using the current state, then replace the variable on the left.
4. Record a condition result when it decides which path is followed.
5. Record output only when the OUTPUT instruction executes.

We will copy current variable values into later rows even when they have not changed. Other layouts can also be correct, but the state and timing must remain unambiguous.

Worked example: following one selected path

Supplied input: temperature = 18

1  INPUT temperature
2  SET fee TO 4
3  IF temperature < 20 THEN
4      SET fee TO fee + 2
5  ENDIF
6  OUTPUT fee

The condition is True, so line 4 executes. Immediately after line 4, fee holds 6; line 6 then outputs 6. With a supplied input of 23, the condition would be False, line 4 would be skipped, and fee would remain 4 for the output.

Tracing repetition

When instructions repeat, the state at the end of one pass becomes the starting state for the next. A reliable table therefore gives each pass its own row.

In the following pseudocode, FOR pass FROM 1 TO 3 means that the loop body executes three times, with pass equal to 1, then 2, then 3.

Worked example: output inside and after a loop

1  SET total TO 1
2  FOR pass FROM 1 TO 3
3      SET total TO total * 2
4      OUTPUT total
5  ENDFOR
6  OUTPUT total + 1

The complete output sequence is 2, 4, 8, 9. Line 4 produces output on every pass, while line 6 executes once after the loop. The final value of total is still 8: outputting total + 1 does not change total.

A branch inside a loop

A condition inside a loop must be tested again on every pass. Do not copy its previous True or False result: earlier assignments may have changed the value being tested.

In this example, FOR round FROM 1 TO 4 uses the four values 1, 2, 3, 4.

1  SET score TO 2
2  FOR round FROM 1 TO 4
3      IF score < 6 THEN
4          SET score TO score + 2
5      ELSE
6          SET score TO score - 1
7      ENDIF
8      OUTPUT score
9  ENDFOR

Worked trace

On round 3, the current score is exactly 6. The strict comparison score < 6 is therefore False, so the ELSE branch changes the score to 5. That change makes the condition True again on round 4.

Pinpointing a value

Some questions ask for a variable's value at a given point, not its final value. Use the line number and wording literally. If a line executes several times, count its executions and stop immediately after the one named.

For the following algorithm, the body repeats while counter <= 4. The condition is checked before each pass.

1  SET counter TO 1
2  SET total TO 0
3  WHILE counter <= 4
4      SET total TO total + counter
5      SET counter TO counter + 1
6  ENDWHILE
7  OUTPUT total

Worked trace focused on line 4

Immediately after the third execution of line 4, total holds 6. That is the answer at the named point, even though tracing further gives a final output of 10. After the fourth pass, line 5 changes counter to 5; the line 3 condition is then False, so the loop stops.

Before giving an answer, check four things: the supplied starting values, the branch taken on each pass, the exact moment output occurs, and whether the question asks for an intermediate value or final output.