HookThe shortest-path algorithm designed in twenty minutes
In 1956 the Dutch computer scientist Edsger Dijkstra was out shopping in Amsterdam with his fiancée and, tired, sat down at a café terrace for a coffee. He was trying to think of a problem that would show off a new machine, the ARMAC, to a general audience — something everyone could understand. He settled on the shortest route between two Dutch cities, and there at the café, in about twenty minutes, with no pen and no paper, he worked out the algorithm that solves it. He published it three years later, in 1959, in a three-page paper. That twenty-minute idea now runs inside every sat-nav that plots a route, every internet router that forwards a packet, and every journey planner that finds you the fastest way across a city.
An algorithm is a finite, precise, unambiguous sequence of steps that solves a problem — and this section is the canon of them that every AQA candidate must be able to follow and trace by hand. How to search a list; how to sort one; how to walk a tree or a graph; how to turn ordinary bracketed arithmetic into a form a machine can evaluate with nothing but a stack; and how Dijkstra's café idea actually works, step by step. Running underneath all of them is the question Dijkstra was really answering — not merely does it work, but how fast does the work grow as the data gets bigger, the idea of time complexity that the Theory of Computation section later makes formal. Master the traces here and that formal theory becomes obvious rather than abstract.
MechanismSearching: linear, binary and binary-tree
Linear search is the honest brute-force method: start at the first element and check each one in turn until you find the target or run off the end. Its great virtue is that it makes no demands — the data can be in any order, even unsorted — but it is slow, taking up to n comparisons for a list of n items, which is O(n). For a one-off search of a small or unsorted list it is exactly the right tool; for repeated searches of big data it is a bottleneck.
Binary search is dramatically faster but carries one strict precondition: the list must already be sorted. It works by repeatedly halving the search space — compare the middle element with the target; if they match you are done; if the target is smaller, throw away the whole upper half; if larger, throw away the lower half; repeat on what remains. Each comparison eliminates half the data, so the work is O(log₂ n): a sorted list of a million items is searched in about 20 comparisons, not a million. Binary-tree search applies the same halving idea to a binary search tree: start at the root, go left when the target is smaller and right when it is larger. If the tree is balanced this is O(log n); if it has degenerated into a long chain it collapses back to O(n), which is why balance matters.
Binary search for 23 in the sorted list [4, 8, 15, 16, 23, 42] (indices 0 to 5). Set low = 0, high = 5. First pass: mid = (0 + 5) DIV 2 = 2, and list[2] = 15. Since 15 < 23 the target must be to the right, so discard everything up to mid: low = mid + 1 = 3. Second pass: mid = (3 + 5) DIV 2 = 4, and list[4] = 23 — found, in just 2 comparisons. A linear search would have checked indices 0, 1, 2, 3, 4 — five comparisons — to reach the same element. The gap is small here and enormous at scale: that is the whole case for sorting first and searching binary.
MechanismSorting: bubble and merge
Bubble sort is the algorithm everyone meets first because it is the easiest to picture: pass through the list comparing each adjacent pair and swapping any that are out of order, so on every pass the largest remaining value 'bubbles' up to its final place at the end. Repeat until a whole pass makes no swaps. It sorts in place using almost no extra memory, and a swapped flag lets it stop early on an already-sorted list, but its running time is O(n²) — double the data and you roughly quadruple the work — so it is hopeless on large lists.
Merge sort is the grown-up alternative and a textbook case of divide and conquer. It splits the list in half, recursively sorts each half, then merges the two sorted halves back into one sorted list by repeatedly taking the smaller of the two front elements. The recursion bottoms out at single-element lists, which are trivially sorted. Because the splitting gives log n levels and each level's merging touches all n items, the running time is O(n log n) — far better than bubble sort on big data. The price is memory: the merges need extra space to hold the combined lists, so merge sort is not in-place. The examinable summary is a trade-off: bubble sort is simple and in-place but slow; merge sort is fast but memory-hungry.
One full pass of bubble sort on [5, 1, 4, 2, 8]. Compare 5 and 1 → out of order, swap → [1, 5, 4, 2, 8]. Compare 5 and 4 → swap → [1, 4, 5, 2, 8]. Compare 5 and 2 → swap → [1, 4, 2, 5, 8]. Compare 5 and 8 → in order, no swap. After pass 1 the list is [1, 4, 2, 5, 8]: the largest value, 8, is settled at the end and 5 has bubbled up one place. Further passes sort the rest.
Merge sort on [38, 27, 43, 3]. Split into [38, 27] and [43, 3], then into singletons [38] [27] [43] [3]. Merge the pairs by comparing fronts: [38] and [27] → [27, 38]; [43] and [3] → [3, 43]. Final merge of [27, 38] and [3, 43]: take 3, then 27, then 38, then 43 → [3, 27, 38, 43]. Sorted, with every comparison made between the fronts of two already-sorted lists.
MechanismTraversals: walking graphs and trees
To traverse a structure is to visit every node exactly once in a defined order. On a graph there are two: depth-first (DFS) plunges as deep as possible along one path before backtracking, and is naturally implemented with a stack (or recursion); breadth-first (BFS) explores level by level, visiting all a node's neighbours before going deeper, and uses a queue. The choice has real consequences: BFS finds the fewest-edges path in an unweighted graph, while DFS suits cycle detection, topological sorting and maze solving.
On a binary tree there are three traversals, distinguished only by when you visit the current node relative to its subtrees. Pre-order visits the node first, then the left subtree, then the right (node–left–right) — used to copy a tree or print a prefix expression. In-order visits left, then the node, then right (left–node–right) — and on a binary search tree this magically produces the values in sorted order, which is the single most examined fact about tree traversal. Post-order visits left, right, then the node (left–right–node) — used to delete a tree safely or evaluate an expression tree, because you handle the children before the parent. Learn the three by the position of the root in the name: pre = root first, in = root in the middle, post = root last.
Take a binary search tree built by inserting 8, 3, 10, 1, 6, 14: 8 is the root, 3 is its left child (with children 1 and 6), and 10 is its right child (with right child 14). In-order (left–node–right) yields 1, 3, 6, 8, 10, 14 — perfectly sorted, straight out of the tree. Pre-order (node–left–right) yields 8, 3, 1, 6, 10, 14. Post-order (left–right–node) yields 1, 6, 3, 14, 10, 8 — every child before its parent, ending at the root.
On the graph with edges A–B, A–C, B–D, C–D, starting at A and taking neighbours alphabetically: BFS visits A, then its neighbours B and C, then D → A, B, C, D. DFS dives — A, B, then B's neighbour D, then back up to reach C → A, B, D, C. Same graph, different order, because one uses a queue and the other a stack.
MechanismReverse Polish Notation
Ordinary arithmetic is written in infix form — the operator sits between its operands, as in 3 + 4 — and infix needs brackets and precedence rules to be unambiguous. Reverse Polish Notation (RPN, or postfix) puts the operator after its operands: 3 4 +. The payoff is that postfix needs no brackets and no precedence rules at all; the order of the symbols alone fixes the meaning, and it can be evaluated in a single left-to-right pass using nothing but a stack. That is exactly why compilers and calculators convert expressions to RPN before evaluating them — it removes the need to look ahead for closing brackets.
Evaluating postfix with a stack is mechanical: scan left to right; every time you meet a number, push it; every time you meet an operator, pop the top two numbers, apply the operator, and push the result back. When the scan ends, the single value left on the stack is the answer. Converting infix to postfix follows precedence — the higher-priority operation is emitted first — and an operator stack (the 'shunting-yard' idea) automates it, but at A-level you are usually asked to convert short expressions by inspection and then evaluate them. The key insight to state in an answer is why postfix is used: unambiguous, bracket-free, single-pass, stack-evaluable.
Convert 3 + 4 × 2 to RPN. Multiplication binds tighter than addition, so it is emitted first: 4 2 × happens before the +, giving 3 4 2 × +. Now evaluate with a stack: push 3, push 4, push 2; meet × → pop 2 and 4, compute 4 × 2 = 8, push 8; meet + → pop 8 and 3, compute 3 + 8 = 11, push 11. Result: 11.
Now watch the brackets disappear. Convert (3 + 4) × 2 to RPN → 3 4 + 2 ×. Evaluate: push 3, push 4; meet + → pop 4 and 3, compute 7, push 7; push 2; meet × → pop 2 and 7, compute 14, push 14. Result: 14. The two expressions used the same numbers and operators; the RPN forms are different, and no bracket was ever needed to tell them apart — the position of the operators did all the work.
CaseDijkstra's shortest path, step by step
Dijkstra's algorithm finds the shortest distance from one start vertex to every other vertex in a weighted graph, provided all the edge weights are non-negative. It keeps a table of the best-known (tentative) distance to each vertex — 0 for the start, infinity for everything else — and a set of vertices not yet finalised. The loop is greedy: pick the unvisited vertex with the smallest tentative distance, mark it settled (its distance is now final and will never change), and relax each of its neighbours — if going through the settled vertex offers a shorter route than the neighbour's current best, update it. Repeat until every vertex is settled.
The reason it works — and the reason non-negative weights are essential — is the greedy guarantee: because no edge can reduce a distance, the nearest unsettled vertex can never later be reached more cheaply through a vertex that is further away, so once you settle it you are done with it. Introduce a negative edge and that guarantee collapses, which is why a different algorithm is needed for graphs with negative weights. In an exam you demonstrate Dijkstra by maintaining the distance table and showing it change row by row as each vertex is settled — the marks are awarded for the intermediate states, not just the final shortest distance.
Run Dijkstra from A on a graph with edges A–B = 1, A–C = 4, B–C = 2, B–D = 5, C–D = 1. Start with distances A = 0, B = ∞, C = ∞, D = ∞.
Settle A (distance 0): relax its neighbours — B becomes min(∞, 0 + 1) = 1, C becomes min(∞, 0 + 4) = 4. Table: A 0, B 1, C 4, D ∞. Settle the nearest unsettled vertex, B (1): relax — C becomes min(4, 1 + 2) = 3, D becomes min(∞, 1 + 5) = 6. Table: A 0, B 1, C 3, D 6. Settle C (3): relax — D becomes min(6, 3 + 1) = 4. Table: A 0, B 1, C 3, D 4. Settle D (4): done. The shortest distance from A to D is 4, along the path A → B → C → D (1 + 2 + 1). Note the direct A → C = 4 was beaten by A → B → C = 3 — the greedy step found it because it always settled the nearest vertex first.
VocabularyKey terms the mark scheme pays for
TrapsMisconceptions that cost marks
ExamWhat examiners want
Algorithms are examined on both papers and the traceable ones dominate the marks. On Paper 1 (7517/1, on-screen) you may have to implement or adapt a search, sort or traversal in code against the skeleton program, so know each well enough to write it, not just describe it. On Paper 2 (7517/2, written) the recurring task is a hand-trace, and the single rule that gains the most marks is: build a trace table with a column per variable and a row per pass, and fill in every intermediate state. For binary search that means a row each for low, high and mid; for bubble sort, the list after each pass; for Dijkstra, the whole distance table after each vertex is settled. Examiners award the working, not only the final answer — a correct end result with no trace is a low-band answer.
Match the objective to the command word. AO1 ('describe binary search', 'state the order of an in-order traversal') wants the precise method and, where relevant, the complexity — say O(log n) or O(n²) and be ready to justify it. AO2 ('trace', 'show each step', 'convert to RPN') wants the mechanical execution laid out fully. AO3 ('compare', 'evaluate', 'justify') wants the trade-off argued against the specific scenario: linear versus binary hinges on whether the data is sorted; bubble versus merge on list size and available memory; BFS versus DFS on whether you need the shortest unweighted path or a deep search. Always state a precondition when one exists — 'binary search requires a sorted list', 'Dijkstra requires non-negative weights' — because naming it is frequently a mark in its own right.