2.1 - Algorithms Flashcards
What is an algorithm?
A sequence of steps that can be followed to complete a task
What is algorithmic thinking?
Following logical steps to solve a problem
What is abstraction?
Ignoring unnecessary information to simplify a problem
What is decomposition?
Breaking down a problem into smaller tasks so it is easier to solve
In a flowchart what represents start/stop terminators?
A ‘squircle’ (square-circle) ▢
In a flowchart what represents subroutines?
A rectangle with a vertical line either side
In a flowchart what is represents the direction of flow?
An arrow
In a flowchart what represents an input or output?
A parallelogram
In a flowchart what represents a process?
A rectangle
In a flowchart what is used to represent a decision?
A diamond with two branches (yes and no)
How do you use a trace table?
- Go through every line
- Only add to a column when that column’s value changes
- Move onto a new row when you move into a new ‘block’ in the code
What is a linear search?
Compares each item one by one until the target is found or the end of the list is reached
What are the advantages of using a linear search?
- No need for the list to be in order
- Quick process for short lists
What is the disadvantage of using a linear search?
Long process for long lists
What is a binary search?
- Compares middle item to the target
- Discards half of the list which the target can’t be in
- Finds the next middle item and repeats until the target is found/runs out of items
What is the advantage of using a binary search?
Time efficient in a large data set
What is the disadvantage of using a binary search:?
Needs to be in order beforehand
What is bubble sort?
- In one pass, go through each pair, swapping if needed
- Repeat passes until a pass happens with no swaps
What is merge sort?
- Divides the list by two until in pairs and compares numbers, swapping them to be in order
- Combines two lists at a time, keeping the items in order
What is insertion sort?
- The list is split into sorted values on the left and unsorted on the right
- Starting from the left, unsorted values are checked and inserted in the correct position in the sorted part
