2.2.2 - Computational Methods

Question 1

What are computational methods?

Answer 1

Techniques used to solve a problem using computational thinking

Examples: Decomposition | Abstraction | Divide and Conquer

Question 2

What is divide and conquer?

Answer 2

• Splits a big problem into smaller parts.
• Examples: Merge Sort | Quick Sort | Binary Search

Divide: Break the given problem into sub problems of same type.
Conquer: Recursively solve these sub problems
Combine: Appropriately combine the answers

Question 3

What is problem decomposition and what benefits does it bring?

Answer 3

Splitting a problem down into smaller sub-problems
* Creates a more manageable problem
* Can lead to the development of subroutines/modules
* Can tackle each sub problem independently

Question 4

What is data mining?

Answer 4

• Turning large quantities of data (big data) into useful information
• Finding patterns and anomalies within large data sets
• Resulting information is used to make predictions

Question 5

What are some example insights that might be gained when a supermarket uses data mining?

Answer 5

• Identify customer trends in order to identify offers to send customers
• Identify which stores are making the most profit
• Identify which items are not selling well to replace them with other items

Question 6

Define problem recognition

Answer 6

Identifying there is a problem to be solved, to determine exactly what the problem is from a description and to determine if the problem can be solved with computational methods.

Question 7

Define and give examples of performance modelling

Answer 7

Simulate systems to test the behaviour of them before it is used under load.

Examples
* Testing the solution with many simultaneous transactions, often called stress testing
* Testing it with a large amount of data in the database

Question 8

Define and give examples of visualisation

Answer 8

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

Examples

• Graphs
• Arrays shown as grids

Question 9

Define and give examples of backtracking

Answer 9

A methodical way of trying out different sequences until you find one that leads to a solution. Solving a maze is a typical problem of this kind.

Backtracking in Depth-First Tree Traversal

When a node does not have any node to visit e.g. D, the algorithm goes back to the previous visited node e.g. B to check for further unvisited nodes to visit e.g. H

Question 10

Describe heuristics, their purpose, and give examples of where they are used.

Answer 10

• Rule of thumb approach which is used when unfeasible to analyse all eventualities. This leads to a “good enough” result although it is not 100% reliable.
• Used to speed up process of finding solution

Example Uses
* Used in the A* algorithm to estimate the distance to destination (more efficient than Dijkstra’s)
* Heuristics in Virus scanning: used to see if a file is displaying the signs of a virus rather than knowing it is a virus.

Question 11

What is pipelining?

Answer 11

• Concurrent processing of multiple instructions – increases the number of instructions processed in a set period (increased speed of execution).
• Would allow one instruction to be fetched as the previous one is being decoded and the one before that is being executed.
• Prevents the CPU having to wait – No idle components

Question 12

What issues does pipelining face?

Answer 12

Struggles with code that uses branching, as wrong instruction may be brought, meaning pipe flush would be used.