📝 9618/22 Paper 2 – Algorithms, Data Structures & Sorting | June 2025

Part two of my June 2025 Paper 2 (9618/22) walkthrough, covering algorithm design and pseudocode, stacks, and sorting algorithms. These are practical, do-it-on-paper skills, so I'll focus on the methods and the slips that lose easy marks.

📄 The original paper and mark scheme are on the Cambridge International past papers page. Questions below are paraphrased and explained in my own words, with my own examples.

Algorithm design & pseudocode

One question asked candidates to write pseudocode that totals a set of numbers, and to explain why initialisation matters.

The pattern to recognise is a running total inside a count-controlled loop. The structure is always: set the total to zero before the loop, add each input to it inside the loop, and output after the loop finishes. Here's the shape, written generically:

Total ← 0
FOR i ← 1 TO n
    INPUT Num
    Total ← Total + Num
NEXT i
OUTPUT Total

Why initialisation matters — and it's a guaranteed mark: if you don't set Total ← 0 first, the variable may start with an unknown/leftover value, so every result is wrong. The same applies to counters and flags. State it as "without initialisation the variable holds an undefined value, producing incorrect output" and you've got it.

The common pseudocode slips: forgetting the initialisation line, an off-by-one in the loop range, or confusing the loop boundary with an IF condition. Be deliberate about where each line sits relative to the loop.

✏️ Practice it: "Write pseudocode that inputs 20 numbers and outputs how many of them were greater than 100. State every variable you need to initialise and why."

Stacks

The next question asked candidates to describe how a stack works and give two of its uses.

A stack is a LIFO structure — Last In, First Out — like a stack of plates: you add to and remove from the top only. Its three operations:

• PUSH — add an item to the top.
• POP — remove (and return) the top item.
• Peek / Top — look at the top item without removing it.

The misconception that costs marks: thinking a stack allows random access. It doesn't — you can only ever touch the top. To reach an item lower down, you'd have to pop everything above it.

Real uses worth quoting: managing recursion (the call stack), the undo function in applications, browser back history, reversing data, and expression evaluation. Each works because the most recent item is always the one you want back first.

✏️ Practice it: "Three values are pushed onto an empty stack in the order 5, 8, 2. Show the result of a POP followed by a Peek, and state which value each operation returns."

Sorting algorithms

The same question asked for bubble-sort pseudocode, a disadvantage of bubble sort, and a description of insertion sort.

Bubble sort repeatedly steps through the list, comparing adjacent pairs and swapping any that are out of order; after each full pass the largest remaining value has "bubbled" to its correct end. It uses nested loops and a temporary variable for the swap:

FOR Pass ← 1 TO n - 1
    FOR i ← 1 TO n - Pass
        IF List[i] > List[i+1] THEN
            Temp ← List[i]
            List[i] ← List[i+1]
            List[i+1] ← Temp
        ENDIF
    NEXT i
NEXT Pass

Note the inner loop runs n - Pass times — the sorted tail grows each pass, so you don't re-check it.

The disadvantage examiners want: bubble sort is inefficient for large lists — its workload grows roughly with the square of the list size (O(n²)), making it slow compared with better algorithms.

Insertion sort takes each element in turn and inserts it into its correct place within the already-sorted portion of the list, shifting larger items along to make room — like sorting a hand of playing cards one card at a time.

✏️ Practice it: "Show the list [4, 1, 3] after the first complete pass of bubble sort, writing out each comparison and any swap you make."

Quick recap

• Pseudocode: a running total is initialise → accumulate in loop → output after; always initialise, or results are undefined.
• Stacks are LIFO, accessed only at the top (PUSH/POP/Peek) — no random access; used for recursion, undo and back-history.
• Bubble sort swaps adjacent pairs (slow, O(n²)); insertion sort builds a sorted section one element at a time.

Part 1 https://www.techiemike.com/cambridge-as-a-level-computer-science-june-2025-paper-2-9618-22-development-life-cycles-maintenance-testing/