Topic 5 Flashcards
What is decomposition?
Breaking a complex problem, down into smaller problems and solving each one individually
What is abstraction?
Taking out the important bits of information from the problem, ignoring specific details that don’t matter
What is algorithmic thinking?
A logical way of getting from a problem to a solution. If the steps you take to solve follow an algorithm you it can be reused and adapt to solve similar problems in the future.
What does an oval mean in a flow chart
Start/end
What is a parallelogram box mean in a flowchart
Input/output
What does a box mean in a flowchart?
General, instructions, processes and calculations
What does a diamond box mean in a flowchart?
A decision
What is a box inside a box mean in a flowchart
Subprogram
What is the arrow show in a flowchart?
Arrows connect the boxes and show the direction you should follow
Conditions for a binary search
List must be ordered
Process of a binary search
Find the middle term in your ordered list
If this is your item then stop
If not compare with the item, you’re looking for, if the middle term comes before get rid of second half and vice versa
You’ll be left for the last half the size of the original list. Repeat steps one to 3 until you find the item.
What can a linear search be used on?
Unordered list
Process for linear search
Look at the first item in the unordered list
If this is your items in stop
Then look at the next item in the list
Repeat steps 2 to 3 until you’ve checked every item or found the one you’re looking for
Advantages of binary search
Faster
Takes fewer steps
Advantages of linear
Simple
Can be done on any type of list
Disadvantages of binary search
List must be ordered
Disadvantages of linear
Slow
Takes a lot of steps
What is bubble sort?
A sorting algorithm?
Pros of bubble sort
Simple
Efficient have already in order
Don’t use much memory
Cons of bubble sort
Inefficient way to sort a list
Doesn’t cope well with very large lists
Process of bubble sort
Look at the first two items in the list
Move the correct order
Look at the next pair of items
Move to correct order
Repeat until end of list
Go back to the first pair and compare
Repeat process until list is in an order
One final pass to check
Process of merge sort
Split the list in half
Keep missing list and half until each list only contains one item
Merge pairs of sublists each merge order the correct way
Repeat until you’ve merged all the sub lists together
Pros of merge sort
More efficient and quicker
Very consistent running time
Cons of Merge sort
It’s slower for small lists
Uses more memory
Process for insertion sort
Look at second item in a list
Compare to all items before it, and insert the number into the right place
Repeat step two for all items in the list, until the last number has been inserted into the correct place
Advantages for insertion sort
Very intuitive
Coped well with smallest
Doesn’t require very much additional memory
Very quick
Very quickly checking this is already sorted
Disadvantages for insertion sort
Doesn’t cope well with very large lists
