Algorithms Exam Practice

This lesson brings together everything you have learned about algorithms and data structures, with exam-style questions, worked examples, and key tips for maximising your marks in the GCSE Computer Science exam.

---

Exam Structure for Algorithms

In both AQA and OCR GCSE Computer Science exams, the algorithms topic typically appears in:

• Multiple-choice questions — testing definitions and comparisons
• Short-answer questions — explaining how an algorithm works
• Trace table questions — following an algorithm step by step
• Algorithm writing questions — writing pseudocode or flowcharts
• Comparison questions — comparing the efficiency of algorithms

Choosing an Approach Under Exam Pressure

Use this decision flowchart to pick the right algorithm in an exam question:

graph TD
    A["Read question"] --> B{"Searching or sorting?"}
    B -->|Searching| C{"Is data sorted?"}
    B -->|Sorting| D{"Small or nearly sorted?"}
    C -->|Yes| E["Binary search O(log n)"]
    C -->|No| F["Linear search O(n)"]
    D -->|Yes| G["Insertion / Bubble sort"]
    D -->|No| H["Merge sort O(n log n)"]

---

Worked Example 1: Trace Table Question

Question: Complete the trace table for the following algorithm.

a = 1
b = 1
OUTPUT a
OUTPUT b
FOR i = 1 TO 5
    c = a + b
    OUTPUT c
    a = b
    b = c
NEXT i

Answer:

Step	i	a	b	c	Output
Initial	—	1	1	—
	—				1
	—				1
1	1	1	2	2	2
2	2	2	3	3	3
3	3	3	5	5	5
4	4	5	8	8	8
5	5	8	13	13	13

This algorithm generates the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13.

---

Worked Example 2: Comparing Search Algorithms

Question: A database contains 10,000 sorted records. A programmer needs to search for a specific record. Compare linear search and binary search for this task. [6 marks]

Model Answer:

Linear search checks each record one by one from the start:

• It does not require the data to be sorted
• In the worst case, it would check all 10,000 records — O(n)
• In the best case, the record is the first one checked — O(1)

Binary search repeatedly halves the search space:

• It requires the data to be sorted (which it is in this case)
• In the worst case, it would need at most about 14 comparisons (log₂ 10,000 ≈ 13.3) — O(log n)
• This is significantly fewer comparisons than linear search

Conclusion: Binary search is far more efficient for this task because the data is already sorted. It would find or confirm the absence of the record in at most 14 steps, compared to up to 10,000 for linear search.

---

Worked Example 3: Writing an Algorithm

Question: Write an algorithm in pseudocode that takes a list of numbers as input and outputs the largest number. [4 marks]

Model Answer:

numbers = [INPUT list of numbers]
max = numbers[0]
FOR i = 1 TO LENGTH(numbers) - 1
    IF numbers[i] > max THEN
        max = numbers[i]
    ENDIF
NEXT i
OUTPUT max

Key marking points:

• Initialise max to the first element (not 0 — what if all numbers are negative?)
• Loop through all remaining elements
• Compare each element to the current max
• Output the result after the loop

---

Worked Example 4: Sorting Algorithm Question

Question: Describe how a bubble sort would sort the list [4, 2, 7, 1, 3]. Show the state of the list after each complete pass. [4 marks]

Model Answer:

Bubble sort compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element moves to its correct position.

Pass	Result after pass
Original	[4, 2, 7, 1, 3]
Pass 1	[2, 4, 1, 3, 7]
Pass 2	[2, 1, 3, 4, 7]
Pass 3	[1, 2, 3, 4, 7]
Pass 4	[1, 2, 3, 4, 7] — no swaps, algorithm terminates

---

Key Definitions to Remember

Term	Definition
Algorithm	A step-by-step set of instructions to solve a problem
Linear search	Checks each element in order; O(n) worst case
Binary search	Halves the search space each step; requires sorted data; O(log n)
Bubble sort	Compares and swaps adjacent elements; O(n²)
Merge sort	Divide and conquer; O(n log n); uses extra memory
Insertion sort	Inserts each element into correct position; O(n²) worst, O(n) best
Big O notation	Describes worst-case time complexity
Stack	LIFO data structure — push and pop
Queue	FIFO data structure — enqueue and dequeue
Trace table	Tracks variable values step by step

---

Common Exam Mistakes to Avoid

1. Confusing linear and binary search — linear does not need sorted data; binary does.
2. Forgetting to state time complexity when comparing algorithms — always include Big O.
3. Not showing all passes in a sorting trace — show each pass, not just the final result.
4. Incomplete trace tables — fill in every row, even if you think you have made an error.
5. Confusing stacks and queues — stack = LIFO (push/pop), queue = FIFO (enqueue/dequeue).
6. Writing ambiguous pseudocode — use clear, standard keywords (IF, THEN, ELSE, FOR, WHILE, etc.).
7. Not explaining the trade-off between time and space complexity when comparing algorithms.

---

Exam Command Words

Command Word	What it means	What to do
State	Give a fact	One word or short phrase
Describe	Give an account of	Explain the process step by step
Explain	Give reasons	Say how AND why
Compare	Identify similarities and differences	Discuss both algorithms side by side
Evaluate	Weigh up and make a judgement	Give pros/cons and a conclusion

---

Revision Checklist

• I can define what an algorithm is
• I can trace through linear search and binary search
• I can trace through bubble sort, merge sort, and insertion sort
• I can state the time complexity of each algorithm
• I can compare algorithms and explain trade-offs
• I can complete a trace table for given pseudocode
• I can describe stacks (LIFO) and queues (FIFO)
• I can explain decomposition and abstraction
• I can write simple algorithms in pseudocode