AQA 7517 4.4.4.5: Classification of algorithmic problems
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
Some problems have an algorithm that solves them, but the algorithm is so slow that no computer that could ever be built would finish in time. This lesson is about that first limit: problems we can solve in principle but not in practice. Module A5 gave you Big O notation for comparing algorithms; here it becomes the line between what is practical and what is not.
- Two things limit computation
- How fast things grow
- Tractable and intractable
- The travelling robot
- Heuristics
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A6.7 Limits of computation: tractable and intractable problems Theory of computation
How complexity and hardware limit computation, tractable and intractable problems, and a heuristic route for the robot. - A6.10 Project: the mission robot Theory of computation
Validate a mission with a regular expression, carry it out with a Mealy machine, and report with sets.
Try it on a robot
The task from A6.7 Limits of computation: tractable and intractable problems, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.4.5 and is not endorsed by the board.