Mission 1 · Spec 3.1.1
Thinking like a computer scientist
What an algorithm is, and the two big thinking tools: decomposition and abstraction.
- Starter 5 min
- Learn 10 min
- Lab 15 min
- Quiz 10 min
- Exam 10 min
The Tube map
The London Underground map is famous for being "wrong": the distances are not to scale and the lines are drawn straight. Why is it still one of the most useful maps ever made?
Reveal
A passenger only needs to know the order of stations and where to change lines. Everything else (real distances, roads, bends in the tunnels) has been removed. Hiding unnecessary detail to focus on what matters is called abstraction.
Key ideas
Algorithm
A sequence of steps that can be followed to complete a task. An algorithm is not a program: a program is an algorithm written in a programming language.
Decomposition
Breaking a problem down into a number of smaller sub-problems. Each one is easier to solve, and they can be solved separately (even by different people).
Abstraction
Removing unnecessary detail from a problem so you can focus on the parts that matter.
Input, process, output
Most algorithms take inputs, process them, and produce outputs. Identifying these is the first step in designing a solution.
Exam tip: when asked to "explain abstraction" in context, say what detail is removed and why it doesn't matter for the task.
Abstraction filter
You're designing a sat-nav route planner. Which details matter?Decompose it
"Create a quiz game" breaks down into sub-problems. Classify each one.Exam-style questions
1. Define the term algorithm.
[1 mark]Mark scheme
- A sequence of steps that can be followed to complete a task (1)
2. Explain what is meant by decomposition.
[2 marks]Mark scheme
- Breaking a problem into a number of sub-problems (1)
- So that each sub-problem accomplishes an identifiable task / is easier to solve (1)
3. A school is writing a program to simulate a game of snooker. Describe one way abstraction could be used.
[2 marks]Mark scheme
- Identifies a detail that can be removed, e.g. the colour of the players' clothes / the audience / the material of the table (1)
- Explains that it does not affect the outcome of the game / the physics of the balls (1)
TUTOR NOTES
- Misconception: abstraction means "making it simpler" in any way. It specifically means removing detail that isn't needed.
- Misconception: an algorithm and a program are the same thing.
- Hook: get the student to write an algorithm for making toast, then "run" it literally. Where does it break?
- Extension: what would you abstract away to model a pandemic? What can you not remove?
Mission 2 · Spec 3.1.1
Pseudocode, flowcharts and trace tables
Three ways to write down an algorithm, and the technique for working out exactly what one does.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 10 min
What does it do?
a ← USERINPUTb ← USERINPUTIF a > b THEN OUTPUT aELSE OUTPUT bENDIF
Try it with a = 4, b = 9. Then a = 7, b = 2. Describe what the algorithm does in one sentence.
Reveal
It outputs the larger of the two numbers. Notice what happens when a = b: it outputs b, which is the same value, so it still works. Testing an algorithm with different inputs is how you work out its purpose.
Representing algorithms
Pseudocode
A way of writing an algorithm that looks like code but isn't tied to one language. AQA exam papers use AQA pseudocode, e.g. x ← 5, OUTPUT x, FOR i ← 1 TO 10.
Flowcharts
A diagram of the steps using standard symbols joined by arrows. Good for showing decisions and loops visually.
Program code
The algorithm written in a real language such as Python, C# or VB.NET.
Trace tables
A table with a column for each variable (and for output). You follow the algorithm line by line and write down each new value.
Three building blocks
| Construct | Meaning | AQA pseudocode |
|---|---|---|
| Sequence | Steps run one after another | a ← 1 b ← a + 2 |
| Selection | Choose a path based on a condition | IF x > 5 THEN … ELSE … ENDIF |
| Iteration | Repeat steps | FOR i ← 1 TO 3 … ENDFOR WHILE x < 10 … ENDWHILE |
Flowchart symbols
Match each symbol to its meaning.Trace table machine
Watch the program run line by line, then switch to Test me.Exam-style questions
1. Complete a trace table for this algorithm.
[3 marks]x ← 2y ← 0WHILE x < 20 x ← x * 3 y ← y + 1ENDWHILEOUTPUT y
Mark scheme
- x column: 2, 6, 18, 54 (1)
- y column: 0, 1, 2, 3 (1)
- Output: 3 (1)
2. State the purpose of this algorithm.
[1 mark]n ← USERINPUTIF n MOD 2 = 0 THEN OUTPUT 'Even'ELSE OUTPUT 'Odd'ENDIF
Mark scheme
- To say whether a number entered by the user is odd or even (1)
3. Draw a flowchart for an algorithm that asks for a password and repeats until the user enters "letmein".
[4 marks]Mark scheme
- Start and stop terminals (1)
- Input symbol for the password (1)
- Decision checking password = "letmein" (1)
- "No" branch loops back to the input; "Yes" branch leads to stop (1)
TUTOR NOTES
- Misconception: writing a value in every column on every row. Only record a value when it changes.
- Misconception: AQA pseudocode arrays start at index 0.
- Exam habit: the "purpose" question wants what the algorithm achieves, not a line-by-line description.
- Extension: rewrite the doubling loop as a REPEAT … UNTIL loop. Does it always give the same result?
Mission 3 · Spec 3.1.2 & 3.1.3
Searching and efficiency
Linear search and binary search: how they work, when to use each, and why one is so much faster.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 10 min
Guess my number
I'm thinking of a number from 1 to 100. After each guess I'll say "higher" or "lower". What is the best first guess? What is the most guesses you should ever need?
Reveal
Guess 50 first. Each answer rules out half of what's left, so you never need more than 7 guesses (27 = 128). Guessing 1, 2, 3… could take 100. That's the difference between binary search and linear search.
Two searching algorithms
Linear search
Check each item in turn, from the start, until you find the target or reach the end.
✓ Works on an unsorted list
✓ Simple to write
✗ Slow for large lists
Binary search
Look at the middle item. If it's the target, stop. If the target is smaller, discard the right half; if bigger, discard the left half. Repeat.
✓ Much faster for large lists
✗ The list must be sorted
Efficiency: more than one algorithm can solve the same problem. For AQA you compare algorithms by time efficiency: how the number of steps grows as the input gets bigger. Doubling a list adds one comparison to a binary search, but doubles the work for a linear search.
Search race
Try the same target with both algorithms and compare the comparisons.How much faster?
Exam-style questions
1. Show the stages of a binary search for 31 in the list 3, 8, 12, 19, 25, 31, 40, 47, 52.
Mark scheme
- First comparison with the middle item, 25 (index 4) (1)
- 31 > 25, so the left half is discarded, leaving 31, 40, 47, 52 (1)
- Next middle item is 40 (index 6); 31 < 40 so compare with 31 (index 5): found (1)
2. Give one advantage and one disadvantage of a linear search compared with a binary search.
[2 marks]Mark scheme
- Advantage: works on unsorted data / simpler to implement (1)
- Disadvantage: slower / more comparisons on average for large lists (1)
3. A list of 1,000 names is sorted alphabetically. Explain why a binary search is more efficient than a linear search for this list.
[2 marks]Mark scheme
- Binary search halves the number of items to check with each comparison (1)
- So it needs at most 10 comparisons, whereas linear search could need 1,000 (1)
TUTOR NOTES
- Misconception: binary search works on any list. Always ask "is it sorted?"
- Misconception: choosing the wrong middle with an even number of items. Use (first + last) DIV 2.
- Exam habit: in "show the stages" questions, write each comparison and which half is discarded.
- Extension: if sorting takes time, when might a linear search still be the better choice overall?
Mission 4 · Spec 3.1.4
Sorting algorithms
Bubble sort and merge sort: trace them step by step and compare how efficient they are.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 10 min
Human sort
Eight cards are face up in a random order. You're only allowed to compare two cards that are next to each other and swap them. What strategy would you use to sort them?
Reveal
Work along the row swapping any neighbours in the wrong order. After one pass the biggest card has "bubbled" to the end. Repeat until a pass makes no swaps. That's bubble sort.
Two sorting algorithms
Bubble sort
- Compare the first two items. Swap them if they're in the wrong order.
- Move along one place and repeat to the end. That's one pass.
- Repeat passes until a pass makes no swaps.
✓ Simple, sorts in place
✗ Very slow on large lists
Merge sort
- Split the list in half, again and again, until every list has one item.
- Merge pairs of lists back together in order, comparing the front items.
- Keep merging until there is one sorted list.
✓ Much faster on large lists
✗ Needs extra memory; harder to write
Merge sort is a "divide and conquer" algorithm. Each merge only compares the front items of two already-sorted lists, which is why it's so efficient.
Sort visualiser
Yellow = being compared, red = swapped, green = in its final place.Merge sort in order
Put the steps of merge sort in the right order.Exam-style questions
1. Show the list 6, 2, 8, 4, 1 after each pass of a bubble sort into ascending order.
Mark scheme
- Pass 1: 2, 6, 4, 1, 8 (1)
- Pass 2: 2, 4, 1, 6, 8 (1)
- Pass 3: 2, 1, 4, 6, 8; Pass 4: 1, 2, 4, 6, 8 (1)
2. Show how merge sort would sort 7, 3, 9, 1.
Mark scheme
- Split into [7, 3] and [9, 1], then [7] [3] [9] [1] (1)
- Merge into [3, 7] and [1, 9] (1)
- Merge into [1, 3, 7, 9] (1)
3. Compare bubble sort and merge sort.
[4 marks]Mark scheme
- Merge sort is generally faster / more time-efficient, especially on large lists (1)
- Bubble sort is simpler to understand / implement (1)
- Merge sort needs more memory as it creates new lists (1)
- Bubble sort can finish early if the list is already (nearly) sorted (1)
- Bubble sort sorts the list in place (1)
- Max 4
TUTOR NOTES
- Misconception: one pass of bubble sort sorts the list. It only guarantees the largest item is at the end.
- Misconception: merge sort "splits then sorts". The sorting happens during the merging.
- Exam habit: in merge sort questions show every level of splitting and every level of merging.
- Extension: how many passes does bubble sort need, at most, for n items? (n − 1.)