1 - Fundamentals of algorithms Flashcards
What is an algorithm?
a sequence of steps that can be followed to complete a task
note that a computer program is just an implementation of an algorithm, and an algorithm is NOT a computer program
What is decomposition?
breaking a problem down into several sub-problems, so each sub-problem accomplishes an identifiable task, which might be further subdivided
What is abstraction?
the process of removing unnecessary detail from a problem to make it easier to solve/see the solution
eg the London Underground map
What is a trace table used for?
used for following an algorithm through by hand to demonstrate its effects on the data contained by certain variables
What are the rules for completing a trace table?
-work through the table by putting values in from left to right, and don’t go backwards ever
-don’t put anything in the space if the variable doesn’t change
How does the linear search algorithm operate?
-starts with the first value in the list
-checks all values in the list in order from start to end until the desired item is found
What are the pros and cons of the linear search algorithm?
-simple to code
-works on both ordered and unordered lists
-inefficient/slow
How does the binary search algorithm work?
-find midpoint of list of numbers and see if it is equal to the desired value
-if not, check if it is greater/less than the desired value
-discard the side of the list that isn’t where the desired item is
-repeat with the other half of the list
Give some pros and cons for the binary search algorithm:
-more efficient as list size increases (discards half each time)
-data must be ordered
-harder to code
How does the bubble sort algorithm work?
-compares 1st and 2nd item, swap if needed
-repeat with 2nd and 3rd, and again until you reach the end of the list
one pass completed
-do more passes until nothing has been swapped in a pass
the larger values “bubble” to the top (or smaller values, depending on if it is descending or ascending order)
Give some pros and cons of the bubble sort algorithm:
-simple to code
-efficient way to check if the list is already ordered
-inefficient
-slower with larger lists
When given a question on the bubble sort like below, how should you complete it?
-make one switch per line
-don’t go back to the beginning for each swap, continue from where you left off in the previous switch and keep going
you forgot this in the end of year 10 exam and you could’ve got 100%
Explain how the merge sort algorithm operates:
-subdivide list into smaller lists until each item is in its own list
-compare adjacent values and swap if needed, join into several lists of 2 values
-compare first values in adjacent lists, then first and second, then second and second, add all values to new list of 4
-repeat until there is only one ordered list
Give the pros and cons of the merge sort algorithm:
-faster + more efficient with large lists
-consistent run time, regardless of how unordered the list already is
-harder to code
-it will still run through the whole process even if it is already ordered
