Notes · Computer ScienceUK · A-Levels

Fundamentals of algorithms

An algorithm is a precise, finite sequence of steps that solves a problem, and this chapter builds the standard toolkit every computer scientist must know by heart: traversing graphs and trees, searching for a value, sorting a list, and finding the shortest path with Dijkstra's algorithm. For each you must be able to state what it does, trace it step by step on given data, and reason about how its running time grows with the size of the input.

5 sections~18 min reading time3 competenciesLevel Standard 2 · Advanced 3

T·0333 / 14

Exam profile

AO1 · Know the standard traversal, search and sort algorithms and Dijkstra's shortest-path algorithm, and their purposes and behaviourAO2 · Trace an algorithm precisely on given data, keeping the state at every stepAO3 · Write and adapt algorithms and compare their time efficiency

Operators:describetracewrite an algorithmcompareexplainevaluate

basic level

AS-Level expects linear and binary search, bubble sort, and the idea of a tree traversal.

higher level

The full A-Level adds depth-first and breadth-first graph traversal, pre/in/post-order tree traversal and expression trees, merge sort, and Dijkstra's shortest-path algorithm, with reasoning about their complexity.

Depth

Text

Contents · 5 sections

Fundamentals of algorithms

Graph traversal: depth-first and breadth-first#

AdvancedAQA 7517 4.3.1DfE GCE Computer Science - traversal

A graph for traversal

Fig. 1Starting at A and taking neighbours alphabetically, breadth-first visits A, B, C, D, E (in rings) while depth-first visits A, B, D, C, E (plunging deep first). BFS uses a queue; DFS uses a stack.

Traversing a graph means visiting every vertex in some systematic order, and there are two fundamental strategies distinguished by the structure that holds the vertices still to be explored. Depth-first search (DFS) plunges as deep as possible along one path before backtracking; it is naturally implemented with a stack (or with recursion, which uses the call stack). Breadth-first search (BFS) explores the graph in rings, visiting all vertices one edge away, then all two edges away, and so on; it is implemented with a queue. The only real difference between the two algorithms is stack versus queue - LIFO drives you deep, FIFO drives you wide.

In both traversals each vertex is marked as visited the moment it is discovered, so it is never processed twice even when the graph contains cycles; without this mark a traversal of a cyclic graph would loop forever. Starting from a source vertex, the algorithm repeatedly takes a vertex from the frontier structure, visits it, and adds its unvisited neighbours to the frontier. DFS adds them to the stack (so the most recent is explored next); BFS adds them to the queue (so the earliest discovered is explored next).

The choice of traversal matters because it changes what you find. BFS finds the shortest path in an unweighted graph - the fewest edges - because it reaches every vertex by the shortest number of hops first; it is used in web crawling, peer-to-peer network discovery and shortest-move puzzles. DFS is the tool for exploring exhaustively, detecting cycles, finding connected components, topological sorting and maze/backtracking problems. Both run in time proportional to the number of vertices plus edges,

O(V+E)

, because each is examined a constant number of times.

Tracing a traversal is a common exam task, and precision is everything: keep an explicit record of the visited order and the current contents of the stack or queue after each step, and resolve ties by a stated rule (usually visiting neighbours in alphabetical or numerical order). The most frequent trace error is forgetting to skip an already-visited vertex, which corrupts the rest of the order.

Worked example

Breadth-first traversal with the queue

Trace a breadth-first traversal of the graph (edges A-B, A-C, B-D, C-D, D-E) from A, visiting neighbours alphabetically. Show the queue after each vertex is visited.

Visit A
Mark A visited. Enqueue its neighbours B, C. Queue: [B, C].
Visit B
Dequeue B (front). Its unvisited neighbour is D; enqueue it. Queue: [C, D].
Visit C
Dequeue C. Its neighbour D is already queued/visited, so nothing new. Queue: [D].
Visit D, then E
Dequeue D; enqueue its unvisited neighbour E. Queue: [E]. Dequeue E; no new neighbours. Queue empty.

