2.2.2: computational methods

• What is meant by a computable problem?


  A problem that can be solved using an algorithm
• Give three limiting factors to computable problems

  • Processing power
  • Processor speed
  • Computer memory
  • Time
• State two factors which may be considered during the Problem Definition phase

  • Strengths and weaknesses of current solution
  • Volume/type/frequency/nature of
  • Inputs
  • outputs
  • stored data
• 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
• State two purposes of problem decomposition.

  • Identify sections which can make use of pre-coded modules or libraries
  • Save timecoding
  • Simplify project management
  • Simplify testing and maintenance
  • Faster project delivery
  • Develop sections in parallel
• 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 to form the final solution to the problem.
• Give two applications of divide and conquer

  • Merge sort
  • Binary search
  • Quick sort
• Which programming construct do many problems solved using Divide and Conquer use?

  Recursion
• What is representational abstraction?


  A computational technique in which excessive details are removed to simplify a problem
• What type of abstraction is used to group together sections of the problem based on their functionality?

  Abstraction by generalisation
• State two problem solving techniques

  • Backtracking
  • Data mining
  • Abstraction
  • Divide and conquer
  • Visualisation
  • Performance modelling
  • Pipelining
  • Visualisation
• Describe how backtracking works

  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.
• When might heuristics be used in problem-solving?

  When the standard way to solve the problem is unreasonably time-consuming or resource-intensive
• State two advantages of using performance modelling

  • Safe
  • Relatively inexpensive
  • Less time-consuming
• What is pipelining?


  A process in which tasks are developed in parallel. The output of one process in pipelining becomes the input of another, resembling a production line
• What is the name given to the technique used to identify patterns and trends in large sets of data?

  Data mining