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.
pseudocode
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
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 |
Key Point
| Benefits of data mining | Drawbacks of data mining |
|---|---|
| Finds patterns and trends that are not obvious, in more data than a person could analyse | Needs very large amounts of data, powerful hardware and specialist software, all of which cost money |
| Supports predictions, such as which products will sell or which users are likely to leave | A pattern shows that two things happen together, not that one causes the other |
| Decisions are based on evidence of what users actually do | Incomplete or inaccurate data gives misleading patterns |
| Can be repeated automatically as new data arrives | Personal data must be collected and used in line with data protection law, and users may object to being tracked |
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):
pseudocode
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
Key Point
| Using a heuristic | Effect |
|---|---|
| Benefit | A solution is found much sooner, because not every possibility is examined |
| Benefit | Problems that would take an impractical time to solve exactly become usable |
| Drawback | The solution is not guaranteed to be the best one |
| Drawback | A poorly chosen heuristic can give a poor answer or save no time |
| Where it suits | When a good-enough answer is needed quickly, as in the A* algorithm's estimate of the distance left to the goal, or a computer-controlled character choosing a route in a game |
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.
Worked Example
Performance Modelling Example: Ticket Website
The company finds out how well the system scales before it goes live, instead of waiting for a real sale to fail.
| Question to answer | How it is modelled |
|---|---|
| Will the site cope when 50,000 people try to buy tickets at once? | Simulate 50,000 requests arriving together and measure the response time |
| How does the response time change as demand grows? | Repeat the simulation with 1,000, 10,000 and 100,000 users and compare the results |
| Is the search algorithm fast enough for the full database? | Use its Big O complexity to predict the number of steps for the expected number of records |
Key Point
Performance modelling is used when testing the real system would be too expensive, too slow or unsafe: for example the software for an aircraft, or a system whose limits are only reached with millions of users. Its predictions are only as reliable as the model and the test data used.
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.
Worked Example
Pipelining Example: Fetch-Decode-Execute
Instructions A, B, C and D pass through three stages. The output of each stage is the input to the next.
The four instructions finish in 6 time steps. Without pipelining each instruction would complete all three stages before the next one started, taking 12 time steps.
Instructions A, B, C and D pass through three stages. The output of each stage is the input to the next.
| Time step | Fetch | Decode | Execute |
|---|---|---|---|
| 1 | A | Idle | Idle |
| 2 | B | A | Idle |
| 3 | C | B | A |
| 4 | D | C | B |
| 5 | Idle | D | C |
| 6 | Idle | Idle | D |
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