Result: Visit order A, B, C, D, E. BFS reaches E in the fewest hops (A-B-D-E or A-C-D-E, three edges) - the shortest unweighted path.

Typical mistakes

Swapping the data structures: DFS uses a stack (go deep), BFS uses a queue (go wide) - getting them the wrong way round changes the whole order.
Failing to mark vertices as visited, so a cyclic graph is revisited endlessly or vertices appear twice in the order.

Active revision

For the graph with edges A-B, A-C, B-D, C-D, D-E, give the breadth-first and the depth-first visit order starting at A, visiting neighbours in alphabetical order, and show the queue (BFS) and stack (DFS) after visiting A.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Tree traversal and expression trees#

StandardAQA 7517 4.3.2DfE GCE Computer Science - tree traversal

An expression tree for (3 + 4) x 5

Fig. 2Operators sit at internal nodes, operands at the leaves; the tree's shape encodes precedence with no brackets. Post-order (left, right, node) gives Reverse Polish 3 4 + 5 x; in-order reconstructs the infix (3 + 4) x 5.

A binary tree is traversed by one of three depth-first orders, each defined by when the node itself is processed relative to its two subtrees. Pre-order visits the node first, then its left subtree, then its right (node, left, right). In-order visits the left subtree, then the node, then the right (left, node, right). Post-order visits both subtrees first and the node last (left, right, node). Each is naturally recursive: to traverse a tree you traverse its subtrees the same way, with the base case of an empty subtree.

The three orders are not interchangeable - each is the right tool for a different job. In-order traversal of a binary search tree emits its keys in sorted order, because it visits everything smaller than a node before the node and everything larger after it. Pre-order produces a copy or a prefix (Polish) form and is used to serialise or clone a tree. Post-order processes children before their parent, which is exactly what is needed to evaluate an expression, delete a tree safely, or compute a value that depends on subtrees.

An expression tree represents an arithmetic expression with operators at the internal nodes and operands at the leaves, capturing precedence in its shape without any brackets. The tree opposite represents

(3 + 4) \times 5

: the multiplication is the root, its left child is the addition of 3 and 4, its right child is 5. A post-order traversal of an expression tree yields Reverse Polish Notation (RPN) - here 3 4 + 5

\times

- which a stack-based machine can evaluate directly, while an in-order traversal reconstructs the usual infix form.

Reverse Polish (postfix) notation needs no brackets and no precedence rules, which is why compilers and calculators use it internally. It is evaluated with a stack: scan left to right, push each operand, and on each operator pop the top two operands, apply it, and push the result. Converting between infix, an expression tree and RPN, and evaluating RPN with a stack, are all standard exam tasks that reward careful, ordered working.

Worked example

Evaluating Reverse Polish with a stack

Evaluate the Reverse Polish expression 3 4 + 5 x using a stack. Show the stack after each token.

Push operands 3, 4
Push 3, then push 4. Stack (base to top): [3, 4].
Operator +
Pop 4 and 3, compute $3 + 4 = 7$ , push the result. Stack: [7].
Push 5
Push the operand 5. Stack: [7, 5].
Operator x
Pop 5 and 7, compute $7 \times 5 = 35$ , push it. Stack: [35].

Result: The single value left on the stack, 35, is the answer. RPN evaluation needs no brackets - the stack enforces the order that the tree's shape recorded.

Typical mistakes

Mixing up the three orders - remember the name states when the node (root) is visited: pre = first, in = middle, post = last.
In RPN evaluation, applying a non-commutative operator ( $-$ or $/$ ) with the operands the wrong way round after popping them off the stack.

Active revision

Draw the expression tree for $(8 - 3) \times (2 + 5)$ , give its Reverse Polish form by a post-order traversal, and evaluate that RPN expression using a stack, showing the stack after each token.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Searching: linear and binary search#

