Topic 4: Computational Thinking Flashcards
sub-procedure
define
A section of code in a program that does a specific job.
Can be called by name when needed without naming the details as these are wrapped in the procedure. It is therefore an example of abstraction.
pre-fetching / caching
define
Building libraries of pre-formed elements for future use (e.g. using Java libraries to increase efficiency, making sure you have your most commonly used spices ready at the front of your cupboard for cooking etc.)
pre-condition
define
Starting state before algorithm is executed, conditions that need to be fulfilled.
e.g. have to have the required ingredients, a place to cook, pre-conditions while making decisions in cooking (“Are the carrots still hard? Cook them a bit longer”).
post-condition
define
Final state after execution of algorithm, the state you are trying to achieve/ lead up to, the final result.
concurrent processing
define
execution of different instructions simultaneously by multiple processors
sequential/linear search
define
Usual search, go through every value and compare to the target value.
pros and cons of sequential/linear search
Pros:
- Simple to implement
- data doesn’t need to be in order.
Cons:
- Inefficient with large number of elements – may have to go through every single one of them
- time consuming
binary search
define
Values in order. Compare search value with middle value. If smaller, compare to middle value of sub-array to the left. If larger, compare to sub-array to the right, and so on.
pros and cons of binary search
Pros:
- Faster than sequential search
Cons:
- Too complicated for small number of elements
- Only works on sorted lists
- difficult if data is constantly being added.
bubble sort
define
Compare adjacent values. If not in order, swap around
pros and cons of bubble sort
Pros:
- Simple to write, less code
Cons:
- Takes more time to sort – average time increases almost exponentially as number of elements increase.
selection sort
define
Splits array into sub-arrays. First sub-array is sorted, second is unsorted. e.g. to sort in ascending order, find the smallest value, place it in the correct position in the first sub-array by swapping it with the element that was there, move position of beginning of sub-array forward one, loop through the rest (second sub-array) to find the smallest value again. Repeated for all elements.
pros and cons of selection sort
Pros:
- Good for small lists
Cons:
- Not efficient with big number of items – have to find the smallest value many times.
collection
define
Group of objects.
No assumptions are made about the order of the collection (if any) or whether it can contain duplicate elements.
We add and retrieve data from them.
efficiency of an algorithm
define
Amount of computer resources required to perform algorithm’s functions
