Trace tables and hand-tracing

Tracing loops, recursion and Little Man Computer programs without slips, and a binary search that prints its own trace table.

A15.3Exam preparationA level45 min

At GCSE you traced loops through a table, a row for every change (F13.2). A level trace questions are harder in three ways: the algorithms are bigger (searches, sorts, traversals), they use recursion, where you must keep track of calls that have not finished yet, and OCR and AQA also ask you to trace assembly language. The skill is the same: be the computer, one step at a time, and never skip a step because you think you know what happens.

The rules that stop slips

1. One column per variable, plus a column for each condition if it helps, and one for output.
2. Write a value only when it changes. A new row when a loop goes round, or when the question's table shows one.
3. Work out the condition before the body. For while low <= high, check it with the current values, and write the result.
4. Keep integer division honest. 7 DIV 2 is 3, -7 DIV 2 depends on the language, 7 MOD 2 is 1.
5. Check the loop bounds. OCR's for i = 0 to 4 runs five times, including 4; Python's range(0, 4) runs four times.
6. Check the answer is sensible. A binary search that ends with low greater than high has not found the item; a sort whose last pass changed something is not finished.

Tracing a search

A binary search of [3, 8, 12, 17, 21, 26, 30, 34, 41, 45] for 13, with mid = (low + high) DIV 2:

Four comparisons for ten items: binary search is O(log n), so doubling the list adds only one more comparison (lesson A5).

Tracing recursion

For a recursive subroutine, the trace must show each call waiting for the one it made. Write the calls going down, then the returns coming back up in reverse order, exactly as the call stack does (lesson A2).

OCR's exam reference language:

function total(n)
    if n == 0 then
        return 0
    else
        return n MOD 10 + total(n DIV 10)
    endif
endfunction

Fill in the "returns" column from the bottom up: call 4 returns first, and only then can call 3 finish. Printing the calls and returns with indentation shows the same shape:

def total(n, depth=0):
    print("  " * depth + f"total({n}) called")
    if n == 0:
        result = 0
    else:
        result = n % 10 + total(n // 10, depth + 1)
    print("  " * depth + f"total({n}) returns {result}")
    return result

print("answer:", total(472))

Run this in the simulator

Tracing assembly language

OCR questions use the Little Man Computer (lesson A9.5); AQA uses its own assembly language (lesson A9.6). The columns are the accumulator or registers, each labelled memory location, and the output. Branches are where slips happen: check the condition against the accumulator at that moment.

        INP
        STA count
loop    LDA count
        OUT
        BRZ end
        SUB one
        STA count
        BRA loop
end     HLT
count   DAT
one     DAT 1

With the input 2:

The program counts down from the input to 0. A common exam follow-up asks what happens with a different input, or asks you to change the program so it stops before outputting 0.

Arguing that it works

AQA also asks you to articulate how a program works and argue that it is correct. A trace is part of that argument, but so are: choosing test data that exercises each path (lesson A14.5), stating what is always true at a point in a loop ("everything left of low is smaller than the target"), and explaining why the loop must end ("high - low gets smaller every time round").

Task: trace the search

Make a binary search print its own trace table.

Write binary_search(items, target). items is a list of whole numbers in ascending order and target is a whole number. Use low starting at 0 and high starting at the last index, and loop while low <= high. Each time round, set mid = (low + high) // 2, then immediately print low=<low> mid=<mid> high=<high> item=<items[mid]>. If items[mid] equals target, return mid; if it is less than target, set low = mid + 1; otherwise set high = mid - 1. If the loop ends, return -1.

Then, for each target in [34, 13] in order: print searching for <target>, call the function, and print found <target> at <index> or <target> not found. The robot stays still.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

readings = [3, 8, 12, 17, 21, 26, 30, 34, 41, 45]

Challenges

1. Trace the search by hand for the target 45 before you run it, then check your table against the output.
2. Change mid to (low + high + 1) // 2. Does the search still work? Trace 13 again to find out.
3. Trace the LMC program with the input 0. How many values does it output?