AQA GCSE Computer Science (8525) · Fundamentals of algorithms
Mini-Lesson
Fundamentals of algorithms
This mini-lesson covers AQA 3.1 — Fundamentals of algorithms: computational thinking (decomposition, abstraction, algorithmic thinking), representing algorithms with pseudocode and flowcharts, trace tables, searching (linear & binary) and sorting (bubble, merge, insertion).
Work through each screen, answer the questions as you go (some are wordy, some are trace-table calculations) and collect ⭐ stars. Press Start when you're ready.
Computational thinking
Decomposition, abstraction & algorithmic thinking
Before you can write an algorithm you break the problem down and strip away the detail. AQA names three techniques:
Decomposition — breaking a big problem into smaller, more manageable sub-problems you can solve one at a time.
Abstraction — removing (hiding) unnecessary detail so you focus only on what matters. A tube map is an abstraction of the real rail network.
Algorithmic thinking — identifying the steps (and their order) needed to solve the problem.
Definition to memorise: an algorithm is a sequence of steps that can be followed to complete a task; a program is an algorithm that has been coded into a form a computer can execute.
Quick check
Which technique?
?A designer draws a simplified map that removes street names and shows only the stations and lines. Which computational thinking technique is this?
Representing algorithms
Pseudocode & flowcharts
The same algorithm can be shown as pseudocode (structured English-like code) or a flowchart (boxes and arrows). Flowchart shapes have set meanings:
# pseudocode: is a number positive?
INPUT num
IF num > 0 THEN
OUTPUT 'positive'ELSE
OUTPUT 'not positive'ENDIF
Exam skill: you must be able to read and write algorithms in AQA-style pseudocode, and convert between pseudocode and flowcharts.
Determining outputs · trace tables
Trace tables
A trace table lets you follow an algorithm by hand, writing down each variable's value on every pass through a loop. It's how you predict an algorithm's output.
# what does this output?
total ← 0
FOR i ← 1 TO 4
total ← total + i
NEXT i
OUTPUT total
Trace it, pass by pass
i=1 → total = 0+1 = 1
i=2 → total = 1+2 = 3
i=3 → total = 3+3 = 6
i=4 → total = 6+4 = 10
Tip: add one column per variable, one row per loop pass. The final OUTPUT is whatever the variable holds when the loop ends.
Trace it
Your turn — trace the loop
1Trace this and give the value output. total ← 1 FOR i ← 1 TO 4 total ← total × i NEXT i OUTPUT total
Hint: it multiplies 1×1×2×3×4 (this is 4 factorial).
Searching · linear search
Linear search
A linear search checks each item in a list one at a time, from the start, until it finds the target or reaches the end. The list does not need to be sorted.
Pros & cons: simple and works on any list, but slow for long lists — in the worst case it checks all n items.
Searching · binary search
Binary search
A binary search is much faster but needs a sorted list. Each step checks the middle item and throws away half the list:
If the middle item is the target → found.
If the target is smaller → search the left half.
If the target is bigger → search the right half.
Key contrast: linear search works on any list; binary search is far faster but only works on a sorted list.
Quick check
When can't you use it?
?Which condition must be true before a binary search will work correctly?
Calculate
Your turn — halving
2A binary search runs on a sorted list of 16 items. In the worst case, how many items must be checked before the search finishes? (Each check roughly halves the list: 16→8→4→2→1.)
checks
Hint: count how many times you halve 16 down to 1: 16→8→4→2→1 is 4 halvings.
Sorting · bubble sort
Bubble sort
A bubble sort repeatedly steps through the list, comparing adjacent pairs and swapping them if they are in the wrong order. After each full pass the largest remaining value has "bubbled" to the end.
Bubble sort: easy to write but slow on big lists (it compares many pairs). It works in place — no extra list needed.
Trace it
Your turn — one bubble pass
3Start with the list [5, 2, 8, 1]. Carry out one complete pass of a bubble sort (compare each adjacent pair left→right, swapping if the left is bigger). What is the last (rightmost) number after this one pass?
Hint: 5>2 swap → [2,5,8,1]; 5<8 keep; 8>1 swap → [2,5,1,8]. The largest bubbles to the end.
Sorting · merge & insertion
Merge sort & insertion sort
AQA requires two more sorts:
Merge sort — a divide and conquer sort. Repeatedly split the list in half until each part has one item, then merge the parts back together in order. It's much faster than bubble sort on large lists.
Insertion sort — builds a sorted section one item at a time, taking the next item and inserting it into its correct place among the already-sorted items.
Merge sort: split until single items, then merge in order.
Speed: on large lists, merge sort is generally much faster than bubble or insertion sort; on small lists the simpler sorts can be fine and use less memory.
Sort it
Which algorithm is it?
Tap a description, then tap the algorithm it belongs to.
🔎 Linear search
✂️ Binary search
🫧 Bubble sort
Match it
Match term to meaning
Tap a description on the left, then its matching term on the right.
Description
Term
Quick check
Best tool for the job
?You must sort a very large, unsorted list as quickly as possible. Which of these AQA sorts is generally the most efficient choice?