AQA GCSE Computer Science: Algorithms and Computational Thinking

Algorithms are at the heart of AQA GCSE Computer Science. They appear throughout Paper 1, and a solid understanding of how they work -- and how to communicate them clearly -- is essential for achieving a strong grade. This guide covers everything you need to know about algorithms and computational thinking for the AQA specification, including searching and sorting algorithms, computational thinking skills, flowcharts, pseudo-code, trace tables, and the exam technique that will help you pick up every available mark.

What Is an Algorithm?

An algorithm is a finite sequence of well-defined instructions designed to perform a specific task or solve a particular problem. You encounter algorithms constantly in everyday life -- a recipe, a set of directions, or a morning routine can all be described as algorithms. In computer science, algorithms are the building blocks of programs. Every piece of software, from a search engine to a game, relies on algorithms to process data and produce results.

For AQA GCSE Computer Science, you need to be able to:

• Understand and explain standard algorithms (searching and sorting)
• Create your own algorithms to solve problems
• Represent algorithms using flowcharts and pseudo-code
• Trace through algorithms using trace tables
• Compare algorithms in terms of efficiency

These skills are tested directly in Paper 1: Computational Thinking and Programming Skills, which accounts for 50% of your final grade.

Searching Algorithms

Searching algorithms are used to find a specific item within a data set. AQA requires you to know two searching algorithms: linear search and binary search.

Linear Search

Linear search is the simplest searching algorithm. It works by checking each item in a list one at a time, starting from the first item, until the target value is found or the end of the list is reached.

How it works:

1. Start at the first item in the list.
2. Compare the current item with the target value.
3. If they match, the search is complete -- return the position.
4. If they do not match, move to the next item.
5. Repeat until the target is found or the end of the list is reached.
6. If the end of the list is reached without finding the target, the item is not in the list.

Key characteristics:

• Works on both sorted and unsorted lists
• Simple to understand and implement
• Can be slow for large data sets because, in the worst case, every item must be checked

In pseudo-code:

SUBROUTINE linearSearch(list, target)
    FOR i <- 0 TO LEN(list) - 1
        IF list[i] = target THEN
            RETURN i
        ENDIF
    ENDFOR
    RETURN -1
ENDSUBROUTINE

Binary Search

Binary search is a much more efficient algorithm, but it only works on data that has already been sorted. It works by repeatedly dividing the search area in half.

How it works:

1. Find the middle item of the list.
2. Compare it with the target value.
3. If the middle item matches the target, the search is complete.
4. If the target is less than the middle item, discard the upper half and repeat with the lower half.
5. If the target is greater than the middle item, discard the lower half and repeat with the upper half.
6. Repeat until the target is found or the search area is empty.

Example: Searching for 23 in the sorted list [3, 7, 11, 15, 23, 31, 42].

• Middle item: 15. Target (23) is greater, so search the upper half [23, 31, 42].
• Middle item: 31. Target (23) is less, so search the lower half [23].
• Middle item: 23. Target found.

In pseudo-code:

