A-level Computer Science revision · Data structures and algorithms

Problem-solving methods

The idea

Computational methods include problem recognition, decomposition, divide and conquer, abstraction, backtracking (trying options and undoing when a path fails, as in maze solving), heuristics (rules of thumb that give good-enough solutions quickly), data mining, performance modelling, pipelining and visualisation.

  1. Backtracking: explore, and step back on failure.
  2. Heuristics: trade accuracy for speed.
  3. Choose the method for the problem.

Watch out A heuristic may not give the optimal solution; it gives a good one quickly.

See it worked

Worked example

Why use a heuristic for the travelling salesperson problem?

  1. The exact solution is intractable for many cities.
  2. A heuristic finds a good route quickly.
  3. It may not be the shortest.

Answer Exact methods are too slow; a heuristic gives a good route quickly

Your turn

Question 11 mark

Which method solves a maze by trying a path and returning to the last junction when stuck?

Choose one
Question 21 mark

What is a heuristic?

Choose one
Question 32 marks

Explain what makes a problem intractable.

Write your answer, then see a model answer
  1. Define it.
  2. Link to complexity.

Answer It can be solved in theory, but the time needed grows so fast (for example exponentially) that it cannot be solved for large inputs in a reasonable time.

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms