2.2.2 Computational Methods

Question 1

What is abstraction?

Answer 1

• Separating ideas from reality
• Removing unnecessary details in order to simplify complex problems

Question 2

What is the halting problem?

Answer 2

• He proved that there are problems that exist that are not computable
• Some problems cant be solved by computers

Question 3

What were the limits of algorithms held on until later?

Answer 3

• Existing hardware
• Memory size
• Processor speed

Question 4

What are tractable problems?

Answer 4

• A tractable problem is any problem that can be solved in polynomial time or better
• The algorithm to solve the problem will run quickly enough to be practical and usefuk

Question 5

We are interested in algorithms that can solve problems …

Answer 5

• In a reasonable amount of time
• Using a reasonable amount of memory

Question 6

What are intractable problems?

Answer 6

• Any problems that can’t be solved in polynomial time or better.
• As soon as input increases - computer takes longer to solve
• Can use heuristics for intractable problems that find a “good enough” answer

Question 7

What are some features of tractable problems that make them great for computational methods?

Answer 7

• Enumeration
• Theoretical Approach
• Abstraction/ Decomposition
• Simulation and Automation

Question 8

What is Enumeration?

Answer 8

• Designing an algorithm that performs an exhaustive search and attempts all possible solutions until the correct one is found.

Question 9

What is Theoretical Approach?

Answer 9

• Putting a problem into pure theory and becomes easy o represent using mathematic equations.
• Computers are great at math’s - better to solve algorithms

Question 10

What is Simulation?

Answer 10

• Process of designing a model of a real system in an attempt to understand its behaviour

Question 11

What is automation?

Answer 11

• Building problem solving models and putting them into action
• Both simulation and automation make heavy use of abstraction and turn complex problems into 1 that can be more easily solved by algorithms.

Question 12

What are the key principles of computational methods?

Answer 12

• Decomposition
• Pattern Recognition
• Abstraction
• Calculations and storage

Question 13

What is Problem Recognition?

Answer 13

• It is the ability to “recognise/ acknowledge” that an issue exists or that a situation needs attention in an existing process/program
• Define the problem and determine what it is

Question 14

When presented with a scenario for problem recognition what are some questions to think about?

Answer 14

• Is there a problem that needs to be solved?
• If so what is the nature of the problem?
• What data do you need to acquire in order to understand the problem
• What variables are in play that could alter the current state of the problem
• What techniques should be put into consideration

Question 15

What is Problem Decomposition?

Answer 15

• Process of taking a large problem and breaking it down into several smaller problems
• Depending on size and complexity of the problem, these smaller problems can often be broken down further
• Repeat process, explore the problem until each lowest level boxes represent a single task/ action which can be put into a procedure, module, function or method.

Question 16

What is step-wise refinement and top-down modular?

Answer 16

• Using step-wise refinement to produce a top down modular design
• Way of tackling problem decomposition

Question 17

Exam Question: Describe how decomposition can be used in the design of the game Four in a Row

Answer 17

• Breaks a problem down into component parts
• Game can be divided into subprograms
• Subprograms can then be programmed as subroutines

Question 18

What is Divide and Conquer?

Answer 18

• Is a technique that reduces the size of a problem with each successive iteration
• Splitting a task down into smaller tasks which are then tackled separately.

Question 19

What is backtracking?

Answer 19

• Process of incrementally building towards a solution and abandoning partial success when the solution can’t be completed and going to a previously successful match
• Used for logic problems, path/route-finding

Question 20

What is Data Mining?

Answer 20

• Analysing vast amounts of data gathered from a variety of sources to discover new information and trends

Question 21

What can Data Mining be seen in?

Answer 21

• Used by companies to maximise profits.
• Weather Modelling
• Business and Economics
• Stock Market
• Medical Research

Question 22

What is Heuristics

Answer 22

• Rule of thumb
• Make use of our experience to find a solution that is good enough
• A solution that has high probability of being correct may be acceptable and provide good results

Question 23

Exam Question: A multi national retailer has a very large database, storing customers, stock and orders. The retailer uses data mining to retrieve a variety of information. Explain how they will use data mining?

Answer 23

• Can look for links between a customer’s purchases
• Give recommendations for further purchases
• Check for days/times/months where increases are likely and what the increase will purchase
• Matching sales

Question 24

What is Performance Modelling?

Answer 24

• Process of approximating how well models perform using mathematical approximations and simulations

Question 25

Performance Modelling: Company tested a new high-tech cloud based server. May send millions of requests - test understress. However this is expensive and hard to replicate. What can they do?

Answer 25

* Instead servers could be closely monitored, while low-level transactions take place. * Mathematical modelling can be used to calculate how servers would perform under more stress * Used in game development - may use beta testing

Question 26

What is Pipelining?

Answer 26

* Completing 3 instructions simultaneously * Whilst one is being fetched, another is being decoded another being executed

Question 27

What is Visualisation?

Answer 27

* Includes a variety of techniques (diagrams, images, graphs, flow charts) that aim to illustrate what a problem entails * Allows us to create a mental image of what a program will do

Question 28

What are some benefits of Visualisation techniques?

Answer 28

* Can be used to explain complex tasks, scenarios or situations * Can be used to model, represent, analyse, summarise concepts and data * Present information which is more easy to understand * Can offer alternative views as how to solve problems.

Question 29

Exam Question: Describe the term Pipelining

Answer 29

* Data/ processes arranged in a series, the output of 1 process is the input of the next

Question 30

Exam Question: Identify 2 advantages of using visualisation

Answer 30

* Visualisations benefit humans rather than computers * Visualisations present information in a simpler form to understand * Visualisations can best explain complex situations