2.2.2 Computational Methods

Question 1

How does hardware pose limits on computable algorithms?

Answer 1

A particular proem may require more memory than is feasible, rendering it ‘unsolvable.’

Question 2

How does exponential complexity pose limits on computable algorithms?

Answer 2

The problem requires an exponential amount of work to be done. Using faster/more processors will make little difference.

Question 3

What are the computational methods to solve tractable problems?

Answer 3

• Enumeration
• Abstraction
• Decomposition
• Theoretical approach
• Simulation and automation

Question 4

What is enumeration?

Answer 4

Many problems, including puzzles, can be solved using this method.
This involves designing an algorithm that performs an exhaustive search and attempts all possible solutions until the correct one is found.

Question 5

How is abstraction and decomposition good in solving algorithms?

Answer 5

These techniques simplify the complexity of the problem and break it down, making it easier to write an algorithm and solve the problem.

Question 6

How does a theoretical approach help solve algorithms?

Answer 6

If a problem is reduced to pure theory, it can be represented using mathematic equations.

Computers are great at maths, so these problems are great candidates for being solved by algorithms.

Question 7

What is simulation and automation?

Answer 7

Simulation - the process of designing a model of a real system in an attempt to understand its behaviour

Automation - building problem-solving models and putting them into action

Question 8

How does simulation help in solving algorithms?

Answer 8

They tend to make heavy use of abstraction and are ways of turning complex problems into ones that can be solved more easily by algorithms.

Question 9

What is problem recognition?

Answer 9

The ability to recognize and acknowledge that an issue exists or that a situation needs attention in an existing process or program.

The ability to define a problem and determine exactly what it is.

Question 10

What is problem decomposition?

Answer 10

The process of taking a large problem and breaking it down into smaller several sub problems.

Question 11

How can you tackle problem decomposition?

Answer 11

Using step-wise refinement to produce a top-down modular design.

Question 12

What is Divide and Conquer?

Answer 12

Technique that reduces the size of a problem with each successive iteration.​

It can also refer to the task of splitting a task into smaller tasks, which are then tackled separately.

Question 13

How does (in general) the Divide and Conquer technique work?

Answer 13

1. Take a problem (e.g., a data set)
2. Apply some rules
3. Based on the outcome of the rules, discard data that doesn’t match
4. Repeat the process with data that is left

Question 14

What is abstraction?

Answer 14

Hiding unnecessary detail and showing details that are important in context in order to reduce complexity.

A representation of reality, using symbols to show real-life features or irrelevant features left out. ​

Question 15

What is backtracking?

Answer 15

The process of incrementally building towards a solution, abandoning partial success when the solution can’t be completed and going back to a previously successful match.

Question 16

What is data mining?

Answer 16

The concept of analysing vast amounts of data gathered from a variety of sources to discover new information and trends.

Question 17

What is heuristics?

Answer 17

Approach to solving problems that allows or even encourages us to make use of our experience and find a solution that can be considered “good enough”.​

Question 18

What is performance modelling?

Answer 18

The process of approximating how well models perform using mathematics.

This method is based around the use of simulation and mathematical approximations within those simulations without having to perform detailed testing, which could be prohibited due to time or cost.

Question 19

What is pipelining?

Answer 19

Splitting a task into manageable chunks and overlapping these small processes to speed up the overall process.

The data/process is arranged in a series, and the output of one process is the input of the next.

Question 20

What is visualisation?

Answer 20

Creating a mental image of what a program will do or how it will work.​

Question 21

Why is abstraction important when solving a problem?

Answer 21

When tackling a problem, you need to consider which details are important to the solution and which ones are not.

In any scenario, there would be many variable you would have to consider. No program should aim to replicate all of these variables and their possible interactions.

Question 22

What is ‘Big Data’ ?

Answer 22

• Associated with data mining
• Refers to extremely large data sets

These can be analysed computationally using various data mining techniques to reveal patterns, trends and associations, especially towards human interactions and behaviour.

Question 23

Where is data mining used in?

Answer 23

• Weather modelling
• Business and economics
• Stock market
• Science and engineering
• Medical research
• Law enforcement

Question 24

Why would heuristics be used?

Answer 24

Trying to find an exact answer may be unrealistic or even impractical due to hardware limitations. So a solution with a high probability of being correct may be acceptable.

They don’t guarantee the best solution, but the results produced will be satisfactory. This is why heuristics is referred to as the rule of thumb.

Question 25

Why is visualisation needed to solve a problem?

Answer 25

This is more beneficial to humans than computers; they can help explain complex situations by presenting the information in a simpler, visual format to make it easier to understand the problem.