D1 Section 1

Página 1

Algorithm Flow Charts

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

Lower Bound

gives 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