Chapter 1: Algorithms Flashcards
What is an algorithm?
A finite sequence of step by step instructions carries out to solve a problem
Flow chart shapes:
Oval- start/end
Rectangle- instruction
Diamond- decision/question
How can we sort out an unordered list?
- Bubble sort
- Quick sort
How do we implement a bubble sort e.g ordering in ascending order
1) First, compare the first two items in the list, if the second number is bigger than the first , we leave the items. If the two items aren’t in order, we swap them.
2) You continue doing this until, the last item will be the biggest number (one pass is complete)
3) Do another pass, swapping any items that are in the wrong order
4) Once you do a pass without swapping any items, every item is in the correct position so the list is ordered in ascending order
ONCE FULLY ORDERED WRITE ‘NO FURTHER CHANGES- SORT COMPLETE’
How do we implement a quick sort e.g when ordering in ascending order?
1) Choose the item in the middle of the list to be the first pivot and all numbers that are lower than the pivot go to the left hand side and all numbers bigger than the pivot go to the right hand side.
2) Then for each individual sublist, choose the midpoint and repeat the first step.
3) Continue doing this until all items have been chosen as a pivot - once all been chosen, the items will be in the correct order.
What are the 3 bin packing algorithms?
1) First-fit bin packing
2) First-fit decreasing bin packing
3) Full-bin packing
How do we work out the lower bound of bins needed?
Optimal solution- total length/ length needed in each bin
Round up if its a decimal.
If solution we get is the lower bound, this means we have found an optimal solution
What is the first-fit algorithm?
1) Pack the items in the order of the list given
2) If it doesn’t fit in a bin, put it in next available bin. Start to see if it fits in bin 1 each time.
Positives: quick to implement
Negatives: unlikely to give optimal solution
What is the first-fit decreasing algorithm?
1) Sort the items in the list so they are in decreasing order
2) Then use the first-fit algorithm using the ordered list to fill pack the bins
Positives: Yo can get quite a good solution, easy to implement
Negative: May not get optimal solution
What is the full-bin packing algorithm?
1) Use inspection to select items that will create a full bin.
2) For items that do not cream full bins, use the first-fit algorithm to pack them into bins
Positives: This algorithm is most likely to give you an optimal solution out of all the algorithms
Negatives: Can be difficult/long to implement if the numbers are plentiful an awkward
What is the order of an algorithm?
The order of an algorithm tells us how change in the size of a problem can affect how long it takes for the algorithm to complete.
For bubble sort: total number of comparisons =1/2n(n-1) - this is quadratic so it has a quadratic order
If it has a linear oder, it will take k times as long to complete
If it has a quadratic order, it will take k^2 times as long to complete
If it has a cubic order, it will take k^3 times as long to complete
Order of algorithm examples:
A computer used first-fit bin packing algorithms to determine number of shipments needed to transports 400 lenghts of piping. It takes 0.72 seconds. How long will it take to apply the algorithm to 6200 lengths?
First-fit bin packing algorithm has a quadratic order.
Number of lengths increase by 6200/400 = 15.5
(15.5)^2 X 0.72 = 172.98
It will take 172.98 seconds to complete
