7.03a–7.03d - Defining, tracing and timing algorithms

What makes an algorithm

A machine takes $0.08$ seconds to process $400$ records. How long should it need for $1200$ records: three times as long, nine times as long, or something else? You cannot answer from the record count alone. You need to know what the instructions do.

Start with a smaller problem: find the largest number in the list $8, 3, 11, 5$. Keep $8$ as the current largest; compare it with $3$, then $11$, then $5$, updating when a larger value appears. The successive current largest values are $8, 8, 11, 11$. The final output is $11$.

The input above is the list; the output is its largest value. “Find a large-looking number” is not a complete instruction: two people could make different choices. “Compare the next entry with the current largest and replace the current largest if it is smaller” specifies the choice.

A counter records how many times something has happened. For a list of length $n$, a counter can start at $2$, identify the next position to inspect and increase by $1$ each time. A stopping condition tells the procedure when to finish: stop when that counter exceeds $n$. These meanings are not in the formula booklet: learn them.

A finite-looking description need not describe a terminating process. “Start at $1$, add $2$ repeatedly, stop at $10$” never stops: it visits only odd integers. Changing the stopping condition to “stop when the value is at least $10$” makes it finish at $11$. The permitted input and the exact stopping test both matter.

Check the stopping condition rather than judging the instructions by their length.

Tracing assignments and repeated steps

A trace follows the instructions in order, recording values as they change instead of trying to guess the final answer.

The assignment $x\leftarrow x+1$ means “replace the stored value of $x$ by its old value plus $1$”. It is an instruction, not an equation claiming that a number equals itself plus $1$. Later lines use the updated value.

These function meanings are not in the formula booklet: learn them. The following algorithm adds the decimal digits of an integer input $N$. It handles a negative input by first taking its magnitude.

For instance, $284=10(28)+4$: $q$ keeps the earlier digits and $d$ extracts the final digit. Replacing $x$ by $q$ removes that digit, so positive $x$ decreases until it becomes $0$. The flow diagram presents exactly the same instructions; a decision diamond has separate yes and no exits.

[DIAGRAM: asset_name: A digit sum algorithm; asset_slug: h245_7_03_digit_flow; caption: The loop extracts one final digit, adds it to the total and removes it before testing again; description: A flow diagram begins with integer input N and initialisation x equals ABS(N), s equals zero. A diamond asks whether x equals zero. The yes branch outputs s and stops. The no branch sets q to INT(x divided by ten), d to x minus ten q, s to s plus d, and x to q, then returns to the decision diamond. Arrows show the order of assignments.]

Worked example 2 changes only the input to a negative integer containing a zero. The absolute value handles the sign; the zero digit still requires a loop.

The same variable can have several values during a trace, but each row must correspond to the same point in the loop.

For the next input, retain the row containing its zero digit.

Adapting instructions for a new output

To alter an algorithm, identify which instructions extract information, which combine it and which guarantee that the process stops.

In the digit algorithm, $q$ and $d$ extract a digit, $s\leftarrow s+d$ combines it with the total, and $x\leftarrow q$ makes progress towards stopping. Changing the output task need not change all three jobs.

Worked example 4 changes only the quantity accumulated: count digits rather than adding their squares. A counter increases once per extracted digit, regardless of its value.