D1 1.1 - Algorithms and their order

Instructions, assignments and decisions

Must adding the first million positive integers require a million additions? One algorithm adds the integers one at a time. Another evaluates $n(n+1)/2$. They produce the same answer, but the amount of work grows very differently.

An input supplies starting information; an output is a reported result. A variable stores a value that may change during the process. An instruction $x\leftarrow x+1$ means “replace the stored value of $x$ by its current value plus one”. It is an assignment, not an equation to solve.

Execute instructions in order. With $x=1$, $y=2$, the instructions $x\leftarrow x+y$, then $y\leftarrow x-y$, give $x=3$, then $y=1$. The second instruction uses the updated $x$, not its old value.

A flowchart expresses the same ideas graphically: an oval marks start or stop, a parallelogram input or output, a rectangle a process, and a diamond a decision with labelled branches. Arrows specify the order, including any return to an earlier step.

The order of assignments is the whole point of this short diagnostic.

Tracing a text algorithm

A trace table records the values actually produced as instructions are executed. Keep the entries in reading order so someone else can reconstruct the same process.

Consider this algorithm for a positive integer input $n$:

1. Set $s=0$, $j=1$.
2. If $j>n$, go to Step 5.
3. Set $s\leftarrow s+j$.
4. Set $j\leftarrow j+1$, then return to Step 2.
5. Output $s$ and stop.

The test occurs before the addition. The row with $j=n+1$ is reached, but its value is not added.

Worked example 2 changes only the input, from $3$ to $4$. One further pass through the loop is now allowed.

If a question supplies a partly completed table, follow its headings and layout. A row after every update is acceptable, but updates must appear in execution order. Avoid rounding intermediate values unless the instructions require it.

Use the same instructions with a new input.

Tracing decisions in a flowchart

At a decision diamond, take one branch and follow its arrow. A return arrow can cause the same instruction to be executed many times.

The flowchart below repeatedly halves an integer, discarding any fractional part, until it is below $2$. The notation $\lfloor u\rfloor$ means the greatest integer not exceeding $u$; for example, $\lfloor21/2\rfloor=10$.

[DIAGRAM: asset_name: A loop that counts repeated integer halvings; asset_slug: 9fm0-d1-161-halving-flowchart; caption: Test before halving, update the counter, then return to the decision; description: Start flows to input positive integer N, then c=0, then a decision N at least 2. The Yes branch goes to N=floor(N/2), then c=c+1, and loops to the decision. The No branch outputs c and stops. Standard flowchart shapes and clear Yes and No labels are used.]