2.2.2 Computational Methods

Question 1

What is a computable problem?

Answer 1

A problem that can be solved with an algorithm.

Question 2

What are three limiting factors to computable problems?

Answer 2

Processing power, speed and memory.

Question 3

What is problem decomposition?

Answer 3

Breaking a clearly defined problem into smaller subproblems, until each subproblem can be represented as a self contained subroutine.

Question 4

How does decomposition save time?

Answer 4

Programmers may find certain sections of the program that can be implemented using precoded modules or libraries.

Question 5

How does decomposition make a project easier to manage?

Answer 5

Different developer teams can be assigned separate sections of the code according to their specialisms. These can be individually designed, developed and tested before being combined to produce a working piece of software at the end.

Question 6

How does decomposition make debugging simpler and less time consuming?

Answer 6

It is easier to identify and fix errors in individual modules, compared to an entire application.

Question 7

What is divide and conquer?

Answer 7

A problem solving technique.

Question 8

Describe the three stages of Divide and Conquer.

Answer 8

• Divide: The size of the problem is halved with every iteration.
• Conquer: Each individual problem is solved, often recursively.
• Merge: The solutions to the sub problems are combined to form the final solution to the problem.

Question 9

What three algorithms use the divide and conquer approach

Answer 9

Binary Search
Quick Sort
Merge Sort

Question 10

Advantage of using Divide and Conquer

Answer 10

The size of the problem halves with each iteration, which greatly simplfies very complex problems. This means that as the size of the problem grows, the time taken to solve it will not grow as significantly.

Question 11

Disadvantage of using Divide and Conquer

Answer 11

• Possiblity of stack overflow.
• Large programs are very difficult to trace

Question 12

Representational abstraction

Answer 12

Excessive details are removed to simplify a problem

Question 13

Benefit of abstraction

Answer 13

Allows programmers to focus on the core aspects required of the solution, rather than worrying about unnecessary details.

Question 14

How can using levels of abstraction benefit a large complex project?

Answer 14

The large project can be split into smaller component parts.

Question 15

Abstraction by generalisation

Answer 15

Groups together different sections of the problem with similar underlying functionality. This allows for segments to be coded together and reused, so it saves time.

Question 16

What is backtracking?

Answer 16

A problem solving technique implemented using algorithms, often recursively.

Question 17

How does backtracking work?

Answer 17

• 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, the algorithm backtracks to the previous stage and visits an alternate path.

Question 18

Give an example of back tracking

Answer 18

Depth first traversals

Question 19

What is data mining?

Answer 19

A technique used to identify patterns or outliers in large sets of data (big data).

Question 20

What is big data?

Answer 20

Large sets of data typically collected from a variety of sources.

Question 21

Data mining is used in what kind of software?

Answer 21

Software designed to spot trends or identify correlations between data which are not immediately obvious.

Question 22

What can insights from data mining be used for?

Answer 22

Making predictions about the future based on previous trends.

Question 23

What kinds of decisions do companies use data mining to assist?

Answer 23

Business and marketing decisions

Question 24

Consider a supermarket. What kind of information would data mining reveal?

Answer 24

Which products are bought at certain points in the year

Question 25

How might a supermarket use data mining in combination with the personal data of their customers?

Answer 25

To reveal insights about people's shopping habits and preferences based on their personal info, which can be used to inform marketing techniques.

Question 26

Data mining often involves the handling of personal data. What compulsory action must be taken as a result?

Answer 26

The personal data must be dealt with in accordance with data protection legislation.

Question 27

What are heuristics?

Answer 27

A non optimal, "rule of thumb" approach to problem solving.

Question 28

What are heuristics used to find?

Answer 28

An approximate solution to a problem when the standard solution is unreasonably time consuming or resource intensive to find.

Question 29

Applications of heuristics

Answer 29

- A* Algorithm - Machine learning - Intractable problems (problems where solution takes unreasonably long to be found)

Question 30

What is performance modelling?

Answer 30

Performing mathematical analysis to assess efficiency.

Question 31

How does performance modelling eliminate the need for true performance testing?

Answer 31

It provides mathematical methods to test a variety of loads on different operating systems.

Question 32

Example where performance modelling is used.

Answer 32

Testing safety critical computer systems, such as those used on an airplane, where it is not safe to do a real trial run before the system can be implemented.

Question 33

What three pieces of information does performance modelling provide companies with?

Answer 33

- The capabilities of a system - How a system copes in diffferent environments - Whether or not it is safe to implement

Question 34

How does pipelining work?

Answer 34

Modules are divided into individual tasks, with different tasks being developed in parallel.

Question 35

How does pipelining resemble a production line?

Answer 35

The output of one process in pipelining becomes the input of another.

Question 36

Benefit of pipelining

Answer 36

Allows projects to be delivered faster

Question 37

What is visualization?

Answer 37

Presenting data in a way thats easier to understand. This makes it possible to identify trends that were not obvious.

Question 38

How may visualisation be achieved?

Answer 38

By representing data as graphs, trees, charts or tables, depending on data type.

Question 39

Why do businesses use visualization?

Answer 39

To pick up on patterns which can be used to inform business decisions.

Question 40

Give an example of data that visualization can be used on.

Answer 40

Statistical data.

Question 41

What is problem recognition?

Answer 41

Identifying what the problem is