D1 Section 1

Algorithm Flow ChartsRemeber to take your time and follow the chart exactly, reading all of the boxes each time.

Lower Boundgives the minimum Number of Bins needed add up the height/weight (etc.) of the items and divide the total by the capactiy of the bins working out the lower bound doesn't mean you'll definitely fit the items into this number of bins if your solution does match then it is optimal

Always round up!

First-Fit probably won't give an optimal solution take the first item in the list and place in first bin move on to the next item and place in the first bin it'll fit into Repeat step 2. until all the items are in a bin

First-Fit Decreasing gives a better solution than the first-fit algorithm but it sill might not be optimal. put items into into descending order first using a sorting algorithm carry out first-fit algorithm

Full-Bin usually wastes the least space and is more likely to produce an optimal solution Look at the items that will add up to give a full bin (done by eye) Once you've filled as many bins as you can, use the first-fit algorithm for the remaining items

Bubble Sort Look at the first 2 numbers in the list. if in correct order, leave alone. If wrong way around swap them. Move on to the next pair of numbers and repeat step 1. Repeat until you reach the last two numbers. When finished a pass go to the beginning and start again until there are no swaps in a pass.

 This set of comparisons is called a pass

The maximum number of passes is \[\frac{1}{2}\times{(n-1)}\times{n}\]

Quick Sort Choose a pivot. Move numbers around the pivot keeping them in the order they appear. Repeat Step 1. for the smaller list just made, When every number has been a pivot you can stop.

To choose a pivot \[\frac{1}{2}(n+1)\]

Binary Search Find the 'middle' item in the list if the 'middle' item is what you're looking for you can stop If not, compare what you're looking for to the 'middle' term. If it comes before it in the list then you can throw away the second half of the list (including the 'middle' term). If the item comes after the 'middle' term, you can throw away the first half of the list (including the 'middle' item). Repeat steps 1.-4. until you find what your looking for.

The list must be in order for the algorithm to work.

\[\frac{1}{2}(a+l)\] a is the position of the first item in the list and l is the position of the last item.

If the list is shrunk to one term and it isn't what your looking for then this shows that your item isn't in the list.

Algorithms

Packing

Sorting

Searching