Backtracking, data mining, heuristics, performance modelling, pipelining and visualisation

Learners should apply their knowledge of: Backtracking Data mining Heuristics Performance modelling Pipelining Visualisation to solve problems

2.2.2 Computational Methods

Computational Methods — Note 6 of 6

Candidates need to understand the purpose of backtracking (for example when traversing a tree) and be able to read, trace and write code that uses it. Candidates need to understand data mining and how a program searches for and interrogates data. Candidates need to understand heuristics (for example in the A* algorithm) and explain their purpose and benefits in a scenario. Candidates need to understand the purpose of performance modelling, pipelining (where the result of one process feeds into the next) and visualisation to create a mental model of what a program will do.

What you need to know

These six computational methods are approaches for solving problems that cannot easily be solved with a simple algorithm. You need to understand each one and apply them to given scenarios.

What to know

Key terms

Exam tipCommon mistake

Backtracking: Building a solution step by step; when a step leads to a dead end, go back to the last decision point and try a different option. Used for mazes, puzzles such as Sudoku, and depth-first traversal of trees and graphs.
Data mining: Searching and analysing large data sets to discover patterns, trends and relationships that are not obvious. Used for targeted marketing, fraud detection and predicting trends; it raises privacy concerns.
Heuristic: A 'rule of thumb' approach that finds a good enough solution in a reasonable time when finding the perfect solution would take too long. For example, the A* algorithm uses a heuristic to estimate the remaining distance.
Heuristics are useful for intractable problems, such as finding the shortest route visiting many cities, where checking every possible route is impractical.
Exam tip: Questions often give a scenario and ask how one of these methods could be used. Apply it specifically, e.g. 'a heuristic could estimate the straight-line distance to the destination to decide which road to explore first'.
Performance modelling: Using mathematical models or simulations to predict how a system will behave (e.g. under heavy load) before it is built or changed, saving time and money compared with testing the real system.
Pipeliningin programming: Splitting a task into stages where the output of one stage becomes the input of the next, so different items can be at different stages at the same time.
Visualisation: Presenting data or a problem visually (e.g. graphs, charts, flowcharts, diagrams) to make patterns easier to see and to create a mental model of how a program will work.

Code examples

Backtracking: finding a path through a maze

python

def solve(maze, row, col, path):
    if not (0 <= row < len(maze) and 0 <= col < len(maze[0])):
        return False                      # outside the maze
    if maze[row][col] != 0:
        return False                      # wall (1) or already visited (2)
    path.append((row, col))
    if (row, col) == (len(maze) - 1, len(maze[0]) - 1):
        return True                       # reached the exit
    maze[row][col] = 2                    # mark as visited
    for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        if solve(maze, row + dr, col + dc, path):
            return True
    path.pop()                            # dead end: backtrack
    return False