Pseudo-Code, Hand-Tracing and Program Correctness

Overview

Recall questions on writing pseudo-code, hand-tracing algorithms and finding bugs, converting pseudo-code into program code, and arguing that a program is correct and efficient.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Express as pseudo-code an algorithm that finds the largest value in a list of numbers, using all four standard constructs.

   Model answer

   largest ← numbers[0] FOR i ← 1 TO length(numbers) − 1 IF numbers[i] > largest THEN largest ← numbers[i] ENDIF ENDFOR OUTPUT largest The lines run in sequence; largest ← … is assignment; the IF is selection; the FOR is iteration. Starting largest at the first element rather than at zero is what makes the algorithm work for a list of negative numbers.

2. 2

   What does it mean to hand-trace an algorithm, and how do you set out the trace?

   Model answer

   Hand-tracing means working through the algorithm on paper exactly as a computer would, one statement at a time, recording the value of every variable after each change. It is set out as a trace table: one column per variable, plus a column for any output, and one row per pass through the loop or per statement that changes something. The point is to find out what the algorithm actually does rather than what you assumed it does.

3. 3

   Hand-trace this algorithm and give the output. total ← 0 FOR i ← 1 TO 4 total ← total + i * i ENDFOR OUTPUT total

   Model answer

   The trace table runs: before the loop: total = 0 i = 1: total = 0 + 1 = 1 i = 2: total = 1 + 4 = 5 i = 3: total = 5 + 9 = 14 i = 4: total = 14 + 16 = 30 The output is 30, the sum of the squares 1 + 4 + 9 + 16.

4. 4

   Hand-trace this algorithm with dividend = 17 and divisor = 5, and say what the two results represent. count ← 0 remainder ← dividend WHILE remainder >= divisor remainder ← remainder − divisor count ← count + 1 ENDWHILE

   Model answer

   start: remainder = 17, count = 0 pass 1: 17 >= 5, so remainder = 12, count = 1 pass 2: 12 >= 5, so remainder = 7, count = 2 pass 3: 7 >= 5, so remainder = 2, count = 3 test: 2 >= 5 is false, so the loop ends The result is count = 3 and remainder = 2. count is the whole-number quotient of 17 ÷ 5 and remainder is the remainder, so the algorithm performs integer division by repeated subtraction.

5. 5

   Hand-trace this algorithm with the list [4, 9, 2] and explain the bug it reveals. index ← 0 found ← False WHILE found = False IF list[index] = 7 THEN found ← True ENDIF index ← index + 1 ENDWHILE

   Model answer

   index = 0: list[0] = 4, not 7, so index becomes 1 index = 1: list[1] = 9, not 7, so index becomes 2 index = 2: list[2] = 2, not 7, so index becomes 3 index = 3: there is no list[3] — the loop tries to read past the end of the list The bug is that the loop condition only stops on success, so when the value is absent the loop never terminates and the index runs off the end. The fix is to stop on either condition: WHILE found = False AND index < length(list). Because it can fail to terminate, the original is not a valid algorithm.

6. 6

   Convert this pseudo-code into Python. total ← 0 FOR i ← 1 TO 5 total ← total + i ENDFOR OUTPUT total

   Model answer

   total = 0 for i in range(1, 6): total = total + i print(total) The two points to watch are that ← becomes =, and that Python's range(1, 6) stops before 6, so it must be written with an upper bound one greater than the pseudo-code's TO value in order to include 5. The output is 15.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.