What is an algorithm?
A set of pricise instructions which, when followed, will solve a problem.
|-9| = 9 (9) = -9
When it's a flow chart - turn into a table & follow instructions
( ) = Start/Stop [ ] = Instuction < > = Decision
Could achieve HCF, LCM, Square numbers, Square roots, Largest number
Start each instruction on a new line, as this makes it clearer for examiner
Always try to state the output
Compares adjacent items
1. Start at the beginning of the list & compare the next values with the one before (if they are in order - leave, if not - swap)
2. When reach the end, repeat step 1.
3. When a pass is completed without any swaps, the list is completed
Could be asked to do in ascending, descending or alphabetical order
Keep number/letters neatly underneath each other - easy for examiner and you to know where you may have made a mistake
Make sure the last pass is stated at the end and includes no swaps
This is quick & efficent
1. Choose the item at the midpoint of the list to be the first (N+1/2 if N is odd. N+2/2 if N is even)
2. Write down all the items less than the pivot (midpoint), in the order that they are already stated
3. Write down the pivot
4. Write the remaining items (greater than pivot)
5. Apply steps 1. & 4. to each until been chosen & then stop!
Circle to indicate pivot. Square to indicate it's correct position.
Never skip a stage & assume it's already in the correct order
Find where particular things are, if any avaliable
1. Select the midpoint in the line (Same way as a Quick Sort)
2. If the ? was the midpoint - the list is completed
If ? is before the midpoint - the second part of the list is discarded & the midpoint
If ? is after the midpoint - the first part of the list is discarded & the midpoint
3. Reapeat steps 1. & 2. until ? is found (if it isn't, it is not in the list)
State what you are doing after each stage e.g. 'So the list becomes' & State the outcome at the end e.g. 'The search is complete' or 'We conclude that ... is not in the list'
Before doing anything, the lower bound must be calculated
To do this you must do the following equation:
Total of all bins
There are 3 methods of bin packing, shown on the following cards;
Bin Packing - First Fit
Leave the order as it is
Place each item in the first avaliable bin that can have it
It is quick but it is unlikely to lead t a good solution
Compare the amount of bins in this algorithm to the lower bound bins
Make sure you double check as it's easy to make mistakes
Bin Packing - First Fit Decreasing
Change the order into decending order
Then apply the first fit
This is good as you usually get a good solution & it's easy/simple
But you may not get an optimal solution (best)
Bin Packing - Full Bin Combinations
This is known as the 'common sence method'
Where you use observations to find combinations of items to fill a bin
Any remaining items are then used in the first fit method
This usually gives you a good solution
However, it's difficult when numbers are large & awkward
Make sure to go over this again if there is any extra time