2.2.2 Computational methods A Level OCR Computer Science

What are computational methods

Problem-solving techniques that use algorithms and mathematical models to analyse and solve complex problems efficiently using a computer.

What is divide-and-conquer

A problem-solving technique that recursively breaks a larger problem down into smaller, more manageable sub-problems of the same type until they can all be solved directly, and then combines these solutions to form the final solution.

Which common algorithms use divide-and-conquer

Merge sort, quick sort, binary search

What are the advantages and disadvantages of using divide-and-conquer

It speeds up program execution time by allowing different parts of the larger problem to be solved concurrently. It also makes efficient use of caching. It requires a lot of extra memory usage, increasing space complexity.

What is backtracking

A problem-solving technique that incrementally builds possible solutions, abandoning them if they fail and returning to the previous decision point with a valid state to try alternative solutions.

Which common algorithms use backtracking

Depth-first graph traversals, pathfinding algorithms (Djikstra and A*)

What are the advantages and disadvantages of backtracking

It explores all possible paths and so is guaranteed to find a solution to a problem if a valid one exists. Since all paths are being checked, algorithms that use this technique are often time-consuming and take up a lot of memory.

What is data mining

The process of using machine learning and statistical analysis to extract hidden trends, correlations and patterns that would not be immediately obvious to humans from large sets of data.

Why is data mining used

By helping find patterns that are not immediately obvious, it can be used to inform decision-making by making predications on future trends based on past behaviour.

What is heuristics

A problem-solving techique that makes use of experience, such as rules of thumb or educated guesses, to find an approximate solution to a problem more quickly than a perfect solution can be found, prioritising speed over accuracy.

How are heuristics used in the A* algorithm

Along with using the distance from the start node (calculated by Djikstra’s algorithm), it uses a heuristic that estimates the approximate distance of each node from the end node, allowing an efficient (though not necessarily perfect) path to be found.

Why are heuristics helpful in algorithms

They significantly reduce the space and time complexity of algorithms by eliminating the need to check every possible solution in favour of one that works well enough.

What is performance modelling

An approach to testing software that involves testing the performance and behaviour of a system under certain conditions and using mathematical models and simulations to predict, based on this, how it will behave with larger inputs/larger workloads.

What are the advantages and disadvantages of performance modelling

It allows safe testing of extreme conditions in safety-critical systems without doing physical damage to anything. It is more time and space efficient than running a test on the full load expected. However, it is heavily reliant on the accuracy of the data and mathematical models used in testing, and is not able to account for unpredictable user behaviour.

What is pipelining

The process of carrying out multiple instructions concurrently, where the output of one process feeds into the input of the next. This improves the efficiency and performance of the devices/components involved.

What is visualisation

A problem-solving technique that involves representing data, algorithms or complex systems in a format easier for humans to understand, like a graphical or visual format, making it easier for humans to analyse and break them down.

What are the advantages and disadvantages of visualisation

It makes complex problems and solutions easier for humans to understand, analyse and use, enhancing Human-Computer Interaction and communication between programmers and clients. However, visualised models are subject to differing interpretations and misinterpretation, and when models are visualised, some important technical information may be lost.