Computational methods are systematic approaches to solving problems using algorithms. The four key methods on the H446 syllabus are: divide and conquer, dynamic programming, backtracking, and greedy algorithms. Each has specific characteristics, use cases, and trade-offs.
Divide and conquer breaks a problem into smaller sub-problems of the same type, solves them recursively, then combines the results. The sub-problems are independent (no overlap).
Three steps: Divide (split the problem), Conquer (solve recursively — until base case), Combine (merge the solutions).
| Example algorithm | How it uses divide and conquer |
|---|---|
| Merge Sort | Divide array in half, sort each half, merge the two sorted halves |
| Binary Search | Divide search space in half at each step; search the correct half |
| Quick Sort | Partition around a pivot; sort left/right partitions recursively |
Divide and conquer algorithms often achieve O(n log n) time — the log n comes from halving the problem at each level (log n levels), with O(n) work per level. Binary search is O(log n) — no combining needed.
Dynamic programming solves problems with overlapping subproblems — it stores the results of subproblems to avoid recomputing them. Two key properties: optimal substructure (optimal solution built from optimal sub-solutions) and overlapping subproblems.
# Fibonacci WITHOUT DP — exponential time O(2^n)
def fib_slow(n):
if n <= 1: return n
return fib_slow(n-1) + fib_slow(n-2) # Recomputes same values!
# Fibonacci WITH memoisation — O(n) time
memo = {}
def fib_memo(n):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
# Fibonacci WITH tabulation — O(n) time, O(n) space
def fib_tab(n):
if n <= 1: return n
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
Backtracking is a brute-force exploration with pruning. It builds a solution incrementally, and abandons (backtracks) a partial solution as soon as it determines the solution cannot be completed. Used when the search space is large but many paths can be eliminated early.
Examples: solving a maze (mark visited cells; backtrack at dead-ends), Sudoku solver (try digit 1–9 in empty cell; backtrack if contradiction), N-Queens problem (place queens on chessboard without attacking each other).
Backtracking is more efficient than exhaustive brute force because it prunes the search tree — it never explores paths that are already invalid. However, worst-case complexity is still exponential in the worst case for NP-complete problems.
A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum. It never revisits past choices. Greedy algorithms are fast but do not always find the globally optimal solution.
| Algorithm | Greedy choice | Optimal? |
|---|---|---|
| Dijkstra's shortest path | Always visit the unvisited node with smallest tentative distance | Yes (non-negative weights) |
| Prim's / Kruskal's MST | Always pick the cheapest edge that doesn't form a cycle | Yes |
| Coin change (standard denominations) | Always pick the largest coin that fits | Yes for UK coins; no for arbitrary denominations |
| Activity selection | Always pick the activity with earliest finish time | Yes |
A decidable problem is one for which an algorithm always terminates with a correct yes/no answer. An undecidable problem has no algorithm that can always correctly determine yes/no in finite time.
The classic undecidable problem is the Halting Problem (Turing, 1936): given any program and input, does it halt? It is mathematically impossible to write a general algorithm that correctly answers this for all programs. Turing proved this using proof by contradiction (assuming a halting detector exists leads to a logical paradox).
| Tractable | Intractable | |
|---|---|---|
| Definition | Solvable in polynomial time O(nᵏ) for some k | No known polynomial-time algorithm exists (worst-case exponential or worse) |
| Practical? | Yes — feasible for large inputs | Only feasible for small inputs |
| Examples | Sorting (O(n log n)), BFS/DFS (O(V+E)), shortest path | Travelling Salesman, satisfiability (SAT), graph colouring |
Problems in class P can be solved in polynomial time. Problems in class NP can be verified in polynomial time (given a solution, we can check it quickly) but no polynomial-time solution algorithm is known. The question "Does P = NP?" is the greatest unsolved problem in computer science. Most computer scientists believe P ≠ NP but this is unproven. NP-complete problems are the hardest in NP — if any NP-complete problem is solved in polynomial time, ALL NP problems can be.
A computable problem has an algorithm that will always produce the correct answer (even if it's slow). A non-computable problem has no algorithm — the Halting Problem is an example of a non-computable problem.
8 questions · 24 marks · instantly marked
| Term | Definition |
|---|