Problem-solving techniques and trace tables

Brute force and divide and conquer

• Brute force (exhaustive search): try every possible solution and pick the one that works or is best. Simple and guaranteed to find the answer, but the number of possibilities often grows exponentially: a 4-digit PIN has 10⁴ = 10 000 possibilities; checking every route through 20 cities is hopeless.
• Divide and conquer: split a problem into smaller sub-problems of the same kind, solve them (often recursively), then combine the results. Examples: binary search, merge sort, quick sort. Usually gives O(log n) or O(n log n) algorithms.

Greedy and heuristics

• Greedy: at each step take the choice that looks best right now, never reconsidering. Fast and simple. Gives the optimum for some problems (UK coin change, Dijkstra's algorithm choosing the closest vertex) but not all: with coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1 (three coins) instead of 3 + 3 (two).
• Heuristic: a rule of thumb or educated guess that finds a good enough solution quickly when an exact one would take too long (intractable problems). It does not guarantee the best answer. A heuristic can give a solution in polynomial time to a problem whose exact solution would take exponential time, often by relaxing the problem (ignoring some constraints) to get an approximate answer. Examples: A* uses a distance estimate; 'nearest neighbour' for delivery routes; antivirus heuristics.

Backtracking and recursion

• Backtracking: build a solution step by step; as soon as a partial solution cannot work, undo the last step and try the next option. Used for mazes, Sudoku, the eight queens puzzle. It prunes whole branches that brute force would explore.
• Recursion: a subroutine that calls itself on a smaller version of the problem, with a base case that stops it. Each call is stored on the call stack; too many calls cause a stack overflow.

def fact(n):
    if n <= 1:          # base case
        return 1
    return n * fact(n - 1)

Trace tables

A trace table records the value of each variable (and any output) as an algorithm runs, one row per change. It is used to find logic errors and to work out what an algorithm does.

total = 0
for i in range(1, 5):
    if i % 2 == 0:
        total = total + i
print(total)

Worked example

Use the greedy method to make 88p from UK coins (50, 20, 10, 5, 2, 1).

1. Take the largest coin that fits each time: 50 (38 left), 20 (18 left), 10 (8 left), 5 (3 left), 2 (1 left), 1 (0 left).

Answer: 50 + 20 + 10 + 5 + 2 + 1: 6 coins

Check yourself

1. Which algorithm is an example of divide and conquer?
   • Merge sort
   • Linear search
   • Bubble sort
   • Greedy coin change
   Show answer

   Merge sort. Merge sort splits the list, sorts the halves and merges them.

2. Using the greedy method with UK coins (50, 20, 10, 5, 2, 1), how many coins are needed for 67p?
   Show answer

   4. 50 + 10 + 5 + 2.

3. With coins of 1, 3 and 4 only, how many coins does the greedy method use to make 6?
   Show answer

   3. 4 + 1 + 1 = three coins (the optimum is 3 + 3, two coins).

4. A brute force attack tries every 3-character code made of the letters A to Z. How many codes are there?
   Show answer

   17576. 26 x 26 x 26 = 17 576.

5. Using the recursive fact function, what is fact(5)?
   Show answer

   120. 5 x 4 x 3 x 2 x 1 = 120.

6. Which technique gives a good, but not necessarily optimal, answer quickly to a problem that is too slow to solve exactly?
   • Brute force
   • Recursion without a base case
   • A trace table
   • A heuristic
   Show answer

   A heuristic. Heuristics trade guaranteed optimality for speed on intractable problems.

7. What does backtracking do when a partial solution breaks the rules?
   • Starts again from the very beginning with random choices
   • Undoes the most recent choice and tries the next option
   • Accepts the solution anyway
   • Sorts the data first
   Show answer

   Undoes the most recent choice and tries the next option. Abandoning dead ends early saves time.

8. total = 0; for i in range(1, 6): if i % 2 == 1: total = total + i. What is total at the end?
   Show answer

   9. Odd values 1, 3, 5 are added: 9.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.