Skip to content
Marlbridge

Study Guides

AQA A-Level Computer Science: Fundamentals of Algorithms (7517)

Guide to AQA A-Level Computer Science 7517 section 4.3: graph and tree traversal, Reverse Polish, searching, sorting, Dijkstra's algorithm and time complexity.

Level
A LEVELS
Topic
Fundamentals of algorithms
Updated

Aligned to AQA A Level Computer Science (7517), 2015-onwards. Official specification .

Syllabus page (what it covers and how it is assessed): AQA A Level Computer Science.

Syllabus topics and points this page is mapped to

7517

  • 3 Fundamentals of algorithms (topic-level mapping)

"Topic-level mapping" means this page belongs to that topic; it does not claim to cover every point in it.

Found an error? Report a correction.

Need help with this topic? Request a free trial class for A Level Computer Science (7517).

This guide covers 4.3 Fundamentals of algorithms, the third of 14 subject-content sections in the A-level-only content of AQA Computer Science (7517). It follows directly from 4.1 Fundamentals of Programming and 4.2 Fundamentals of Data Structures, since every algorithm here operates on the data structures (arrays, stacks, queues, trees, graphs) introduced in those earlier sections. These notes complement the site’s guides to Fundamentals of Programming and Data Structures and Arrays.

Where this fits in 7517

This section is Paper 1 content. The specification at a glance numbers the A-level content 10-23 (the subject-content pages number the same sections 4.1-4.14), and Paper 1 – the on-screen paper – tests programming ability together with theoretical knowledge from content 10-13 (4.1-4.4: programming, data structures, algorithms, theory of computation) and the skills of section 22 (4.13). Paper 2, the written paper, covers 14-21 (4.5-4.12). Much of this section is still assessed by tracing rather than by writing code: expect questions that give you an algorithm and a specific input and ask you to trace its exact execution step by step, or state and compare time complexities.

Syllabus coverage

AQA A-LEVEL COMPUTER SCIENCE (7517) – 4.3 FUNDAMENTALS OF ALGORITHMS

  • 4.3.1 Graph-traversal: trace breadth-first and depth-first search algorithms and describe typical applications (breadth-first: shortest path for an unweighted graph; depth-first: navigating a maze)
  • 4.3.2 Tree-traversal: trace pre-order, post-order and in-order tree-traversal algorithms and describe their uses (pre-order: copying a tree; in-order: binary search tree, outputting contents in ascending order; post-order: infix-to-RPN conversion, producing a postfix expression, emptying a tree)
  • 4.3.3 Reverse Polish: convert simple expressions between infix and Reverse Polish Notation (RPN) form, and understand why RPN is used (eliminates the need for brackets; suitable for stack-based evaluation; used in stack-based interpreters such as PostScript and bytecode)
  • 4.3.4.1 Linear search: trace and analyse its time complexity, O(n)
  • 4.3.4.2 Binary search: trace and analyse its time complexity, O(log n)
  • 4.3.4.3 Binary tree search: trace and analyse its time complexity, O(log n)
  • 4.3.5.1 Bubble sort: trace and analyse its time complexity, O(n^2) – included as an example of a particularly inefficient sorting algorithm
  • 4.3.5.2 Merge sort: trace and analyse its time complexity, O(n log n) – an example of the “divide and conquer” approach to problem solving
  • 4.3.6.1 Dijkstra’s shortest path algorithm: understand and be able to trace it, and be aware of its applications (students are not expected to recall the steps unprompted)

How to approach it

Every algorithm in this section falls into one of three exam-question types: trace it on a given input, state its time complexity, or explain when you would use it over an alternative. Build a single comparison table across all the searching and sorting algorithms – complexity, best use case, what data structure it needs (sorted or unsorted, array or tree) – since “compare X and Y” questions are common and reward exactly this kind of side-by-side knowledge.

Official syllabus

AQA A-level Computer Science (7517) specification, first teaching 2015 – aqa.org.uk.

A weighted graph with nodes A to F (illustrative): A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3. From A the algorithm fixes nodes in the order A, C, B, D, E, F with shortest distances 0, 2, 3, 8, 10, 13. The shortest route from A to F is A, C, B, D, E, F with total 13.
Dijkstra's algorithm fixes the closest unfixed node each time and updates its neighbours' distances.

Graph and tree traversal: the same idea, two structures

Breadth-first search explores a graph level by level using a queue, making it the natural choice for finding the shortest path in an unweighted graph. Depth-first search explores as far as possible along one branch before backtracking, using a stack, which is why it suits maze-navigation problems. Tree traversal applies the same underlying idea to a more constrained structure: in-order traversal of a binary search tree always outputs values in ascending order, which is the single fact most exam questions on tree traversal are built around.

The same seven-node graph (illustrative) traversed from A two ways. Breadth-first search uses a queue and visits A B C D E F G level by level. Depth-first search uses a stack and visits A B D C E G F, going deep before backtracking. After A and B are visited the queue and the stack both hold C and D, but the queue next releases C and the stack next releases D.
Breadth-first search takes the front of a queue; depth-first search takes the top of a stack.
An illustrative binary search tree with root 40, children 20 and 60 and leaves 10, 30, 50 and 70, drawn three times with nodes numbered in visiting order. Pre-order gives 40 20 10 30 60 50 70 (copying a tree), in-order gives 10 20 30 40 50 60 70 (ascending order) and post-order gives 10 30 20 50 70 60 40 (postfix expressions, emptying a tree).
In-order traversal of a binary search tree always comes out in ascending order.

