Divide & Conquer, Backtracking, Heuristics & Data Mining (OCR A-Level CS 2.2.2)

Free Divide Conquer Heuristics revision resources (OCR A-Level Computer Science, 2.2.2)

We’ve made exam-style practice for this exact topic, free to download: Divide Conquer Heuristics question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.

Once a problem is recognised and decomposed, you choose a strategy to solve it. Spec point 2.2.2(d)–(f) covers a toolkit of computational methods: divide and conquer, abstraction, backtracking, data mining, heuristics, performance modelling, pipelining and visualisation. Paper 2 expects you to define each, recognise it in a scenario, and give an example — so this post is your glossary with the examples that earn marks.

Divide and conquer

Divide and conquer solves a problem by repeatedly breaking it into smaller sub-problems of the same type until they're trivial to solve, then combining the results. Crucially, each step discards or isolates part of the problem, so the work shrinks fast.

The classic examples are binary search (halve the search space each step) and merge sort / quicksort (split the list, sort the halves, combine). A quicksort is "divide and conquer" because it partitions the list around a pivot and recursively sorts each part. (Note: binary search has a precondition — the data must be sorted.) "Explain why a quicksort is a divide-and-conquer algorithm" is a common 2-mark question.

Abstraction

Abstraction (revisited from 2.1.1, here as a problem-solving method) means removing unnecessary detail to focus on the essentials, producing a simpler model of the problem. Representing a road network as a graph of nodes and weighted edges is abstraction — the routing algorithm doesn't care about tarmac or scenery. It makes problems manageable and general.

Backtracking

Backtracking explores possible solutions step by step, and undoes (backtracks) the last choice when it leads to a dead end, then tries a different option. It's how you'd solve a maze (try a path; if it's blocked, return to the last junction and try another) or a Sudoku (place a digit; if it breaks a rule later, undo it). It systematically searches without trying every possibility blindly.

Data mining

Data mining is searching large data sets for patterns, trends and relationships that aren't obvious. Businesses mine purchase data to spot which products sell together; it finds unexpected connections between variables. It turns big, messy data into useful insight (and raises the privacy issues from 1.5.2).

Heuristics

A heuristic is a "rule of thumb" — a practical approach that finds a good-enough solution quickly, without guaranteeing the best one. They're used when an exact method would take too long. For example, a sat-nav uses heuristics to find a near-optimal route fast rather than checking every possible route; antivirus software uses heuristics to flag likely malware. Trade-off: speed and feasibility in exchange for not guaranteeing the optimal answer.

Performance modelling

Performance modelling means using a model (often mathematical) to predict how a system will behave under different conditions — instead of building it and finding out the expensive way. It's used to test how software will cope with heavy load, or to model systems that are too costly or dangerous to test for real (e.g. nuclear reactors, aircraft, financial markets).

Pipelining

Pipelining means starting the next instruction (or stage) before the previous one has finished, so different stages run at once — like an assembly line. In a processor, while one instruction is being executed, the next is being decoded and another fetched (you met this in 1.1.1). It increases throughput without making any single step faster.

Visualisation

Visualisation means presenting data graphically — charts, graphs, heat maps, diagrams — so that patterns and relationships are easy for humans to see and understand. A heat map of website clicks instantly shows where users look; a graph reveals a trend that a table of numbers hides. It aids both analysis and communication of results.

Worked example: matching method to scenario

• "A robot finds its way out of a maze, reversing at dead ends" → backtracking.

• "A supermarket finds which products are often bought together" → data mining.

• "A delivery app finds a near-optimal route quickly without checking every option" → heuristics.

• "A list is sorted by splitting it, sorting the halves and merging" → divide and conquer.

Recognising the method from its description is exactly what 2.2.2(f) tests.

Common exam mistakes

• Divide and conquer ≠ just decomposition. It repeatedly splits into the same type of sub-problem and combines results (binary search, merge/quicksort).

• Heuristic isn't "a guess". It's a rule of thumb giving a good-enough answer fast — not guaranteed optimal.

• Backtracking vs brute force. Backtracking undoes dead ends and tries alternatives systematically; it isn't trying every combination blindly.

• Data mining vs a normal search. Data mining finds hidden patterns/relationships in large data, not a single known record.

• Pipelining vs parallel processing. Pipelining overlaps stages of a sequence; it's not the same as running fully separate tasks at once.

Quick recap

• Divide and conquer: repeatedly split into same-type sub-problems, then combine (binary search, merge/quicksort).

• Abstraction: remove detail to model the essentials.

• Backtracking: explore step by step; undo dead ends and try alternatives (maze, Sudoku).

• Data mining: find hidden patterns in large data sets.

• Heuristics: rule-of-thumb for a good-enough answer fast; performance modelling: predict behaviour with a model; pipelining: overlap stages for throughput; visualisation: show data graphically to reveal patterns.

Frequently asked questions

What is divide and conquer? Divide and conquer is a method that solves a problem by repeatedly breaking it into smaller sub-problems of the same type until they are trivial, then combining the results. Binary search and merge sort are examples, because each repeatedly splits the problem and combines or narrows the results.

Why is quicksort a divide-and-conquer algorithm? Quicksort is divide and conquer because it partitions the list around a pivot into smaller sub-lists and then recursively sorts each sub-list, before the sorted parts form the whole. It repeatedly divides the problem into the same type of smaller problem.

What is backtracking? Backtracking is a method that explores possible solutions step by step and undoes the most recent choice when it leads to a dead end, then tries a different option. It is used for problems like navigating a maze or solving a Sudoku, searching systematically rather than trying every combination blindly.

What is a heuristic? A heuristic is a rule-of-thumb approach that finds a good-enough solution quickly without guaranteeing the best one. Heuristics are used when an exact method would take too long, such as a sat-nav finding a near-optimal route fast or antivirus software flagging likely malware.

What is data mining? Data mining is searching large data sets for patterns, trends and relationships that are not immediately obvious. For example, a supermarket might mine purchase data to discover which products are frequently bought together, turning large amounts of data into useful insight.

What is the difference between pipelining and parallel processing? Pipelining overlaps the stages of a sequence, starting the next instruction before the previous one finishes, like an assembly line, which increases throughput. Parallel processing runs fully separate tasks at the same time on different processors or cores. Pipelining overlaps stages of one flow; parallel processing runs independent tasks together.