# D1: Section 1- Algorithms

HideShow resource information
• Created by: amy
• Created on: 11-03-13 12:59

## Algorithm

• An algorithm is a set of precise instruction which if followed will solve a problem.
• Algorithms start with an input and have an end result. This means the algorithm will stop when you have a solution.
1 of 9

## Algorithm in the form of a flow chart

• Flow charts are often used to design computer programs
• Flow charts are linked by arrowed lines
• As with an algorithm in words, you need to follow each step in order
• loops are used to take you back to an earlier stage and are a way of repeating steps

boxes used:

Start/ End                  Instruction                      Desicion

2 of 9

## Bubble sort

• Bubble sort is to put a list into aplhabetical or numerical order
• In a bubble sort we compare adjacent items
• If there are numbers in your list, there will be n-1 comparisons in the first pass

The algorith:

1. start at the beggining of the list. Pass through the list and compare adjacent values. For each pair of values

- if they are in order leave them

-if they are not in order swap them

2. When you get to the end of the list, repeat step 1.

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

3 of 9

## Quick sort

• The quick sort is quick and efficent
• You select a pivot and then split teh items into two sub-lists: those less than the pivot, and those greater
• Pivots are then selected in each sub-list to create futher sub-lists

The algorithm: (for a list in ascending order)

1. Choose the item at the mid-point of the list to be the first pivot. (if the list has an even number of items the pivot should be the item to the right of the middle.)

2. Write down all the items that are less than the pivot, keeping their order, in a sub-list.

3. Write down the pivot.

4. Write down the remaining items (those greater than the pivot) in a sub-list.

5. Apply the steps 1 to 4 in each sub-list.

6. When all the items have been chosen as pivots, stop

4 of 9

## Binary Search

• A binary search will search an ordered list to find out whether a particular item is in the list. If it is in the list, it will locate its position in the list.
• A binary search concentrates on the midpoint of an ever-halving list, so it is very quick.

Algorithm:

To search an ordered list of n items for a target T:

1. Select the middle item in the list, m (use n+1/2 and round up if necessary)

2. i) if T=m, the target is located and the search is complete

ii) if T is before m, it cannot be in the second half of the list, so that half, and m, are discarded

iii) if T is after m, it cannot be in the first half of the list, so that half, and m, are discarded

5 of 9

## Bin packing algorithms

• Bin packing refers to a whole class of problems.
• It could be loading cars onto a ferry with several lanes of equal length
• You have a set of items that you need to fit into the minimum number of bins
• An optimal solution is the one that uses the least possible number of bins. THere is often more than one. - it also has the least wasted space

The lower bound

• Sum of the heights and divide by the bin size.
•  You must always round up to determine the lower bound.
• However the optimal solution may not fit the number of bins, you may need more.
• But if it does fit, then the lower bound is the optimal solution
6 of 9

## First-fit algorithm

For the first fit algorithm

1. Take the items in the order given

2. Place each item in the first available bin that can take it. Start from bin 1 each time.

• quick and easy to do

• it is not likely to lead to a good solution
7 of 9

## First fit decreasing algorithm

1. Re-order the items so they are in descending order.

2. Apply the first fit algorithm to the reordered list.

• usually get a good solution
• it is easy to do

• you may not get an optimal solution
8 of 9

## Full bin packing

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.

• you usually get a good solution