StandardAQA 7517 4.3.3DfE GCE Computer Science - searching

Comparing search growth rates

Fig. 3For a list of

n

items, linear search cost grows as

n

(the straight line) while binary search cost grows as

\log_2 n

(the flat curve). The gap widens dramatically as

n

grows: doubling

n

adds only one comparison to binary search but doubles the work of linear search.

Linear search checks each element in turn from the start until it finds the target or reaches the end. It makes no assumption about order, works on any list, and is simple, but in the worst case (the target is last or absent) it examines all

n

elements, so it runs in

O(n)

time. For a small or unsorted list it is perfectly adequate and is the only option when the data is not sorted.

Binary search is far faster but requires the list to be sorted. It repeatedly examines the middle element and, by comparing it with the target, discards half the remaining list each time: if the target is smaller it searches the left half, if larger the right half, and if equal it has found it. Because the search space halves every step, at most

\lceil \log_2 n \rceil + 1

comparisons are ever needed, giving

O(\log n)

time - a list of a million items is searched in about twenty comparisons rather than a million.

The reason binary search is logarithmic is worth deriving. Starting with

n

elements, after one comparison at most

n/2

remain, after two at most

n/4

, and after

k

comparisons at most

n/2^k

. The search ends when one element remains, i.e. when

n/2^k \leq 1

, which rearranges to

k \geq \log_2 n

. The number of steps is therefore proportional to

\log_2 n

- the defining property of the algorithm. A binary tree search applies the same halving idea to a balanced binary search tree, following the ordering invariant left or right at each node.

The efficiency gain is not free: binary search needs the data sorted first, and keeping data sorted has its own cost. So the choice is a trade-off: for a one-off search of unsorted data, linear search (with no sorting cost) may win; for repeated searches of data that can be kept sorted, binary search's logarithmic lookups pay back the sorting cost many times over. Binary search also needs random (indexed) access, so it suits arrays, not linked lists.

\text{mid} = \left\lfloor \dfrac{\text{low} + \text{high}}{2} \right\rfloor

Midpoint index

The integer midpoint of the current search bounds; binary search compares the target with the element here.

n / 2^{k} \leq 1 \;\Rightarrow\; k \geq \log_2 n

Why binary search is O(log n)

Halving $n$ elements $k$ times leaves at most $n/2^k$ ; the search ends when that reaches 1, after about $\log_2 n$ steps.

Worked example

Tracing a binary search

Search the sorted list [3, 7, 11, 15, 19, 23, 27, 31] (indices 0-7) for 23 by binary search. Give low, high, mid and the comparison at each step.

Step 1
low = 0, high = 7, mid = $\lfloor 7/2 \rfloor = 3$ . Element at 3 is 15. $23 > 15$ , so search the right half: low = 4.
Step 2
low = 4, high = 7, mid = $\lfloor 11/2 \rfloor = 5$ . Element at 5 is 23. $23 = 23$ - found.

Result: Found at index 5 in 2 comparisons. Linear search would have taken 6 comparisons to reach the same element; the advantage grows with list size.

Typical mistakes

Running a binary search on an unsorted list - it only works when the data is sorted.
Off-by-one errors when updating the bounds: after comparing the middle, set low = mid + 1 or high = mid - 1, not low = mid or high = mid, or the search can loop.

Active revision

The sorted list is [3, 7, 11, 15, 19, 23, 27, 31]. Trace a binary search for the value 23, giving low, high, mid and the comparison at each step, and state the number of comparisons made.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education)

Sorting: bubble sort and merge sort#

AdvancedAQA 7517 4.3.4DfE GCE Computer Science - sorting

Merge sort: the divide phase

Fig. 4Merge sort splits [38, 27, 43, 3] in half repeatedly until each piece is a single element. It then merges pairs back up - [27, 38] and [3, 43], then [3, 27, 38, 43] - each merge interleaving two sorted pieces. Halving

\log_2 n

