2.2.2 Computational Methods

Decomposition

Decomposition

Once a problem has been clearly defined, it is continually broken down into smaller problems.

Divide and conquer

Problem-solving technique that can be broken down into three parts: divide, conquer and merge. Divide involves halving the size of the problem in each iteration. These subproblems are solved in the conquer stage, often using recursion. The solutions are then recombined during the merge state to form the final solution

Common uses of divide and conquer

Binary search, quick sort, merge sort

Advantage of divide and conquer

The size of the problem halves with each iteration which greatly simplifies very complex problems. This means time complexity is O(log n)

Disadvantage of divide and conquer

As it uses recursion, stack overflow will cause the program to crash and large programs are very difficult to trace

Representational abstraction

Excessive details are removed to simplify a problem

Advantages of abstraction

Allows programmers to focus on the core aspects required of the solution

Allows a large, complex project and its functionality to be split up into simpler component parts

Backtracking

Methodically visiting each path and building a solution based on the paths found to be correct. Depth-first graph traversals are an example.

Data mining

Used to identify patterns or outliers in large data sets, termed big data. Used in software designed to spot trends or identify correlations between data which aren’t immediately obvious

Heuristics

A non-optimal, ‘rule-of-thumb’ approach to problem solving which are used to provide an approximate solution to a problem when the standard solution is unreasonably time consuming or resource intensive

Performance modelling

Eliminates the need for true performance testing by providing mathematical methods to test a variety of loads on different operating systems. Provides a cheaper, less time-consuming method of testing applications

Pipelining

A process that allows for projects to be delivered faster, as modules are divided into individual tasks, with different tasks being developed in parallel

Visualisation

Can be used to present data in a way that is easier for us to understand. May be represented as graphs, trees, charts and tables