Decision Maths: 1. Algorithms Flashcards
How do you carry out a Quick Sort Algorithm
You select a pivot and split the items into two sub-lists - those less than the pivot and those greater than the pivot:
- Choose the item at the midpoint of the list to be the first pivot (if there’s an even number of items, choose to the right of the middle)
- Write down all the items that are less than the pivot, keeping their order, in sub-list.
- Write down the pivot
- Write down the remaining items (those greater than the pivot) in a sub list
- Apply steps 1 to 4 to each sub-list
- When all the items have been chosen as pivots, stop. Write ‘Sort Complete’
What is the Order of an Algorithm
The order of an algorithm is described as a function of its size. If an algorithm has an order f(n), then increasing the size of the problem from n to m will increase the run time if the algorithm by a factor of approximately f(m)/f(n).
How are Orders Displayed (e.g a Quadratic Order or a Cubic Order)
Order n^2
(Quadratic Order)
Order n^3
(Cubic order)
If an algorithm has order n^2, what will be the effect of increasing the size of the problem from 10 to 20?
Order n^2
(Quadratic Order)
20/10 = 2
2^2 = 4
If an algorithm has order n^3, what will be the effect of increasing the size of the problem from 10 to 20?
Order n^3
(Cubic Order)
20/10 = 2
2^3 = 8
What should you do as a Bubble Sort develops
As the bubble sort develops, it is helpful to consider the original list as being divided into a working list, where comparisons are made, and a sorted list containing the items that are in their final positions. To start with, all items are in the working list.
Method to perform a Bubble Sort
- Start that the beginning of the working list and move from left to right comparing adjacent items.
a) If they are in order, leave them
b) If they are not in order, swap them. - When you get to the end of the working list, the last item will be in its final position. This item is then no longer in the working list.
- If you have made some swaps in the last pass, repeat step 1.
- When a pass is completed without any swaps, every item in it’s final position and the list is in order.
What are the 3 Bin-Packing Algorithms
- First-Fit Algorithm
- First-Fit Decreasing Algorithm
- Full-Bin Algorithm
Method for the First-Fit Algorithm and how does it work
Method:
1. Take the items in the given order
2. Place each item in the first available bin that can take it. Start from bin 1 each time.
- The first-fit algorithm works by considering items in the order they are given.
Advantage(s) and Disadvantage(s) of the First-Fit Algorithm
Advantages:
- It is quick to implement
Disadvantages:
- It is not likely to lead to a good solution
Method for the First-Fit Decreasing Algorithm and how does it work
Method:
1. Sort the items so that they are in descending order.
2. Apply the first-fit algorithm to get the reordered list.
- The first fit decreasing algorithm requires the items to be in descending order before applying the algorithm.
Advantage(s) and Disadvantage(s) of the First-Fit Decreasing Algorithm
Advantages:
- You usually get a fairly good solution
- It is easy to implement
Disadvantages:
- You may not get an optimal solution
Method for the Full-Bin Packing Algorithm and how does it work
Method:
1. Use observation to find combinations of items that will fill a bin. Pack these items first.
2. Any remaining items are packed using the first-fit algorithm.
- Full bin packing uses inspection to select items that will combine to fill bins. Remaining items are packed using the first-fit algorithm.
Advantage(s) and Disadvantage(s) of the Full-Bin Packing Algorithm
Advantages:
- You usually get a good solution
Disadvantages:
- It is difficult to do, especially when the numbers are plentiful and awkward.
