2.2.2 Computational Methods

Question 1

Computable problems

Answer 1

• can be represented by an Algorithm
• solved within a finite timescale
• solved at a reasonable cost

Question 2

Problem recognition

Answer 2

• identifying there is a problem to be solved/ what the problem is [1]
• stakeholders state what they require from the solution
• information is used to clearly define the problem and system requirements
• problem may be defined by considering :
• strengths and weaknesses of current solution
• inputs, outputs, stored data and volume of data

Question 3

Problem decomposition

Answer 3

• problems are broken down into smaller problems until each sub problem can be represented as a self contained subroutine
• has the same benefits as modular programming

Question 4

Use of divide and conquer

Answer 4

• divide and conquer splits a big problem into smaller parts [1]
• repeatedly divides the problem into smaller sub problems halving the size of the problem with every iteration (divide) [1]
• each subproblem is solved, often recursively (conquer)
• solutions to the sub problems are then recombined (merge)
• used in quick sort, merge sort and binary search

Question 5

Problem solving strategies

Answer 5

• backtracking
• data mining
• heuristics
• performance modelling
• pipelining
• visualisation

Question 6

Backtracking

Answer 6

• an approach to finding a solution that explores a possibility until it is no longer deemed feasible.
• After finding a solution /
  failing to find a solution go back to an earlier step to test an alternative
• is used in DFS

Question 7

Data mining

Answer 7

• involves searching through unconnected data [1]
• used to identify patterns or outliers in large sets of data collected from a variety of sources [1]
• may include pattern matching algorithms [1]
• spots trends or correlations between data which are not immediately obvious [1]
• insights from data mining can aid predictions about the future [1]
• useful tool in assisting business and marketing decisions [1]

Question 8

Heuristics

Answer 8

• non optimal, rule of thumb approach to problem solving [1]
• which is used when it is unfeasible to analyse all eventualities [1]
• provides a good enough solution/result although it is not 100% reliable or accurate [1]
• used in A* , machine learning etc

Question 9

Performance modelling

Answer 9

• when the behaviour of something is tested or simulated before it is used in the real world
• to identify potential bottlenecks and areas of improvement
• can be used for evaluating and predicting the performance characteristics of a software system

Question 10

Pipelining

Answer 10

• carrying out instructions concurrently [1]
• the output of one process is usually an input of the next [1]

Question 11

Visualisation

Answer 11

• presents data in way that’s easier to understand [1]
• makes it possible to identify trends that were not otherwise obvious [1]
• eg. Use of graphs, trees, charts etc

Question 12

Example of backtracking in DFS

Answer 12

• when a node doesn’t have any nodes to visit
• the algorithm goes back to the previous visited node
• the check for further nodes to visit