Unit 2 - Problem Solving Flashcards
What is computational thinking?
The ability to think logically about a problem and apply techniques for solving it
What are the 5 main ways to solve a problem?
- Enumeration (list all cases)
- Simulation
- Theoretical approach
- Creative approach
- Trial and error
What does simulation involve?
Designing a model for a system in order to understand its behaviour and then testing it to observe how the system responds to different situation
What does enumeration involve?
Running every possible solution until there is one that works
What does the decrease and conquer approach to algorithm design involve?
Breaking down a problem into smaller sub-problems which can be tackled individually and then applied to the greater problem
What is an algorithm?
A sequence of steps that can be followed to complete a task and always terminates
What does a good algorithm need to do?
- Have a clear set of steps which produces a successful outcome for any set of inputs
- Allows for invalid inputs
- Terminate
- Efficiently achieve the outcome in as few steps as possible
- Be designed in a way that it can be understood and edited by others
What do hierarchy charts do?
Break down a bigger problem into smaller subtasks, a visual representation of decomposition
What does an insertion sort entail?
Removing an item and replacing it in the correct position within the set
What type of sets is an insertion sort suited to?
Small sets
When is bubble sort used?
When there is a small set of values
What does a bubble sort entail?
Iterating through the set n-1 times and comparing a value to the ones which are next to it, if they need to switch a switch is carried out
What does a linear search entail?
Iterating through the items in the list and comparing them to the desired item, if they match then this item is returned
What does a binary search entail?
Splitting the set in two and then checking to see if the desired item is higher or lower, if it is lower the higher section of the set can be discarded and vice versa. This is repeated until the desired item is attained
Why do we test?
To reveal errors and prove that a system does not work
Define module testing
Ensuring a subprogram works correctly
Define program testing
Ensuring that each program within the system works in isolation
Define system testing
Ensuring that the whole system works and does what is required of it according to the specification