times with

O(n)

work per level gives

O(n \log n)

Bubble sort repeatedly passes through the list comparing each adjacent pair and swapping them if they are out of order. Each pass 'bubbles' the largest remaining element to its final place at the end, so after

k

passes the last

k

elements are sorted. A pass with no swaps means the list is already sorted and the algorithm can stop early. Bubble sort is easy to understand and sorts in place using negligible extra memory, but it is slow: it makes about

n^2

comparisons, so its time complexity is

O(n^2)

and it is impractical for large lists.

Merge sort is a divide-and-conquer algorithm and is far more efficient. It recursively splits the list in half until each piece is a single element (which is trivially sorted), then merges pairs of sorted pieces back together into larger sorted pieces until the whole list is rebuilt in order. The splitting phase forms a tree of halvings (shown opposite); the merging phase does the real work of ordering. Because a list of

n

items can be halved only about

\log_2 n

times and each level of merging touches all

n

items, merge sort runs in

O(n \log n)

time - dramatically better than

O(n^2)

for large

n

The merge step is the heart of the algorithm: given two already-sorted lists, it repeatedly compares their front elements and takes the smaller into the output, until one list is exhausted and the rest of the other is appended. Merging two lists of total length

m

takes

O(m)

time. The cost of this efficiency is space: merge sort is not in place - it needs

O(n)

extra memory for the temporary merged lists - whereas bubble sort needs almost none. That space-versus-time trade-off is a recurring theme.

The two algorithms illustrate why complexity matters. On a list of a million items, an

O(n^2)

bubble sort makes on the order of

10^{12}

operations while an

O(n \log n)

merge sort makes about

2 \times 10^7

- roughly fifty thousand times fewer. For small or nearly-sorted lists bubble sort's simplicity and low overhead can win, but for anything large, an

O(n \log n)

sort such as merge sort is essential. Being able to trace both and to state and justify their complexities is core exam content.

T_{\text{bubble}}(n) = O(n^2), \qquad T_{\text{merge}}(n) = O(n \log n)

Sorting complexities

Bubble sort makes about $n^2$ comparisons; merge sort halves $\log_2 n$ times with $O(n)$ work per level.

Worked example

One pass of bubble sort

Perform one full left-to-right pass of bubble sort on [5, 1, 4, 2], comparing adjacent pairs and swapping if the left is larger. Show each comparison.

Compare 5 and 1
$5 > 1$ , so swap. List becomes [1, 5, 4, 2].
Compare 5 and 4
$5 > 4$ , so swap. List becomes [1, 4, 5, 2].
Compare 5 and 2
$5 > 2$ , so swap. List becomes [1, 4, 2, 5].

Result: After one pass the largest value 5 has bubbled to the end: [1, 4, 2, 5]. The next pass ignores the final element and continues until a pass makes no swaps.

Typical mistakes

Forgetting that after each bubble-sort pass the end of the list is already sorted, so later passes need not re-check it.
Describing merge sort's merge step as concatenation - it must interleave the two sorted lists by repeatedly taking the smaller front element.

Active revision

Trace one full pass of bubble sort on [5, 1, 4, 2], showing each comparison and swap and the list after the pass. Then show how merge sort splits and merges [38, 27, 43, 3] to sort it.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Dijkstra's shortest path algorithm#

AdvancedAQA 7517 4.3.5DfE GCE Computer Science - Dijkstra

A weighted graph for Dijkstra's algorithm

Fig. 5Edge labels are costs. From source A the shortest distances are A = 0, D = 1, B = 3 (via D), E = 3 (via D) and C = 8 (via D then B). The shortest path to C is A - D - B - C.

Dijkstra's algorithm finds the shortest (least-cost) path from a single source vertex to every other vertex in a weighted graph with non-negative edge weights. It generalises breadth-first search from counting edges to summing weights, and it is the algorithm behind satellite navigation, network routing and journey planning. The idea is to grow a set of settled vertices whose shortest distance from the source is known for certain, always settling next the unsettled vertex with the smallest tentative distance.

