Computational Methods and Problem Classification | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Classify problems as tractable or intractable based on computational complexity

Define P, NP, and NP-hard problem classes and understand P vs NP

Explain heuristic approaches for NP problems

Describe computational methods: backtracking, dynamic programming, greedy algorithms, divide and conquer, and data mining

Tractability

Tractable vs Intractable Problems

Tractable

A problem is tractable if it can be solved in polynomial time — O(nᵏ) for some constant k. As n grows, running time grows at a manageable rate. Practical to solve on real hardware. Examples: sorting (O(n log n)), binary search (O(log n)).

Intractable

A problem is intractable if no known polynomial-time algorithm exists. Running time grows exponentially or factorially — O(2ⁿ), O(n!). Impractical for large n. Example: Travelling Salesman Problem (brute force is O(n!)).

For n=20: O(n²) = 400 steps; O(2ⁿ) = 1,048,576 steps; O(n!) = 2,432,902,008,176,640,000 steps. Exponential and factorial growth quickly becomes computationally impossible.

P vs NP

Problem Classes: P, NP, NP-Hard

P (Polynomial time): problems that can be solved in polynomial time. E.g. sorting, shortest path (Dijkstra's). These are tractable problems.

NP (Non-deterministic Polynomial): problems where a proposed solution can be verified in polynomial time, but finding the solution may not be possible in polynomial time. E.g. Sudoku verification vs solving.

NP-hard: at least as hard as the hardest problems in NP. The Travelling Salesman Problem is NP-hard. Includes problems that may not even be in NP.

P vs NP question: does P = NP? If so, every problem whose solution can be verified quickly could also be solved quickly. This is the most famous unsolved problem in computer science. Almost all experts believe P ≠ NP.

Heuristics

Heuristic Approaches

For intractable problems, we cannot find an optimal solution in reasonable time. Heuristics find a good enough solution (but not guaranteed optimal) in a reasonable time. They trade accuracy for speed.

Example — Nearest Neighbour for TSP: start at any city; repeatedly visit the nearest unvisited city; return to start. Fast (O(n²)) but does not guarantee the shortest route — typically within 20–25% of optimal.

Heuristics are widely used in real life: route planning (Google Maps uses approximations for complex multi-stop routes), game AI (chess engines evaluate positions heuristically), spam filters (bayesian approximations).

Computational Methods

Key Computational Methods

Backtracking

Explores all possibilities by building a solution incrementally and abandoning a path (backtracking) as soon as it becomes invalid. Used for: Sudoku, constraint satisfaction, maze solving. Systematically exhausts the solution space.

Dynamic Programming

Breaks a problem into overlapping sub-problems; solves each once and stores results (memoisation). Avoids recomputation. Used for: Fibonacci, shortest paths (Bellman-Ford), longest common subsequence.

Divide and Conquer

Split the problem into independent sub-problems; solve recursively; combine results. Sub-problems do not overlap (unlike DP). Examples: merge sort, binary search, quicksort.

Greedy Algorithm

Always makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. Fast and simple but not always correct. Examples: Dijkstra's, Prim's, Huffman coding.

Data Mining

Data mining is the process of discovering patterns, correlations, anomalies and insights in large datasets. It uses statistical, machine learning and AI techniques to extract knowledge from raw data.

Uses include: market basket analysis (products bought together), fraud detection (unusual transaction patterns), medical diagnosis (identifying disease patterns), recommendation systems (Netflix, Amazon).

OCR H446 includes data mining as a computational method because it involves applying algorithms to solve complex real-world problems where patterns cannot be identified manually due to the scale of data.

Exam Practice

OCR H446 Style · 5 marks

A logistics company needs to plan delivery routes for its fleet of vehicles. The optimal route for n stops requires evaluating n! possible routes. Explain why this problem is considered intractable for large n, and describe a computational method the company could use to find a good (but not necessarily optimal) solution.

[5 marks]

Intractable: The problem grows factorially — O(n!). For n=20 stops, this is over 2.4 × 10¹⁸ possible routes. Even at 10⁹ evaluations per second, this would take billions of years. No polynomial-time algorithm exists for finding the optimal solution (TSP is NP-hard), making it intractable for large n.

Heuristic approach: Use a nearest-neighbour heuristic — start at the depot and repeatedly travel to the nearest unvisited delivery location, then return to the depot. This runs in O(n²) time and produces a good route, though not guaranteed to be optimal. Alternatively, a greedy algorithm could be applied to build the route step by step.

Common Mistakes

Don't Lose Marks

Saying NP means "Not Polynomial" — NP stands for "Non-deterministic Polynomial". It means solutions can be verified in polynomial time, not that no polynomial algorithm exists. P is a subset of NP. "NP means impossible to solve quickly" is imprecise and penalised.

Confusing dynamic programming with divide and conquer — both split problems into sub-problems, but in DP the sub-problems overlap (the same sub-problem is solved multiple times without DP), while in divide and conquer the sub-problems are independent. DP stores results to avoid recomputation.

Saying heuristics always find the optimal solution — by definition, heuristics sacrifice optimality for speed. They find a good enough solution. In the exam, always say "a good solution, not necessarily the optimal/shortest/cheapest" when describing heuristics.

Computational Methods& ProblemClassification