2. 2. 2 Computational Methods

Question 1

Features that make a problem solvable by computational methods

Answer 1

• A problem that can be solved using an algorithm is computable
• Can be classified as computable if it can be solved within a finite, realistic amount of time
• Typically consists of inputs, outputs and calculations
• Some problems may be computable but are impractical to solve due to the number of resources or length of time it requires to complete
• Problems that can be solved computationally are constrained by factors such as processing power, speed, memory, funding
• Developing technology allows us to solve more problems computationally than ever before

Question 2

Problem recognition

Answer 2

• Once problem determined to be computable, next stage is to clearly identify what the problem is
• Stakeholders state what they need from the finished product, this info used to clearly define the problem and the system requirements
• Analyse of strengths and weaknesses with current ways this problem is being solved may be performed
• Types of data like inputs, outputs, stored data and the amount of data is considered

Question 3

Problem decomposition

Answer 3

• Once problem clearly defined, it is continually broken down into smaller problems
• Continues till each subproblem can be represented as a self-contained subroutine, this is problem decomposition
• Aims to reduce complexity of problem, split problem into smaller sections, easier to understand
• Identifying subproblems may allow programmers to spot that some sections can be implemented using pre-coded modules or libraries
• This saves time that would have been spent coding and testing
• Decomp makes project easier to manage, different software development teams assigned to different sections of code according to specialisms
• Sections individually designed, developed and tested before being combined to produce final program
• Decomp allows development in parallel, makes it possible to deliver projects faster
• Makes debugging simpler and less-time consuming, easier to identify, locate and correct errors in individual modules (A lot better compared to debugging entire application then trying to find error)

Question 4

Divide and conquer

Answer 4

• Problem-solving technique, can be broken down into three parts, divide, conquer and merge
• “Divide”, halve size of problem with every iteration
• Individual subproblems solved in “Conquer” stage, often recursively
• Solutions to subproblems then recombined in “Merge” stage, forms final solution to the problem
• One common use of this technique is in binary search
• Divide and conquer is also applied to problem solving in quick sort and merge sort
• Principle of divide conquer also used in problems that can be reduced by less than half every iteration, this technique sometimes referred to as “Decrease and Conquer”
• Advantage of divide and conquer, greatly simplifies very complex problems, problem size halved every iteration
• As the size of the problem increases time taken to solve does not grow significantly, time complexity of algorithms using this technique is 0(log n)
• Disadvantage, due to it using mostly recursion, prone to stack overflow which would cause the program to crash and large programs are very difficult to trace

Question 5

Use of abstraction

Answer 5

• Representational abstraction is a key technique to solving a problem computationally
• Excessive details removed to simplify a problem, allows programmers to focus on core aspects required of the solution instead of worrying about unnecessary details
• Levels of abstraction allows large, complex projects to be split into simpler component parts, individual components dealt with by different teams
• Do not interfere with each other, makes projects more manageable
• Abstraction by generalisation can be used to group together different sections of problem with similar underlying functionality, allows segments of code to be reused, saves time
• Abstract thinking needed to represent real-world entities with computational elements like tables and variables

Question 6

Problem solving strategies

Answer 6

Backtracking, Data mining, Heuristics, Performance modelling, Pipelining and Visualisation

Question 7

Backtracking

Answer 7

• Problem-solving technique implemented using algorithms, often recursively
• Works by methodically visiting each path, building a solution based on paths found to be correct
• If path found to be invalid at any point, algorithm backtracks to previous stage visits alternate path
• Depth-first graph traversal is an example of backtracking
• Can be visualised as a maze, maze has many routes, only few lead to correct destination
• Maze solved by visiting each path, if path leads to dead end, return back to most recent stage where there is a selection of paths to choose from

Question 8

Data mining

Answer 8

• Used to identify patterns or outliers in large sets of data (big data like databases)
• Big data typically collected from variety of sources
• Data mining used in software designed to spot trends or identify correlations between data that is not immediately obvious
• Insights from this can be used to make predictions about the future based on previous trends, makes data mining useful tool in assisting business and marketing decisions
• May for example show what products are bought when, this info can help shops prepare stock in advance
• Also used to reveal peoples shopping habits and preferences based on their personal info, insights used to inform marketing techniques
• Data mining involves handling of personal data, crucial that is dealt with in accordance with GDPR

Question 9

Heuristics

Answer 9

• Non-optimal, “rule-of-thumb” approach to problem-solving, used to find approximate solution to problem when standard solution unreasonably time-consuming or resource-intensive to find
• Solution found not perfectly accurate or complete, focus on finding quick solution that is “good enough”, heuristics provides shortcut to exactly that
• Used to provide estimated solution for intractable problems like the A* algorithm
• Also used in machine learning and language recognition

Question 10

Performance modelling

Answer 10

• Eliminates need for true performance testing, provides mathematical methods to test variety of loads on different OSs
• Provides cheaper, less time-consuming and safer method of testing applications
• Useful for safety-critical computer systems like those in airplanes and hospitals where it is not safe to do a real trial run before system can be implemented
• Results of performance modelling helps companies judge capabilities of the system, how well it will cope in different environments, assess if its safe to implement

Question 11

Pipelining

Answer 11

• Process that allows projects to be delivered faster, modules divided into individual tasks, with different tasks being developed in parallel
• Output of one process in pipelining becomes input of another traditionally, resembles a production line

Question 12

Visualisation

Answer 12

• Data can be presented in a way that is easier for us to understand using this technique
• Makes it possible to identify trends that may not have been obvious, particularly amongst statistical data
• Data may be represented as graphs, trees, charts and tables
• This technique used by businesses to pick up on patterns which can be used to inform business decisions