Searching and sorting: complexity is the exam’s real focus

Linear search checks every element in turn (O(n)) and works on unsorted data; binary search repeatedly halves the search space (O(log n)) but requires the data to already be sorted. This trade-off – binary search is faster but has a precondition linear search does not – is a frequent short-answer question. Bubble sort (O(n^2)) is deliberately included as an example of an inefficient algorithm to contrast against merge sort (O(n log n)), which achieves its better complexity through the divide-and-conquer principle of repeatedly splitting the problem in half.

Finding 34 in the sorted list 3, 8, 12, 17, 21, 26, 34, 41 (illustrative). Linear search checks seven items in turn. Binary search checks the middle item three times (17, 26, then 34), halving the search area each time, but only works because the list is sorted. For 1,024 sorted items linear search needs up to 1,024 checks and binary search at most 11.
Binary search is much faster than linear search, but only on sorted data.
Bubble sort on 6, 3, 5, 1, 4, 2 (illustrative) shown after each pass, with the values already in their final place at the end. Six items need five passes and 15 comparisons. Comparisons grow with the square of the number of items: 15 for 6 items, 66 for 12 and 276 for 24, so the time complexity is O(n squared).
Bubble sort is O(n²): doubling the number of items roughly quadruples the comparisons.
Merge sort on 6, 3, 7, 1, 8, 2, 5, 4 (illustrative). The list is divided into two fours, four twos and eight single items, then merged back through four sorted pairs and two sorted fours into one sorted list 1 to 8. Three levels of splitting and three of merging give n log n growth: 24 for 8 items, against 64 for n squared.
Merge sort repeatedly halves the problem, which is why it reaches O(n log n).

Worked example: converting infix to Reverse Polish Notation

The expression (3 + 4) * 2 converts to RPN as follows, using a simple stack-based method:

Step 1 - scan left to right, output operands immediately:
3, 4 go straight to output.

Step 2 - push operators onto a stack, respecting brackets:
'(' opens a scope; '+' is pushed; ')' closing pops '+' to output.

Step 3 - continue scanning:
'*' is pushed once no higher-priority operator blocks it.

Step 4 - at the end, pop all remaining operators to output:
Result: 3 4 + 2 *

Reading 3 4 + 2 * back: add 3 and 4 (giving 7), then multiply by 2 (giving 14) – exactly matching (3 + 4) * 2, but with no brackets needed, which is precisely why RPN suits stack-based evaluation.

Converting (3 + 4) * 2 to RPN with an operator stack: the table shows each symbol read, the output so far and the operator stack, ending with 3 4 + 2 *. Below, evaluating 3 4 + 2 * with a number stack: push 3, push 4, plus gives 7, push 2, multiply gives 14.
RPN needs no brackets and is evaluated left to right with a stack.

Common mistakes

Confusing pre-order, in-order and post-order traversal outputs for the same tree. Stating binary search’s complexity without noting its precondition that the data must already be sorted. Describing bubble sort’s inefficiency without being able to state its actual complexity, O(n^2). Forgetting that Dijkstra’s algorithm’s exact steps are not required for recall – only tracing a worked example and knowing its applications. Reversing the queue/breadth-first and stack/depth-first pairing.

Quick revision checklist

  • Trace breadth-first and depth-first graph traversal on a given graph, and state a typical use for each.
  • Trace pre-order, post-order and in-order tree traversal on a given binary tree.
  • Convert an infix expression to RPN and back, and explain why RPN avoids the need for brackets.
  • State the time complexity of linear search, binary search, binary tree search, bubble sort and merge sort, and explain the trade-offs between them.
  • Trace Dijkstra’s shortest path algorithm on a given weighted graph and describe an application.

Frequently asked questions

What is the time complexity of bubble sort and merge sort? Bubble sort is O(n²) and is included as an example of an inefficient algorithm. Merge sort is O(n log n), achieved through the divide-and-conquer approach.

Which tree traversal outputs a binary search tree in order? In-order traversal of a binary search tree outputs its values in ascending order. Pre-order is used for copying a tree, and post-order for producing a postfix expression or emptying a tree.

Do you need to memorise Dijkstra’s algorithm for AQA 7517? No. Students must understand and trace Dijkstra’s shortest path algorithm and know its applications, but are not expected to recall its steps unprompted.

Why is Reverse Polish Notation used? RPN removes the need for brackets and suits stack-based evaluation, which is why it is used in stack-based interpreters such as PostScript and bytecode.

Get free revision emails (optional)

Occasional emails with practice questions, worked explanations and links to free resources for the qualification and subjects you choose. No spam, and you can unsubscribe from any email. The free tools on this site never need an email.

Subjects (optional, up to 6)

Choose a qualification to see its subjects.

Related resources

Related articles

Studying this with a teacher

Working through Computer Science A LEVELS?

This page is free and stays free. If you would rather be taught it, Marlbridge runs Computer Science classes one-to-one and in small groups of up to 15, online in your own time zone. The first trial class is free. WhatsApp replies within an hour (8am–11pm Pakistan time, every day); email the same day.

AQA Computer Science teachers at Marlbridge