What is an algorithm?
A finite sequence of step-by-step instructions carried out to solve a problem
Name 2 methods of sorting unordered lists
- Bubble Sort
2. Quick Sort
What are the steps to the bubble sort algorithm?
- Start at beginning of working list and move from left to right, comparing adjacent items
- If the two items are not in order, swap them
- If the two items are in order, leave them
- Once at the end of the working list, the last item is in its final position (no longer part of working list)
- If you had swaps in last pass, repeat steps 1-3
- If not, the list is sorted
What are the steps to the quick sort algorithm to sort a list in ascending order?
- Choose item at midpoint of list (even-numbered list has a midpoint of item to the right of middle) to be the pivot point
- Write all items less than pivot point, keeping their order, as a sub-list
- Write down the pivot point
- Write remaining items after pivot point as sub-list
- Apply steps 1-4 to each sub-list
- Once all items have been chosen, the list is ordered
What are the 3 bin-packing algorithms?
- First-fit
- First-fit decreasing
- Full-bin
What is the state of the order of a list for the first-fit algorithm?
Items are in the order they are given
What is the state of the order of a list for the first-fit decreasing algorithm?
Requires the items to be in descending order before applying algorithm
What is the state of the order of a list for the full-bin algorithm?
Order does not matter
What are the steps to the first-fit algorithm?
- Take items in order they are given
2. Place each item in first available bin that can take it, starting from Bin 1 each time.
What are the steps to the first-fit decreasing algorithm?
- Sort items in descending items
2. Apply first-fit algorithm to this list
What are the steps to the full-bin algorithm?
- Use observation to find combinations of items that will fill a bin, packing these items first
- Any remaining items should be packed using first-fit algorithm
What is the advantage and disadvantage of using first-fit algorithm?
Advantage: Quick to implement
Disadvantage: Unlikely to lead to good solution
What are the advantages and the disadvantage of using the first-fit decreasing algorithm?
Advantages: Easy to implement and usually get a fairly good solution
Disadvantage: May not get optimal solution
What is the advantage and disadvantage of using the full-bin algorithm?
Advantage: Usually get a good solution
Disadvantage: Difficult to do, esp. with many awkward numbers
What is the order of an algorithm?
A function of its size
If an algorithm has an order of f(n), what factor will the algorithm’s run time increase by if the size of the problem n to m?
f(m) / f(n)
When the size of a problem is increased by a factor of k, how long does it take a linear order algorithm to complete?
k times as long
When the size of a problem is increased by a factor of k, how long does it take a quadratic order algorithm to complete?
k squared times as long
When the size of a problem is increased by a factor of k, how long does it take a cubic order algorithm to complete?
k cubed times as long
