Computational Methods

Introduction

How do you know if a problem is solvable? Think about your NEA and the steps that you went through to define the problem. It must:

• It must be amenable to a computational solution. Think about the processing power required to perform calculations.
• Consider the data - is there enough memory capacity to store it?
• Can the main elements be deduced by abstraction?
• Can the problem be broken down using decomposition?

Be clearly defined — this means that you should be able to identify the existing solution, the requirements, and the potential obstacles and limitations.

Problem Recognition

You need to recognise the problem exists and then define it. You would need to consider the required data and any variables that might alter the current state of the problem. Are there existing solutions that you need to consider?

Problem Decomposition

This involves repeatedly breaking a problem down into sub problems.

Divide and Conquer

This is the process of repeatedly halving the problem to work with a smaller set of data. A very obvious example of this is binary search. Other examples include filtering data in a database.

Abstraction

This is the technique of selecting the important details and ignoring unimportant data. A* Algorithm focuses on nodes and weighted edges to work out the best path, but ignores other features such as geography. Find out more here.

Backtracking

This is also a process of discarding by going back along a path already travelled. For example searching through a binary tree.

Data Mining

This is the process of analysing vast amounts of data to find patterns. Data mining is used to predict weather patterns, in medical research, economics, the stock market.

Pipelining

This is a technique which can be applied to sub tasks which are processed in a sequence one after the other. This means that each subtask is executed by a different process. Find out more here.

Visualisation

This is the process of using diagrams, flowcharts, images etc. to illustrate and clarify the problem being solved. Trees and Graphs are a great example of this. We often use abstraction to focus on the required details when visualising a problem.

Heuristics

Heuristics involves using expertise to make a best guess where the processing power and resources outweighs the need for higher accuracy. Heuristics are used in the A* path finding algorithm. Using heuristics can make a problem you thought was unsolvable solvable.