unit 1
,Algorithm: a sequence of steps that can be followed to complete a task.
There are 3 main types of computational thinking:
1. Decomposition: breaking a bigger problem down into smaller sub problems where
each sub problem accomplishes an identifiable task
2. Abstraction: removing unnecessary details from a problem
An algorithm is more efficient if it uses less iterations and less space if it doesn’t use a list.
A sequence: only one way from the start to the end
Selections: multiple ways from the start to end
Iteration: allows to repeat
Binary search (for ordered list):
● Find the middle item in an ordered list
● If this is the item you are looking for then stop the search
● If not, compare the item you are looking for to the middle item. If it is bigger than the
middle item then delete the first half of the list but if it is smaller then delete the later
half.
● Repeat steps 1-3 until you reach the item you are looking for
Adv: more efficient than linear
Dis: list must be ordered
Linear search (for unordered list):
● Look at the first item
● If this = what you're looking for then stop
● If not look at the next item in the list
● Repeat steps 2-3 until you find what you are looking for or you have finished every
item in the list
Adv: list doesn’t need to be ordered
Dis: less efficient that binary
Bubble sort (unordered):
● Look at first two items
● If they are in the right order then don’t do anything but if they are in the wrong order
then swap them
● Move to the next pair items and repeat step 2
● Repeat step 3 until you get to the end of the list
● Repeat steps 1-4 until there are no more swaps to be made
Adv:
● simple algorithm that can be implemented on a computer
● Efficient way to check if a list is already in order
● Doesn’t use much memory
Dis:
● Inefficient way to sort a list
, ● Slow for large lists
Merge sort:
● Split the list in half (2 sublists)
● Repeat step 1 until each list only has one value
● Merge pairs of sublists so that each sublist has twice as many items, sort the items
● Repeat step 3 until all the sublists are merged together
Adv:
● More efficient than bubble sort for large lists
● Has consistent running time
Dis:
● If the list is already sorted it will still go through the whole process so the bubble sort
may sometimes be quicker
● It uses more memory
,Algorithm: a sequence of steps that can be followed to complete a task.
There are 3 main types of computational thinking:
1. Decomposition: breaking a bigger problem down into smaller sub problems where
each sub problem accomplishes an identifiable task
2. Abstraction: removing unnecessary details from a problem
An algorithm is more efficient if it uses less iterations and less space if it doesn’t use a list.
A sequence: only one way from the start to the end
Selections: multiple ways from the start to end
Iteration: allows to repeat
Binary search (for ordered list):
● Find the middle item in an ordered list
● If this is the item you are looking for then stop the search
● If not, compare the item you are looking for to the middle item. If it is bigger than the
middle item then delete the first half of the list but if it is smaller then delete the later
half.
● Repeat steps 1-3 until you reach the item you are looking for
Adv: more efficient than linear
Dis: list must be ordered
Linear search (for unordered list):
● Look at the first item
● If this = what you're looking for then stop
● If not look at the next item in the list
● Repeat steps 2-3 until you find what you are looking for or you have finished every
item in the list
Adv: list doesn’t need to be ordered
Dis: less efficient that binary
Bubble sort (unordered):
● Look at first two items
● If they are in the right order then don’t do anything but if they are in the wrong order
then swap them
● Move to the next pair items and repeat step 2
● Repeat step 3 until you get to the end of the list
● Repeat steps 1-4 until there are no more swaps to be made
Adv:
● simple algorithm that can be implemented on a computer
● Efficient way to check if a list is already in order
● Doesn’t use much memory
Dis:
● Inefficient way to sort a list
, ● Slow for large lists
Merge sort:
● Split the list in half (2 sublists)
● Repeat step 1 until each list only has one value
● Merge pairs of sublists so that each sublist has twice as many items, sort the items
● Repeat step 3 until all the sublists are merged together
Adv:
● More efficient than bubble sort for large lists
● Has consistent running time
Dis:
● If the list is already sorted it will still go through the whole process so the bubble sort
may sometimes be quicker
● It uses more memory
