2.2.2 Computational Methods
2.2.2(a) Features That Make a Problem Solvable by Computational Methods
Definition
Not all problems are solvable using computational methods. A problem must be computable, meaning it can be resolved using a well-defined algorithm within a finite and practical amount of time.
Characteristics of Computable Problems
Key Point
| Computability feature | Why it matters |
|---|---|
| Clear inputs/outputs | Problem can be formally specified |
| Well-defined steps | Algorithm can be implemented consistently |
| Finite execution | Solution terminates in practice |
| Deterministic outcome | Same input gives predictable result |
| Practical limitation | Typical constraint |
| --- | --- |
| Processing power | CPU limits on large/complex tasks |
| Memory | Insufficient RAM/storage for data/structures |
| Time | Runtime too long to be useful |
| Data availability | Missing/poor-quality input data |
2.2.2(b) Problem Recognition
Definition
Problem recognition involves clearly defining a problem by understanding stakeholder needs and translating them into specific system requirements.
Key Aspects of Problem Recognition
Key Point
| Problem-recognition activity | Key questions |
|---|---|
| Analyse current solutions | What works now, what fails, what can improve? |
| Identify data requirements | What inputs/outputs/storage/scale are needed? |
| Stakeholder involvement | Are we solving the real user/business problem? |
2.2.2(c) Problem Decomposition
Definition
Problem decomposition is breaking down a complex problem into smaller, more manageable subproblems. This continues until each subproblem can be addressed independently.
Key Point
| Decomposition benefit | Practical effect |
|---|---|
| Reduced complexity | Smaller subproblems are easier to reason about |
| Parallel development | Different team members can build different modules |
| Reuse | Shared sub-solutions reused across system |
| Easier testing/debugging | Faults isolated within smaller units |
| Team collaboration | Clear component ownership |
| Project scalability | Large systems become manageable |
2.2.2(d) Use of Divide and Conquer
Definition
Divide and conquer is a strategy that breaks a problem into smaller parts, solves each part, then merges solutions. The three steps are: divide, conquer, and merge.
Worked Example
Divide and Conquer: Binary Search
Efficiency: Binary search halves the search space each time - O(log n) complexity.
Other examples: Quicksort, Mergesort
text
function binarySearch(array, target, low, high):
// Base case: element not found
if low > high then
return -1
end if
// DIVIDE: Find middle
mid = (low + high) DIV 2
// CONQUER: Check middle element
if array[mid] == target then
return mid
elseif array[mid] > target then
// Search left half
return binarySearch(array, target, low, mid - 1)
else
// Search right half
return binarySearch(array, target, mid + 1, high)
end if
end function
Efficiency: Binary search halves the search space each time - O(log n) complexity.
Other examples: Quicksort, Mergesort
2.2.2(e) Use of Abstraction
Definition
Abstraction removes unnecessary details to simplify a problem. By focusing on core elements, complex problems become manageable, often revealing similarities to previously solved problems.
Key Point
| Abstraction aspect | What it gives you |
|---|---|
| Generalisation | Recognise shared patterns and reuse solutions |
| Levels of abstraction | Separate concerns while hiding low-level detail |
| Reduced complexity | Focus only on relevant detail at each stage |
| Better maintainability/teamwork | Cleaner interfaces between modules |
2.2.2(f) Solving Problems Using Various Techniques
Backtracking
Definition
Backtracking systematically explores possible solutions by building them incrementally. If a path fails, the algorithm backtracks to explore alternatives. Useful for puzzles and decision trees.
Worked Example
Backtracking Example: Maze Solving
When dead end reached: Backtrack to previous decision point and try alternative path.
text
function solveMaze(maze, position):
if position is exit then
return True
end if
if position is valid then
mark position as visited
// Try all directions
if solveMaze(maze, north) then return True
if solveMaze(maze, south) then return True
if solveMaze(maze, east) then return True
if solveMaze(maze, west) then return True
// BACKTRACK: unmark and return false
unmark position
end if
return False
end function
When dead end reached: Backtrack to previous decision point and try alternative path.
Data Mining
Definition
Data mining involves analysing large datasets to discover patterns, correlations, or anomalies. Used for predictive analysis, trend spotting, and decision-making.
Worked Example
Data Mining Example: Supermarket Sales
| Element | Detail |
|---|---|
| Dataset | 3+ petabytes of sales/customer data |
| Pattern discovered | Hurricane warnings correlate with increased fruit pie sales |
| Action taken | Move fruit pies to high-visibility locations during warnings |
| Business outcome | Significant sales increase |
| Why computation was needed | Scale too large for manual analysis; pattern not obvious |
Heuristics
Definition
Heuristics offer practical approaches to problem-solving by finding approximate solutions when exact solutions are impractical. They provide quick, often "good enough" results.
Worked Example
Heuristic Example: Travelling Salesman Problem
Problem: Find shortest route visiting all cities.
Exact solution: Check all possible routes - O(n!) complexity.
Heuristic (Nearest Neighbour):
Result: Good solution quickly, though not guaranteed to be optimal.
Problem: Find shortest route visiting all cities.
Exact solution: Check all possible routes - O(n!) complexity.
Heuristic (Nearest Neighbour):
text
function nearestNeighbourTSP(cities):
current = startingCity
tour = [current]
unvisited = all other cities
while unvisited not empty:
nearest = findClosest(current, unvisited)
add nearest to tour
remove nearest from unvisited
current = nearest
end while
return tour
end function
Result: Good solution quickly, though not guaranteed to be optimal.
Performance Modelling
Definition
Performance modelling uses mathematical methods to predict system behaviour under various conditions without extensive real-world testing. Critical for safety-critical systems.
Pipelining
Definition
Pipelining divides a process into distinct stages, with each stage executing in parallel. Accelerates delivery by allowing multiple tasks to proceed simultaneously.
Worked Example
Pipelining Example: Car Assembly
Without pipeline: complete one full car before starting next.
With pipeline: multiple cars progress concurrently through different stages.
| Stage | Task |
|---|---|
| 1 | Install engine |
| 2 | Add wheels |
| 3 | Paint body |
| 4 | Install interior |
| Time step | Pipeline state |
| --- | --- |
| Time 1 | Car 1 at Stage 1 |
| Time 2 | Car 1 at Stage 2, Car 2 at Stage 1 |
| Time 3 | Car 1 at Stage 3, Car 2 at Stage 2, Car 3 at Stage 1 |
With pipeline: multiple cars progress concurrently through different stages.
Visualisation
Definition
Visualisation translates data into graphical formats (charts, graphs, trees) making complex data easier to interpret. Helps identify trends, outliers, and patterns.
Key Point
| Visualisation benefit | Impact |
|---|---|
| Accessibility | Complex data becomes easier to interpret |
| Pattern detection | Trends/outliers visible at a glance |
| Decision support | Faster, evidence-based decisions |
| Communication | Findings clearer for non-technical audiences |
| Monitoring | Dashboards support real-time observation |
Exam Tip
Exam Tips for Computational Methods:
ā¢ Know what makes a problem computable
ā¢ Understand problem recognition and stakeholder involvement
ā¢ Be able to explain decomposition benefits
ā¢ Know divide and conquer: binary search, quicksort, mergesort
ā¢ Understand abstraction's role in simplifying problems
ā¢ Know various techniques: backtracking, data mining, heuristics, pipelining
ā¢ Give specific examples for each technique
ā¢ Understand when each technique is appropriate
ā¢ Know what makes a problem computable
ā¢ Understand problem recognition and stakeholder involvement
ā¢ Be able to explain decomposition benefits
ā¢ Know divide and conquer: binary search, quicksort, mergesort
ā¢ Understand abstraction's role in simplifying problems
ā¢ Know various techniques: backtracking, data mining, heuristics, pipelining
ā¢ Give specific examples for each technique
ā¢ Understand when each technique is appropriate