Mission 1 · Spec 2.1.1
Computational thinking
Abstraction, decomposition and algorithmic thinking: the three ways computer scientists tackle problems.
- Starter 5 min
- Learn 10 min
- Lab 15 min
- Quiz 10 min
- Exam 10 min
The Tube map
The London Underground map isn't to scale and its lines are drawn straight. Why is it still so useful?
Reveal
Passengers only need the order of stations and where to change. Everything else has been removed. That is abstraction: removing unnecessary detail to focus on what matters.
Key ideas
Abstraction
Removing unnecessary detail from a problem so you can focus on the important parts.
Decomposition
Breaking a complex problem into smaller, more manageable sub-problems that can be solved individually.
Algorithmic thinking
Identifying the steps needed to solve a problem, in the right order, so it can be followed (or programmed).
Abstraction filter
You're designing a sat-nav route planner. Which details matter?Which technique?
Exam-style questions
1. Define decomposition.
[1 mark]Mark scheme
- Breaking a problem down into smaller sub-problems (1)
2. A programmer is creating a game of snooker. Give one example of how abstraction could be used and explain why.
[2 marks]Mark scheme
- A detail removed, e.g. the audience, the players' appearance, the room (1)
- because it doesn't affect how the game is played / the movement of the balls (1)
TUTOR NOTES
- Misconception: abstraction = simplifying anything. It specifically removes unnecessary detail.
- Extension: draw a structure diagram for a school library system.
Mission 2 · Spec 2.1.2
Designing, creating and refining algorithms
Inputs, processes and outputs; structure diagrams; flowcharts; pseudocode in OCR Exam Reference Language; and trace tables.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 10 min
What does it do?
a = input("First number")b = input("Second number")if a > b then print(a)else print(b)endif
Try a = 4, b = 9, then a = 7, b = 2. What is the purpose of this algorithm?
Reveal
It outputs the larger of two numbers. Testing with different inputs is how you work out an algorithm's purpose.
Key ideas
Inputs, processes, outputs
Identify what data goes in, what is done to it, and what comes out, before designing the solution.
Structure diagrams
Show a problem broken down (decomposed) into sub-sections, as a hierarchy from the top.
Flowcharts
Terminal (start/stop), process, decision, input/output and sub-program symbols joined by arrows.
Trace tables
A column per variable (and output). Follow the algorithm line by line, recording each change.
Errors: a syntax error breaks the rules of the language; a logic error means the algorithm runs but gives the wrong result. Trace tables are the best way to find logic errors.
Flowchart symbols
Trace table machine
Watch, then switch to Test me.Exam-style questions
1. Complete a trace table for this algorithm.
[3 marks]total = 0for i = 2 to 6 step 2 total = total + inext iprint(total)
Mark scheme
- i: 2, 4, 6 (1)
- total: 0, 2, 6, 12 (1)
- Output: 12 (1)
2. Identify the inputs, processes and outputs for a program that calculates the area of a rectangle.
[3 marks]Mark scheme
- Inputs: width and height / length (1)
- Process: multiply width by height (1)
- Output: the area (1)
TUTOR NOTES
- ERL reminders:
=assigns,==compares;for i = 1 to 5 … next i. - Misconception: recording every variable on every row of a trace table.
Mission 3 · Spec 2.1.3
Searching algorithms
Linear search and binary search: how they work, their pre-requisites, and how they compare.
- 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 say "higher" or "lower". What's the best first guess, and what's the most guesses you'd ever need?
Reveal
Guess 50. Each answer halves what's left, so at most 7 guesses. That's binary search. Guessing 1, 2, 3… (linear search) could take 100.
Two searching algorithms
Linear search
Check each item in turn from the start until the item is found or the end is reached.
✓ Data doesn't need to be sorted
✗ Slow on large lists
Binary search
Pre-requisite: the data must be sorted. Compare the middle item with the target; discard the half that can't contain it; repeat.
✓ Much faster on large lists
✗ Only works on sorted data
Search race
How much faster?
Exam-style questions
1. Show the stages of a binary search to find 47 in 4, 9, 15, 22, 30, 47, 51, 63.
Mark scheme
- Middle item (index 3) is 22; 47 > 22 (1)
- so discard the left half, leaving 30, 47, 51, 63 (1)
- Middle item (index 5) is 47 (1)
- 47 = 47, so the item is found (1)
2. State the pre-requisite for a binary search.
[1 mark]Mark scheme
- The data must be sorted / in order (1)
TUTOR NOTES
- Middle item: OCR accepts either middle for an even-length list if used consistently; the lab rounds down.
- Check: list indexes 0–7; (0 + 7) DIV 2 = 3 → 22; then (4 + 7) DIV 2 = 5 → 47.
Mission 4 · Spec 2.1.3
Sorting algorithms
Bubble sort, merge sort and insertion sort, traced step by step.
- Starter 5 min
- Learn 10 min
- Lab 25 min
- Quiz 10 min
- Exam 10 min
Sorting a hand of cards
How do you sort a hand of playing cards? Describe your method in steps.
Reveal
Most people pick up each card and slide it into the right place among the cards they've already sorted. That's insertion sort.
Three sorting algorithms
Bubble sort
Compare adjacent items and swap if in the wrong order. Repeat passes until a pass has no swaps. Simple but slow on large lists.
Merge sort
Split the list in half repeatedly until each list has one item, then merge pairs of lists in order until one sorted list remains. Fast on large lists but uses more memory.
Insertion sort
Take each item in turn and insert it into the correct place in the sorted part of the list. Simple, efficient on small or nearly sorted lists.
Sort visualiser
Try all three on the same list and compare comparisons.Exam-style questions
1. Show the stages of an insertion sort on 5, 2, 8, 1.
Mark scheme
- 2, 5, 8, 1 (1)
- 2, 5, 8, 1 (8 already in place) (1)
- 1, 2, 5, 8 (1)
2. Describe how a merge sort works.
[3 marks]Mark scheme
- The list is repeatedly split in half (1)
- until each sub-list contains one item (1)
- Sub-lists are merged in order, comparing the first items, until one sorted list remains (1)
TUTOR NOTES
- Misconception: confusing insertion and bubble sort. Insertion builds a sorted section on the left.
- Exam habit: show every intermediate list.