SUBROUTINE binarySearch(list, target)
    low <- 0
    high <- LEN(list) - 1
    WHILE low <= high
        mid <- (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSEIF list[mid] < target THEN
            low <- mid + 1
        ELSE
            high <- mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDSUBROUTINE

Comparing Linear and Binary Search

Feature	Linear Search	Binary Search
Requires sorted data?	No	Yes
Best case	1 comparison	1 comparison
Worst case	n comparisons	log2(n) comparisons
Efficiency on large data sets	Poor	Very good
Simplicity	Very simple	More involved

The most common exam question on this topic asks you to explain why binary search is more efficient than linear search, or to identify a scenario where linear search must be used (when the data is unsorted). Make sure you can articulate the trade-off: binary search is faster, but it requires the data to be sorted first, and sorting has its own cost.

Sorting Algorithms

AQA requires you to know three sorting algorithms: bubble sort, merge sort, and insertion sort. You must understand how each one works, be able to trace through them step by step, and compare their efficiency.

Bubble Sort

Bubble sort works by repeatedly stepping through the list, comparing adjacent pairs of items, and swapping them if they are in the wrong order. After each full pass through the list, the largest unsorted item "bubbles" to its correct position at the end.

How it works:

1. Start at the beginning of the list.
2. Compare the first item with the second. If the first is greater, swap them.
3. Move to the next pair and repeat.
4. Continue until the end of the list -- this completes one pass.
5. Repeat the entire process. After each pass, one fewer item needs to be checked.
6. Stop when a complete pass is made with no swaps -- the list is sorted.

Example: Sorting [5, 3, 8, 1] using bubble sort.

• Pass 1: [3, 5, 1, 8] (three comparisons, two swaps)
• Pass 2: [3, 1, 5, 8] (two comparisons, one swap)
• Pass 3: [1, 3, 5, 8] (one comparison, one swap)
• Pass 4: [1, 3, 5, 8] (no swaps -- sorted)

Key characteristics:

• Simple to understand and code
• Very inefficient for large data sets
• Best used on small lists or lists that are nearly sorted

Merge Sort

Merge sort uses a divide-and-conquer approach. It splits the list into smaller and smaller sub-lists until each sub-list contains a single item, then repeatedly merges these sub-lists back together in the correct order.

How it works:

1. If the list has one item (or is empty), it is already sorted -- return it.
2. Split the list into two roughly equal halves.
3. Recursively apply merge sort to each half.
4. Merge the two sorted halves together by comparing the first items of each and placing the smaller one into the result list. Repeat until both halves are fully merged.

Example: Sorting [6, 2, 8, 4, 3, 7] using merge sort.

• Split: [6, 2, 8] and [4, 3, 7]
• Split again: [6] [2, 8] and [4] [3, 7]
• Split again: [6] [2] [8] and [4] [3] [7]
• Merge: [2, 6] [8] and [3, 4] [7] (merging pairs in order)
• Merge: [2, 6, 8] and [3, 4, 7]
• Final merge: [2, 3, 4, 6, 7, 8]

Key characteristics:

• More efficient than bubble sort and insertion sort on large data sets
• Consistent performance regardless of the initial order of items
• Uses more memory because it creates new sub-lists during the splitting process
• More difficult to understand and implement than the other two sorts

Insertion Sort

Insertion sort builds the sorted list one item at a time. It takes each item from the unsorted portion and inserts it into the correct position in the sorted portion.

How it works:

1. Treat the first item as a sorted sub-list of one item.
2. Take the next item from the unsorted portion.
3. Compare it with each item in the sorted portion, moving from right to left.
4. Shift items in the sorted portion to the right to make space.
5. Insert the item into its correct position.
6. Repeat until all items have been inserted.

Example: Sorting [5, 3, 8, 1] using insertion sort.

• Start: sorted portion [5], unsorted [3, 8, 1]
• Insert 3: compare with 5, shift 5 right, insert 3 -- [3, 5, 8, 1]
• Insert 8: compare with 5, 8 is greater, no shift needed -- [3, 5, 8, 1]
• Insert 1: compare with 8, shift; compare with 5, shift; compare with 3, shift; insert 1 -- [1, 3, 5, 8]

Key characteristics:

• Simple to understand and implement
• Efficient for small data sets or data that is nearly sorted
• Less efficient than merge sort for large, randomly ordered data sets
• Sorts "in place" (does not require significant additional memory)

Comparing the Three Sorting Algorithms

Feature	Bubble Sort	Merge Sort	Insertion Sort
Efficiency (worst case)	Slow (n squared)	Fast (n log n)	Slow (n squared)
Memory usage	Low (in place)	Higher (extra lists)	Low (in place)
Best for	Very small or nearly sorted lists	Large data sets	Small or nearly sorted lists
Ease of implementation	Very easy	More involved	Easy

A typical exam question might give you a list and ask you to show the state of the list after each pass of a particular sort, or to explain why merge sort is preferred for large data sets despite being harder to implement.

Computational Thinking

Computational thinking is a set of problem-solving skills that underpin everything in computer science. AQA identifies four key components, and you need to understand and be able to apply all of them.

Decomposition

Decomposition is the process of breaking a large, complex problem down into smaller, more manageable sub-problems. Each sub-problem can then be solved individually, making the overall task much easier.

Example: Building a quiz application could be decomposed into: designing the user interface, storing the questions and answers, implementing the scoring system, and managing user input.

Abstraction

Abstraction is the process of removing unnecessary detail and focusing only on the information that is relevant to the problem at hand. It allows you to create a simplified model that is easier to work with.

Example: A map of the London Underground is an abstraction. It shows stations and connections but removes real-world details like the actual distances between stations, the depth of tunnels, and the terrain above ground. These details are not needed to plan a journey.

Pattern Recognition

Pattern recognition involves identifying similarities or trends within problems or between different problems. Recognising patterns allows you to reuse solutions and develop general-purpose algorithms.

Example: If you notice that several problems all require you to find the largest value in a list, you can write one general algorithm for that task and reuse it, rather than writing separate solutions each time.

Algorithmic Thinking

Algorithmic thinking is the ability to define a clear set of steps to solve a problem. It involves thinking about the order of operations, how to handle different cases, and how to structure a solution so that it can be followed precisely -- by a human or a computer.

Example: Working out the steps needed to calculate the average of a list of numbers: add all the numbers together, count how many numbers there are, and divide the total by the count.

In the exam, computational thinking questions often appear as the opening part of longer programming questions. You might be asked to decompose a problem before writing code, or to explain how abstraction has been used in a given scenario.

Flowcharts

A flowchart is a visual representation of an algorithm using standard symbols connected by arrows to show the flow of control.

Standard flowchart symbols:

• Oval (rounded rectangle): Start and end points
• Rectangle: A process or instruction (e.g., total <- total + 1)
• Parallelogram: Input or output (e.g., OUTPUT total or INPUT name)
• Diamond: A decision (yes/no question, e.g., Is x > 10?)
• Arrow: Shows the direction of flow

Tips for drawing flowcharts in the exam:

• Always include a start and end symbol.
• Use the correct shape for each type of operation -- marks are awarded for using the right symbols.
• Make sure all arrows are labelled where there is a decision (typically "Yes" and "No").
• Keep the layout clear and tidy. Flow should generally go top to bottom, with loops going back up on one side.
• If the flowchart represents a loop, the arrow should clearly loop back to the correct decision point.

Flowchart questions in Paper 1 may ask you to complete a partially drawn flowchart, draw one from a description, or trace through a given flowchart to determine its output.

Pseudo-Code

Pseudo-code is a way of writing an algorithm in structured, human-readable text that resembles a programming language but is not tied to any specific language syntax. AQA has its own pseudo-code conventions that are used throughout Paper 1.

You must be familiar with AQA's pseudo-code for:

• Variable assignment: x <- 5
• Selection: IF ... THEN ... ELSEIF ... ELSE ... ENDIF
• Iteration: FOR ... ENDFOR, WHILE ... ENDWHILE, REPEAT ... UNTIL
• Input and output: USERINPUT, OUTPUT
• Subroutines: SUBROUTINE name(parameters) ... ENDSUBROUTINE
• String and array operations: LEN(), SUBSTRING(), indexing with square brackets

Even if you learned to program in Python, the exam will use AQA pseudo-code in many questions. You can choose to write your own solutions in pseudo-code or in a real programming language, but you must be able to read and trace through AQA's pseudo-code accurately. For a full breakdown of the pseudo-code conventions and other exam strategies, see our AQA GCSE Computer Science Exam Guide.

Trace Tables

A trace table is a technique for tracking the values of variables as an algorithm executes, line by line. They are essential for verifying that an algorithm produces the correct output and for finding errors in code.

How to use a trace table:

1. Create a column for each variable in the algorithm and one for any output.
2. Work through the algorithm one step at a time.
3. Each time a variable changes value, write the new value in the next row of the appropriate column.
4. If a variable does not change during a step, leave its cell blank or carry the value down.

Example: Trace the following algorithm:

x <- 1
y <- 0
WHILE x <= 4
    y <- y + x
    x <- x + 1
ENDWHILE
OUTPUT y

Step	x	y	Output
1	1	0
2	2	1
3	3	3
4	4	6
5	5	10	10

The output is 10 (the sum of 1 + 2 + 3 + 4).

Common mistakes with trace tables:

• Forgetting to update a variable after an assignment
• Getting confused about when a loop condition is checked (before the loop body executes for WHILE loops, after the loop body for REPEAT ... UNTIL loops)
• Skipping the final check of the loop condition that causes the loop to exit
• Writing the output at the wrong point in the trace

Trace table questions are almost guaranteed to appear in Paper 1. Practise them regularly, and always double-check your working before moving on.

Efficiency and Big-O Basics

While AQA GCSE Computer Science does not require formal Big-O notation, the specification does expect you to compare the efficiency of algorithms. Understanding the basic idea behind Big-O will help you explain these comparisons clearly.

Efficiency describes how the number of operations an algorithm requires grows as the size of the input increases.

• Linear search has a worst-case performance that grows proportionally with the number of items. If you double the list size, you roughly double the number of comparisons. This is described as O(n).
• Binary search grows much more slowly. Doubling the list size adds only one extra comparison. This is described as O(log n).
• Bubble sort and insertion sort have worst-case performance that grows with the square of the number of items. Doubling the list size roughly quadruples the time taken. This is described as O(n squared).
• Merge sort grows more slowly, at O(n log n), which is significantly better for large data sets.

In the exam, you will not need to write O(n) or O(n log n) formally. However, you should be able to explain in words that binary search "halves the data with each comparison, making it much more efficient for large data sets" or that merge sort "handles large lists more efficiently than bubble sort because it does not repeatedly compare every pair of items." Clear, specific explanations of why one algorithm is faster than another will earn you full marks.

How These Topics Appear in Paper 1

Algorithms and computational thinking are central to Paper 1. Here is how they typically appear:

• Short-answer questions (1--4 marks): Define a term (e.g., "What is abstraction?"), state an advantage of binary search over linear search, or identify the type of search or sort shown in a piece of code.
• Trace table questions (3--6 marks): You are given an algorithm and asked to complete a trace table showing the values of variables at each step.
• Algorithm design questions (4--8 marks): You are asked to write an algorithm in pseudo-code or a programming language to solve a given problem, often involving searching, sorting, or data processing.
• Flowchart questions (2--5 marks): Complete a partially drawn flowchart or draw one from scratch to represent a described process.
• Extended-answer questions (6--8 marks): Compare two algorithms (e.g., "Compare the efficiency of bubble sort and merge sort for sorting a large data set"), explain a computational thinking concept in context, or design a solution to a more complex problem using decomposition and algorithmic thinking.

Exam Technique for Algorithm Questions

Read the Question Twice

Algorithm questions are precise. A small misreading -- confusing "less than" with "less than or equal to," for instance -- can throw off your entire answer. Read the question carefully, underline key words, and make sure you understand exactly what is being asked before you start writing.

Show Your Working

For trace table and algorithm-tracing questions, lay out your working neatly. If you make an error midway through, the examiner can still award method marks for the correct steps that follow your mistake -- but only if your working is clear enough to follow.

Use the Correct Terminology

When comparing algorithms, use precise language. Do not say "binary search is better." Instead, say "binary search is more efficient for large sorted data sets because it eliminates half of the remaining items with each comparison." Vague answers lose marks.

Practise Writing Algorithms Under Timed Conditions

You cannot learn to write algorithms just by reading about them. You must practise regularly, ideally under timed conditions. Write sorting and searching algorithms from memory, create trace tables for unfamiliar code, and draw flowcharts for real-world processes.

Check Your Edge Cases

When writing an algorithm, think about what happens when the list is empty, when the target is the first or last item, or when all items are identical. Examiners deliberately include these scenarios to test whether your algorithm handles them correctly.

Do Not Panic About Unfamiliar Problems

Paper 1 will often present a problem you have not seen before. That is the point -- it tests problem-solving, not memorisation. Use decomposition to break the problem into smaller parts, identify any patterns, and build your solution step by step. If you can write a clear, logical algorithm that addresses the problem, you will earn marks even if the solution is not perfectly optimised.

Prepare with LearningBro

Mastering algorithms and computational thinking takes practice. Use our free courses to test your knowledge and build confidence before your exam:

• AQA GCSE Computer Science: Algorithms -- practise searching, sorting, and algorithm design questions
• AQA GCSE Computer Science: Computational Thinking -- test your understanding of abstraction, decomposition, and problem-solving skills
• AQA GCSE Computer Science Exam Guide -- detailed exam technique for both Paper 1 and Paper 2