D1 - algorithms Flashcards
How are boxes in flow charts linked?
Arrowed lines.
What shapes are used in flow charts and what do they mean?
Curve circle - start/end
Rectangle - instruction
Diamond - decision
What is the bubble sort used for?
To compare adjacent items.
Sorting an unordered list into some kind of order, like numerical or alphabetical.
How do you carry out a bubble sort?
Compare adjacent values, if they are in order leave them, if not swap them.
When you get to the end of the list, repeat again for a second pass, third etc.
When no swaps are made in a pass, the list is in order.
How do you carry out a quick sort?
Choose the mid point value to be the first pivot.
Write down all the values smaller than the pivot,
followed by the pivot,
followed by the greater numbers.
Apply these steps to each sub list, and once all items have been pivots the sort Is complete.
What is a binary search?
A search in an ordered list to find out whether a particular item is in the list, if it is it locates the point.
Concentrates on the mid point of an ever halving list so is quick.
How do you carry out a binary search algorithm?
T = target M = middle point
Select the middle item by n + 1 / 2 and round up if needed.
If T is before m then the second half of the list can be discarded.
Vice versa.
Repeat until T is found or until you result in one value which is not T.
How do you determine the lower noun of bin packing?
Sum up all the heights and divide by the bin size.
Then round up your answer to determine the lower bound/minimum number of bins needed.
How do you carry out the first fit algorithm?
Also first fit decreasing algorithm
Do not change the given order.
Place each bin in the first available bin it can take, starting from bin 1 each time.
Quick.
Not very good solution.
Reorder into descending order and apply first fit.
Quick, easy and fairly good solution.
May not get optimal solution.
Describe how to carry oh the full bin packing algorithm.
Use observation to find combinations of items that will fill a bin.
Any remaining items are packed by first fit.
Good solution.
Awkward with plentiful numbers/awkward full value or numbers.
