(Done) 2. Algorithms Flashcards
List the three key techniques for computational thinking
- Decomposition
- Abstraction
- Algorithmic Thinking
Define decomposition
- Breaking down a complex problem into smaller problems and solving each one individually
Define abstraction
- Picking out the important bits of information, ignoring the specific details that don’t matter
Define algorithmic thinking
- A logical way of getting from the problem to the solution. 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 conditions are required for a binary search to occur
- The items in the list are ordered
What conditions are required for a linear search to occur
- None
List the five steps in a binary search
- Find the middle item (n+1)/2
- If not item, compare target and current items, if item, stop
- If greater than current item, search second half of the list
- If less than current item, search first half of list
- Repeat indefinitely
List the four steps in a linear search
- Look at the first item in the unordered list
- If this is the item you’re looking for, then stop the search
- If not, look at the next item in the list
- Repeat steps 2 and 3 until you have found the item you are looking for or you have reached the end of the list
Steps in a bubble sort
- Look at the first two items in a list
- If they’re in the right order, leave them, otherwise swap them
- Move onto the next item pair and repeat the check
- Keep completing checks and moving onto the next pair until you reach the end
- Exclude the last term and repeat everything until no more swaps happen
Pros of a bubble sort
- Simple and easy to implement
- Also allows you to check if a list is already in order
- Doesn’t use much memory as all the sorting is done in the original list
Cons of a bubble sort
- inefficient as its time consuming
- Does not cope well with a long list of items
Steps of a merge sort
- Split the list in half, the second sub-list should contain the middle item
- Repeat the splitting in half until each list only contains 1 item
- Merge pairs of sub lists together so that each sub-list has twice* as many items. Each time you merge lists, sort the items
- Repeat until all sub-lists are merged
Pros of merge sorts
- In general more efficient and quicker than bubble and insertion sorts
- Consistent running time regardless of how ordered the items in the list already are
Cons of merge sorts
- Slower than other algorithms for small lists
- Even if the list is already sorted, still goes through the splitting and merging process
- Uses more memory than other sorting algorithms in order to create the separate lists
Steps of an insertion sort
- Look at the second item in the list
- Compare it to all items in the list before it and insert the item into the right place
- Repeat for the third, fourth, fifth etc. items until the last item in the list has been inserted in the right place
Pros of insertion sorts
- Easy to code
- Very good with small lists
- Very little additional memory required as all the sorting is done in the original list
- Very quick at adding items to an already sorted list
- Very quick at checking if a list is already sorted
Cons of an insertion sort
- Doesn’t cope very well with large lists
What does this represent in a flow diagram
- The start or end of a process
What does this represent in a flow diagram
- Selection (if/else)
What does this represent in flow diagram
- Suborutine
What does this do in a flow diagram
- An input or output operation
what is a condition shape in flowcharts
What is an input/output shape in flowcharts
What is a process shape in flowcharts
