Answer the questions as you go and collect ⭐ stars. Press Start when you're ready.
Computational thinking
Computational thinking
Three techniques help us solve problems like a computer:
Abstraction — removing unnecessary detail to focus on what matters (e.g. a tube map ignores real distances).
Decomposition — breaking a big problem into smaller, easier sub-problems.
Algorithmic thinking — working out the step-by-step sequence of instructions to solve it.
Nail it: abstraction = hide detail; decomposition = break it up; algorithmic thinking = define the steps.
Quick check
Which technique?
?A programmer splits 'build a game' into 'draw screen', 'move player' and 'keep score'. Which computational thinking technique is this?
Flowcharts & pseudocode
Flowcharts & pseudocode
Algorithms are written before coding using flowcharts or pseudocode.
Flowchart symbols: terminator, process, decision (diamond) and input/output (parallelogram).
OCR uses OCR Exam Reference Language for pseudocode. Structures include if…then…else, for and while loops, and input/print.
Searching
Searching: linear & binary
Two algorithms to find an item in a list:
Linear search — check each item from the start until found or the end is reached. Works on any list (sorted or not) but slow for big lists.
Binary search — needs a sorted list. Check the middle item; if not found, discard the half the target can't be in and repeat. Much faster.
Key rule: binary search only works on a sorted list; linear search works on any list but is slower on average.
Quick check
Which search?
?You need to find a name in an alphabetically sorted list of 1,000,000 names as quickly as possible. Which search is best?
Sorting
Sorting: bubble, merge & insertion
Three algorithms to put a list in order:
Bubble sort — repeatedly compare adjacent pairs and swap if out of order; the largest 'bubbles' to the end each pass. Simple but slow.
Merge sort — divide the list in half repeatedly until single items, then merge pairs back together in order. Faster for large lists (divide and conquer).
Insertion sort — build a sorted section one item at a time, inserting each new item into its correct place. Good for small or nearly-sorted lists.
Nail it: bubble = swap adjacent pairs; merge = split then merge; insertion = insert each item into place.
Calculate
Your turn — one bubble pass
1A bubble sort works on the list [5, 3, 8, 1]. After the first complete pass (comparing adjacent pairs left to right, swapping when the left is bigger), what number ends up in the last position?
the value
Hint: the largest value 'bubbles' to the end on the first pass.
Sort it
Search, sort — or thinking?
Tap an algorithm/idea, then tap what kind it is.
🔎 Searching
🔀 Sorting
🧠 Comp. thinking
Trace tables
Trace tables
A trace table tracks the value of each variable line by line as an algorithm runs, so you can check it works or find a bug.
Worked example — trace this
total = 0; for x = 1 to 3: total = total + x
x=1 → total=1 · x=2 → total=3 · x=3 → total=6
Method: write a column per variable; fill in a new row each time a value changes; the last row shows the final output.
Trace
Your turn — trace table
2Trace this: total = 0; for x = 1 to 4: total = total + x. What is the final value of total?
total
Hint: 1 + 2 + 3 + 4.
Quick check
Abstraction
?A programmer designing a map app ignores the colour of buildings and keeps only roads and junctions. Which technique is this?
Quick check
Merge sort idea
?Which sorting algorithm works by repeatedly splitting the list in half until single items remain, then merging them back in order?
Match it
Match algorithm to description
Tap an algorithm on the left, then its matching description on the right.