Algorithms Flashcards
What is meant by decomposition?
Breaking a complex problem down into smaller problems and solving them individually.
What is meant by abstraction?
Separating the important parts out from the problem (ignoring unnecessary details)
Why is using algorithmic thinking useful when solving a problem?
If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future.
What is pseudocode?
A neutral, made-up coding language made to roughly write out algorithms to be converted to another language,
Give three features of well-written pseudocode.
Readable
Easy to interpret
Not too vague
What are the benefits of writing algorithms in psuedocode rather than a programming language?
It is quick to write and can be easily converted to another programming language.
What are the four steps of the binary search algorithm?
Find the middle item in the ordered list.
If this is the item searched for, then stop (it is found).
If not, compare the searched item with the middle item - if it comes before the middle item, discard the second half of the list (or vice versa)
Repeat steps 1-3 until the item is found.
What are the four main steps of a linear search algorithm?
Look at the first item in the unordered list.
If this is the item searched for, then stop (it is found).
If not, check the second item in the list. If this is the item searched for, then stop (it is found).
Repeat steps 1-3 until the item is found.
What are the benefits and drawbacks of using a linear search over a binary search?
Benefits - can be used on any type of list, similar run time when used in a small (ordered) list
Drawbacks - slower when used on a large (ordered) list
What are the five steps of the bubble sort algorithm?
Check the first 2 items in the list.
If they’re in the right order, leave them alone. If they’re wrong, swap them.
Move onto the next pair of items (2nd & 3rd) and repeat step 2.
Repeat step 2 until you reach the end of the list. (one pass)
Repeat steps 1-4 until there are no swaps left to make.
What are the four steps of the merge sort algorithm?
Split list in half to make 2 sub-lists
Repeat step 1 until all the sublists contain 1 item
Merge pairs of sublists so when they are combined, they are sorted
Repeat step 3 until all the sublists are merged and in order
What are the strengths and weaknesses of bubble sort?
Strengths - simple algorithm, doesn’t use much memory
Weaknesses - slow (for large lists), inefficient
What are the strengths and weaknesses of merge sort?
Strengths - generally more fast and efficient, consistent running time
Weaknesses - uses more memory than bubble sort
