2.2.2 - Computational Methods Flashcards
Component 2 (15 cards)
What are computational methods?
What are some examples?
Techniques used to solve a problem using computational thinking
Examples: Decomposition | Abstraction | Divide and Conquer
What is divide and conquer?
- An algorithm that 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
What is problem decomposition and what benefits does it bring?
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
Define problem recognition
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.
Define and give examples of performance modelling
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
Define and give examples of visualisation
- 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
Define and give examples of backtracking
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
Describe heuristics, their purpose, and give examples of where they are used.
- 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.
What are the drawbacks of heuristics?
- Due to timesaving, they are not always accurate, the solution e.g. shortest path might not be the most efficient.
- Requires skill to implement effectively
What is pipelining?
- 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
What issues does pipelining face?
Struggles with code that uses branching, as wrong instruction may be brought, meaning pipe flush would be used.
What is data mining?
- 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, to increase revenue, to target advertising or improve services.
What are the benefits of data mining to the owner of an online multiplayer game?
- Use to target advertising
- Use to find out what users do
- Find features that are used most often and features that are not used
- Find out characteristics of people who use the game
- Can identify areas to focus attention
- Save time and money by identifying areas that are not popular/used
- New features targeted at specific groups which could bring in new business
What are some example insights that might be gained when a supermarket uses data mining?
- 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
What are the drawbacks of data mining?
- Can spot patterns/trends, however it cannot explain them.
- Privacy concerns - potential to misuse the information
- Requires powerful computers with a lot of processing power to process huge amounts of data.
- Need to make sure data collection is legal and in terms and conditions
- Analysis can be costly e.g. may need an external company
- Security - data being collected requires protection
