2.2.2 Computational methods

What is meant by a computable problem?

• A problem that can be solved using an algorithm

• Bees

• A problem solved by a computer

• A problem that cannot be solved

Give three limiting factors to computable problems

• Processing power
• Processor speed
• Computer memory
• SSD size

State one factor which might be considered during the Problem Definition phase

• Strengths and weaknesses of current solution
• Previous systems
• Problem decomposition
• Develop sections in parallel

What is the name given to the process in which problems are continually broken down until each subproblem can be represented as a subroutine?

• Problem decomposition
• Problem Definition
• Divide and Conquer
• Abstraction

State two purposes of problem decomposition

• Identify sections which can make use of pre-coded modules or libraries
• Simplify project management
• Strengths and weaknesses of current solution
• Develop sections in parallel

State two purposes of problem decomposition

• Develop sections in parallel
• Simplify testing and maintenance
• Backtracking
• Data mining

Describe how the Divide and Conquer technique works

• The problem size is halved with every iteration. Each individual subproblem is then solved recursively. The solutions to the subproblems are then recombined o<br />form the final solution to the problem.
• A computational technique in which excessive details are removed to simplify a problem
• Identify sections which can make use of pre-coded modules or libraries
• The backtracking algorithm works by methodically visiting each path and building a solution based on the paths found to be correct. If a path is found to be invalid at any point, it backtracks to the previous stage and visits an alternate path.

Give two applications of divide and conquer

• Merge sort
• Binary search
• Dijkstra's
• A-Star

Which programming construct do many problems solved using Divide and Conquer use?

• Recursion
• Backtracking
• Pipelining
• Data mining

What is representational abstraction?

• A computational technique in which excessive details are removed to simplify a problem
• Identify sections which can make use of pre-coded modules or libraries
• The problem size is halved with every iteration. Each individual subproblem is then solved recursively. The solutions to the subproblems are then recombined to form the final solution to the problem.
• The backtracking algorithm works by methodically visiting each path and building a solution based on the paths found to be correct. If a path is found to be<br />invalid at any point, it backtracks to the previous stage and visits an alternate path.