3.1 Fundamentals of algorithms Flashcards
Define algorithm
An algorithm is a sequence of steps that can be followed to complete a task.
Define decomposition
Decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
Define abstraction
Abstraction is the process of removing unnecessary detail from a problem.
What command boxes are used in flowcharts?
- Start/Stop
- Input/Output
- Processes
- Decision
What shape is a start/stop command box?
Rectangle with rounded corners
What shape is an input/output command box?
Parallelogram
What shape is a process command box?
Rectangle
What shape is a decision command box?
Diamond
When is the start/stop command box used?
The beginning and the end of the algorithm
When is the input/output command box used?
When anything is put into or taken out of the algorithm
When is the process command box used?
When there are general instructions, processes and calculations
When is the decision command box used?
When there are decisions (often a yes or no question)
Define sequence
A set of instructions in order
Define iteration
Involves repeating actions
Define selection
Involves a choice
How does a binary search work?
1- Find the middle item in the ordered list
2- If this is the item you’re looking for, then stop the search as you have found the item
3- If not, compare the item your looking for to the middle item. If it comes before the middle item, get rid of the second half of the list (and vice versa)
4- You’ll be left with a list that is half the size of the original list. Repeat steps 1 to 3 on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.
What is the positive of binary search?
- Efficient
What is the negative of binary search?
- Data must be sorted
How does a linear search work?
1- Look at the first item in the unordered list
2- If this is the item you’re looking for, then stop the search as you have found the item
3- If not, then look at the next item in the list
4- Repeat steps 2 to 3 until you find the item that you’re looking for or you’ve checked every item
What is the positive of linear search?
- Can be performed on unsorted data
What is the negative of linear search?
- Inefficient
How does bubble sort work?
1- Look at the first 2 items in the list
2- If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them
3- Move on to the next pair of items (2nd and 3rd entries) and repeat step 2
4- Repeat step 3 until you get to the end of the list (this is called one pass). The last item will now be in the correct place, so don’t include it in the next pass
5- Repeat steps 1 to 4 until there are no swaps in a pass.
What is the positive of bubble sort?
- Doesn’t use a lot of memory as all the sorting is done using the original list
What is the negative of bubble sort?
- Inefficient on large sets of data
