2.2.2 Computational Methods

• Problem decomposition

  • Once problem clearly defined, it is continually broken down into smaller problems
  • continues until each subproblem can be represented as a self-contained subroutine
  • aims to reduce the complexity by splitting it up into smaller sections which are more easy to understand
  • makes coding easier to manage
• Divide and conquer

  • strategy can be broken down into three parts: divide, conquer and merge
  • ‘Divide’ involves halving the size of the problem with every iteration
  • Each individual subproblem is solved in the ‘Conquer’ stage, often recursively
  • The solutions to the subproblems are then recombined during the ‘Merge’ stage to form the final solution
• Divide and conquer

  
• Binary Search

  • use of divide and conquer
• Divide and Conquer

  • simplifies very complex problems
  • the time complexity of algorithms that use divide and conquer is of the order O(logn)
  • use of recursion: risk of stack overflow and difficult to trace
• Representational abstraction

  • a powerful technique that is key to solving a problem computationally.
  • This is when excessive details are removed to simplify a problem.
• Problem solving strategies

  • Backtracking
  • Data Mining
  • Heuristics
  • Pipelining
  • Performance modelling
  • Visualisation
• Backtracking

  • e.g Depth-first graph traversals
  • Process of incrementally building towards a solution
  • if a path is found to be invalid, the algorithm backtracks to the previous stage and visits an alternate path
• Heuristics

  • used to provide an estimated solution for problems which take unreasonably long time to be found
  • 'rule-of-thumb' approach to problem-solving used to find an approximate solution to a problem
  • Educated guess approach to analyse all eventualities
  • e.g Travelling Salesman Problem and A* algorithm
• Data Mining

  • technique used to identify patterns or outliers in large sets of data (BigData)
  • used in software designed to spot trends or identify correlations between data which are not immediately obvious
• Advantages of Data Mining

  • Useful for Business and Marketing: can be used to make predictions about the future based on previous trends
  • reveals insights about people’s shopping habits and preferences based on their personal information
• Disadvantages of Data Mining

  • involves the handling of personal data, it is crucial that it is dealt with in accordance with the Data Protection Act 2018
  • Inaccurate info can produce false results
  • Customers may not want personal info to be collected
• Visualisation

  Data can be presented in a way that is easier for us to understand

  • makes it possible to identify trends that were not otherwise obvious
  • data may be represented as graphs, trees, charts and tables
• 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
  • resembles a production line
• Performance modelling

  eliminates the need for true performance testing by providing mathematical methods to test a variety of loads on different operating systems
• Problem Recognition

  • once a problem is determined computable, the next stage is to clearly identify what the problem actually is
  • stakeholders state what they require from the finished production - this info is used to clearly define the problem and the system requirements
  • requirements may be defined by:
  • analysing strengths and weaknesses with the current way the problem is being solved
  • considering types of data involved inputs, outputs, stored data and amount of data
• First Stage of Problem Solving

  • Identifying whether or not a problem can be solved using computational methods
  • A problem that can be solved using an algorithm is computable
  • Problems can only be called computable if they can be solved within a finite, realistic amount of time