# D1 Mathematics ALGORITHMS

HideShow resource information
• Created by: abbiee
• Created on: 05-03-13 11:18

## What is an algorithm?

A set of pricise instructions which, when followed, will solve a problem.

|-9| = 9            (9) = -9

When it's a flow chart - turn into a table & follow instructions

(      ) = Start/Stop                 [        ] = Instuction                    <      > = Decision

Could achieve HCF, LCM, Square numbers, Square roots, Largest number

Start each instruction on a new line, as this makes it clearer for examiner

Always try to state the output

1 of 8

## Bubble Sort

1. Start at the beginning of the list & compare the next values with the one before (if they are in order - leave, if not - swap)

2. When reach the end, repeat step 1.

3. When a pass is completed without any swaps, the list is completed

Could be asked to do in ascending, descending or alphabetical order

Keep number/letters neatly underneath each other - easy for examiner and you to know where you may have made a mistake

Make sure the last pass is stated at the end and includes no swaps

2 of 8

## Quick Sort

This is quick & efficent

1. Choose the item at the midpoint of the list to be the first (N+1/2 if N is odd. N+2/2 if N is even)

2. Write down all the items less than the pivot (midpoint), in the order that they are already stated

3. Write down the pivot

4. Write the remaining items (greater than pivot)

5. Apply steps 1. & 4. to each until been chosen & then stop!

Circle to indicate pivot.                   Square to indicate it's correct position.

Never skip a stage & assume it's already in the correct order

3 of 8

## Binary Search

Find where particular things are, if any avaliable

1. Select the midpoint in the line (Same way as a Quick Sort)

2. If the ? was the midpoint - the list is completed

If ? is before the midpoint - the second part of the list is discarded & the        midpoint

If ? is after the midpoint - the first part of the list is discarded & the            midpoint

3. Reapeat steps 1. & 2. until ? is found (if it isn't, it is not in the list)

State what you are doing after each stage e.g. 'So the list becomes' & State the outcome at the end e.g. 'The search is complete' or 'We conclude that ... is not in the list'

4 of 8

## Bin Packing

Before doing anything, the lower bound must be calculated

To do this you must do the following equation:

Total of all bins

----------------------

Bin size

There are 3 methods of bin packing, shown on the following cards;

5 of 8

## Bin Packing - First Fit

Leave the order as it is

Place each item in the first avaliable bin that can have it

It is quick but it is unlikely to lead t a good solution

Compare the amount of bins in this algorithm to the lower bound bins

Make sure you double check as it's easy to make mistakes

6 of 8

## Bin Packing - First Fit Decreasing

Change the order into decending order

Then apply the first fit

This is good as you usually get a good solution & it's easy/simple

But you may not get an optimal solution (best)

7 of 8

## Bin Packing - Full Bin Combinations

This is known as the 'common sence method'

Where you use observations to find combinations of items to fill a bin

Any remaining items are then used in the first fit method

This usually gives you a good solution

However, it's difficult when numbers are large & awkward

Make sure to go over this again if there is any extra time

8 of 8