The algorithm keeps a tentative distance for every vertex - the length of the shortest path found so far - initialised to 0 for the source and infinity for the rest. It then repeats: pick the unsettled vertex

u

with the smallest tentative distance and settle it, then relax each of its edges - for a neighbour

v

, if

\text{dist}(u) + w(u,v)

is less than the current

\text{dist}(v)

, update

\text{dist}(v)

to this smaller value and record

u

as its predecessor. Settling always takes the globally closest unsettled vertex, which is why, with non-negative weights, a settled distance can never later be improved.

It is essential that weights are non-negative. Dijkstra's guarantee - that once a vertex is settled its distance is final - relies on the fact that extending a path can only lengthen it; a negative edge could later offer a cheaper route to an already-settled vertex, breaking the argument. The table opposite traces the algorithm on the graph, showing every vertex's tentative distance after each vertex is settled; a

\star

marks the vertex settled at that step.

Recording a predecessor for each vertex as it is relaxed lets the actual shortest path be reconstructed by following the predecessors backwards from the destination to the source. With a priority queue to find the closest unsettled vertex efficiently, Dijkstra runs in about

O(E \log V)

time. Tracing the algorithm as a distance table - and reading off both the shortest distance and the path - is one of the most demanding and most heavily rewarded algorithm questions in the A-Level.

\text{if } \text{dist}(u) + w(u,v) < \text{dist}(v) \text{ then } \text{dist}(v) \leftarrow \text{dist}(u) + w(u,v)

The relaxation step

When a shorter route to $v$ is found through the just-settled $u$ , the tentative distance to $v$ is lowered.

The distance table trace

Fig. 6Each row is the state after settling one vertex (the row header). A cell is that vertex's smallest tentative distance so far; the settled vertex's distance is final. D is settled first (1), then B and E (both 3), then C (8).

Worked example

Tracing Dijkstra to vertex C

Using the weighted graph (source A), find the shortest distance and path from A to C.

Settle A, relax
dist(A) = 0. Relax A's edges: dist(B) = 6, dist(D) = 1. Closest unsettled is D.
Settle D, relax
dist(D) = 1. Relax: B via D = $1 + 2 = 3$ (improves 6 to 3); E via D = $1 + 2 = 3$ . Predecessor of B and E is D.
Settle B, relax
dist(B) = 3 (tie with E; settle either). Relax: C via B = $3 + 5 = 8$ ; E stays 3. Predecessor of C is B.
Settle E then C
dist(E) = 3 relaxes C via E to $3 + 5 = 8$ (no improvement). Finally settle C at 8.

Result: Shortest distance A to C is 8. Following predecessors C <- B <- D <- A gives the shortest path A - D - B - C.

Typical mistakes

Settling a vertex other than the closest unsettled one, or updating a vertex that is already settled.
Applying Dijkstra to a graph with negative edge weights, where its correctness guarantee fails.

Active revision

Using the weighted graph opposite (source A), trace Dijkstra's algorithm as a distance table, give the shortest distance from A to C, and state the shortest path itself using the predecessors.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

AQA

AQA A-level Computer Science 7517 specification

Department for Education

GCE AS and A level subject content for computer science

Fundamentals of algorithms

5 sections~18 min reading time3 competenciesLevel Standard 2 · Advanced 3

Fundamentals of algorithms

Key points

Breadth-first traversal with the queue

Key points

Evaluating Reverse Polish with a stack

Key points

Tracing a binary search

Key points

One pass of bubble sort

Key points

Tracing Dijkstra to vertex C

Sources

Fundamentals of algorithms

Key points

Breadth-first traversal with the queue

Key points

Evaluating Reverse Polish with a stack

Key points

Tracing a binary search

Key points

One pass of bubble sort

Key points

Tracing Dijkstra to vertex C

Sources