Topic 7: Algorithm Design and Problem-Solving — Part 4

Logic Patterns & Trace Tables

Common logic patterns

Many algorithms reuse the same logical patterns. Recognising these patterns helps you write and understand pseudocode quickly.

Totalling

Keep a running sum by initialising a total to zero and adding each value inside a loop:

Total ← 0
FOR i ← 1 TO 5
    INPUT Number
    Total ← Total + Number
NEXT i
OUTPUT Total

Counting

Count how many items meet a condition by initialising a counter to zero and incrementing when the condition is true:

Count ← 0
FOR i ← 1 TO 10
    INPUT Value
    IF Value > 10 THEN
        Count ← Count + 1
    ENDIF
NEXT i
OUTPUT Count

Finding the maximum

Store the largest value seen so far by initialising to the first value, then comparing each new value:

INPUT FirstValue
Max ← FirstValue
FOR i ← 2 TO 10
    INPUT Value
    IF Value > Max THEN
        Max ← Value
    ENDIF
NEXT i
OUTPUT Max

Finding the minimum

Mirror the maximum pattern — initialise from the first value read, then replace Min whenever a smaller value is found:

INPUT FirstValue
Min ← FirstValue
FOR i ← 2 TO 10
    INPUT Value
    IF Value < Min THEN
        Min ← Value
    ENDIF
NEXT i
OUTPUT Min

Finding the average

Combine totalling and counting, then divide after the loop:

Total ← 0
Count ← 0
FOR i ← 1 TO 5
    INPUT Number
    Total ← Total + Number
    Count ← Count + 1
NEXT i
Average ← Total / Count
OUTPUT Average

Bubble sort

Sorts a 1D array into ascending order by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. Multiple passes are made until no swaps occur in a complete pass.

DECLARE Scores : ARRAY[1:5] OF INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Pass, i : INTEGER
DECLARE Temp : INTEGER

Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR i ← 1 TO 4
        IF Scores[i] > Scores[i + 1] THEN
            Temp ← Scores[i]
            Scores[i] ← Scores[i + 1]
            Scores[i + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT i
    Pass ← Pass + 1
UNTIL Swapped = FALSE

Bubble sort diagram showing adjacent elements being compared and swapped in one pass through an array — Diagram 2: One pass of bubble sort — adjacent pairs are compared; larger values bubble toward the end of the array.

Linear search

Search through a list one item at a time until the target is found or the end is reached. Use a Found flag to track success:

Found ← FALSE
Position ← 1
WHILE Position <= Length AND Found = FALSE
    IF List[Position] = Target THEN
        Found ← TRUE
    ELSE
        Position ← Position + 1
    ENDIF
ENDWHILE
IF Found = TRUE THEN
    OUTPUT "Found at position ", Position
ELSE
    OUTPUT "Not found"
ENDIF

Diagram 1: Linear search checks each element in an array sequentially until the target value is found or the end of the list is reached.

Exam Traps

Bubble sort compares adjacent elements — it does not split the list in half like binary search.

Trace tables and dry runs

A trace table (or dry run) tracks how variables change as an algorithm executes step by step. It is essential for finding logic errors and predicting program output.

Consider this counting algorithm that counts how many of three input numbers are greater than 10. The inputs are 15, 4, and 12:

Count ← 0
FOR i ← 1 TO 3
    INPUT Number
    IF Number > 10 THEN
        Count ← Count + 1
    ENDIF
NEXT i
OUTPUT Count

Step	i	Number	Number > 10?	Count
Initialise	—	—	—	0
Loop 1 — input 15	1	15	TRUE	1
Loop 2 — input 4	2	4	FALSE	1
Loop 3 — input 12	3	12	TRUE	2
Output	—	—	—	2

The final output is 2 because 15 and 12 are greater than 10, but 4 is not.

0/15

Ad Banner Placeholder