AQA 7517 · Paper 1 · 4.13.1

Problem Solving
& Algorithms

Decomposition · abstraction · algorithm design · testing strategies · Big O

WHAT YOU'LL LEARN

Computational thinking · decomposition · abstraction · algorithm design · testing · Big O complexity

AQA SPEC LINK

4.13.1 — Problem solving: computational thinking, decomposition, abstraction, algorithms, testing

Computational Thinking

Computational thinking is the thought process of formulating a problem and expressing its solution in a way that a computer can execute. It involves four key concepts.

Decomposition — breaking a complex problem into smaller, more manageable sub-problems

Abstraction — identifying and removing unnecessary detail; focusing on what matters

Pattern recognition — identifying similarities and patterns that can be reused

Algorithm design — creating step-by-step instructions to solve the problem

Decomposition

Decomposition breaks a large problem into smaller sub-problems, each of which can be solved independently then combined.

Build a school website →

Design the UI
Build the student login
Create the lesson database
Implement the payment system
Test and deploy

Each sub-problem can be assigned to a different developer; easier to test and debug independently

Abstraction

Abstraction removes irrelevant detail to focus on the essential features of a problem. A model or representation captures what matters without the complexity.

A map is an abstraction of the real world — it removes buildings, trees, street signs; keeps roads and distances

A class in OOP is an abstraction — hides implementation details, exposes only the interface

Good abstraction makes programs easier to understand, maintain, and reuse

Levels of abstraction: machine code → assembly → high-level language → problem domain

Algorithm Design

Algorithm Design Strategies

Divide and conquer — split problem in half recursively; solve each half; merge results (e.g. merge sort, binary search)

Dynamic programming — break into overlapping sub-problems; store solutions to avoid recomputation (memoisation)

Greedy algorithm — always make the locally optimal choice at each step (e.g. Dijkstra's shortest path)

Backtracking — try a solution; if it fails, undo and try another (e.g. solving a maze, Sudoku)

Big O Complexity

Algorithm Complexity — Big O

Big O notation describes how the time/space requirement of an algorithm grows as input size n increases.

Notation	Name	Example
O(1)	Constant	Array index access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n²)	Quadratic	Bubble sort
O(2ⁿ)	Exponential	Brute force password

Testing

Testing Strategies

White box testing — tester knows the internal code; tests all branches and paths

Black box testing — tester has no knowledge of code; tests based on specification/requirements

Unit testing — test individual functions/modules in isolation

Integration testing — test how modules work together

Alpha testing — internal testing by developer/team; beta testing — tested by a limited group of real users

Regression testing — re-run previous tests after changes to ensure nothing is broken

Test Data

Test Data Types

To fully test a program, you need three categories of test data:

Normal (valid) data

Data within the expected range. The program should accept and process correctly. E.g. age = 17 for a 0-120 range.

Boundary (edge) data

Values at the edges of valid range. E.g. age = 0 and age = 120. Errors often occur at boundaries.

Erroneous (invalid) data

Data that should be rejected. E.g. age = -5 or age = "abc". Program should handle gracefully, not crash.

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) Explain the difference between decomposition and abstraction in computational thinking. [4]
(b) A function accepts an age between 0 and 130. Give ONE example of normal, ONE boundary, and ONE erroneous test value. [3]
(c) An algorithm has O(n²) complexity. Explain what this means and why it matters. [3]

[10 marks]

4 marks

(a) Decomposition breaks a complex problem into smaller, manageable sub-problems [1] that can be solved independently and combined [1]; abstraction removes unnecessary detail [1] to focus on the essential features relevant to solving the problem [1]

3 marks

(b) Normal: any value in range e.g. 25 [1]; boundary: 0 or 130 [1]; erroneous: negative number, value over 130, or non-numeric input e.g. "abc" [1]

3 marks

(c) The time taken grows proportionally to the square of the input size [1]; doubling n makes the algorithm 4x slower [1]; matters because for large n it becomes very slow — e.g. bubble sort on 1 million items requires 1 trillion operations [1]

Summary

Key Points to Remember

Computational thinking: decomposition, abstraction, pattern recognition, algorithm design

Decomposition — break into sub-problems; abstraction — remove irrelevant detail

Algorithm strategies: divide & conquer · dynamic programming · greedy · backtracking

Big O: O(1) constant · O(log n) logarithmic · O(n) linear · O(n²) quadratic · O(2ⁿ) exponential

Test data: normal (valid), boundary (edge), erroneous (invalid)

Testing: white box, black box, unit, integration, alpha, beta, regression

🎉 All 70 AQA 7517 slide decks complete!