Data Abstraction & Problem Reduction

AQA 4.4.5 — Data abstraction and problem reduction

Retrieval: Year 12's algorithmic-thinking taught recognising a problem's underlying structure. This lesson names that skill precisely as problem reduction, and pairs it with data abstraction — the same abstraction principle from earlier this sequence, now applied specifically to choosing how data is represented.

Key vocabulary

• Data abstraction — choosing a data representation based on the operations a problem genuinely needs, hiding the concrete storage detail from the rest of the program.
• Abstract Data Type (ADT) — Year 12 Sequence 4's own example of data abstraction: a stack or queue defined entirely by its operations, independent of how it's actually stored.
• Problem reduction — transforming an unfamiliar problem into a form of a problem you already know how to solve.

Understand — data abstraction, retrieved and named precisely

Every data structure covered across Year 12 and Sequence 12 was, in fact, an exercise in data abstraction: choosing a representation (array, stack, queue, dictionary, graph, tree, hash table) based on which operations a problem genuinely needs — fast lookup, ordered access, relational connections — while hiding exactly how that representation is stored underneath. This lesson doesn't re-teach any of those structures; it names the design principle that was silently guiding every one of those earlier selection decisions.

Understand — problem reduction, precisely

A reduction transforms a new problem into an already-solved one. Concretely: "find the shortest number of button presses to reach a target number on a calculator, starting from 0, using only +1, -1, or ×2" can be reduced to a graph shortest-path problem — each reachable number becomes a vertex, each button press becomes an edge connecting one number to another, and Sequence 13's BFS (unweighted shortest path) directly solves it.

Reason about what a reduction preserves

The reduction above preserves the solution structure: the shortest path found in the reduced graph corresponds exactly to the fewest button presses in the original calculator problem, even though the reduced form (vertices and edges) looks nothing like the original problem statement (numbers and buttons). What a valid reduction must preserve is this correspondence between solutions — solving the reduced problem correctly must always translate back into a correct solution to the original problem.

Reason about where a reduction fails or becomes insufficient

Extend the calculator problem: suppose one button doesn't just change the number, but also makes a future press "free" — effectively giving that operation a different cost than the others. The straightforward BFS-based reduction above assumes every edge (every button press) costs exactly the same — Sequence 13's own correctness argument for BFS depends on this. Once operations have genuinely different costs, the reduction to a plain unweighted graph is no longer sufficient — the problem would need reducing to a weighted shortest-path problem instead, solved with Dijkstra, not BFS. Recognising when a chosen reduction stops being valid is as important a skill as constructing the reduction in the first place.

Diagnose the flawed reduction

A student is asked to find the minimum number of coins needed to make a target amount, and proposes reducing it to "always greedily use the largest coin that doesn't exceed what's left." For standard currency (coins: 1p, 5p, 10p, 25p) and a target of 30p, this greedy approach gives 25p + 5p — 2 coins, genuinely optimal. But for coins {1, 3, 4} and a target of 6, the same greedy approach gives 4 + 1 + 1 — 3 coins — while the genuine minimum is 3 + 3, only 2 coins. Identify a genuine reason greedy coin selection is not a universally valid reduction for this problem, even though it works for some coin sets and targets.

(Greedy coin selection is only a VALID reduction for certain coin systems (ones where the denominations are structured so the greedy choice is always safe, such as standard currency) - for other coin sets like {1, 3, 4}, greedily taking the largest coin available can genuinely produce a worse-than-minimum answer, because taking a large coin now (4) can leave a remaining amount (2) that needs more coins than a different, less "greedy" first choice (3, leaving exactly 3) would have. The reduction "this is always safely solved by taking the biggest coin each time" only preserves correctness for specific coin systems - it is not a universally valid reduction, exactly the "where a model becomes insufficient" issue this lesson is about.)

Common mistake

Assuming a reduction that works correctly on a few example cases is therefore valid in general. As the coin-selection task shows, a reduction can appear to work for several test cases while still being fundamentally invalid for the general problem — genuinely checking why a reduction preserves correctness (not just checking it against examples) is what this lesson's "Reason about what a reduction preserves" section is for.

Why this matters for the NEA

Recognising that a new, seemingly novel problem in an NEA project is actually a variant of something already known how to solve — and choosing data structures based on genuinely required operations, not habit — is precisely the kind of independent analytical thinking AQA's NEA marking rewards at the highest level.

Check your understanding

A city planner wants the fewest number of bus-changes needed to travel between two specific stops in a transit network, where every direct route between two stops counts as exactly one "change," regardless of distance. Identify which algorithm this problem reduces to. (2 marks)

(BFS (unweighted shortest path) - each stop is a vertex, each direct route an edge, and since every change costs the same "one hop" regardless of distance, this is exactly Sequence 13's unweighted shortest-path problem, not a weighted one.)

Challenge

Propose a reduction for the following problem: "find the fewest number of exact-change coin exchanges needed to convert one currency amount into another, where each exchange has a fixed conversion table." Identify what your reduction preserves, and state one condition under which it might fail.

Looking ahead: the final lesson of this sequence brings decomposition, composition and automation together — the practical discipline of actually building and evaluating a complete solution from the pieces this sequence has covered.