# ALGORITHMS for D1 MATHEMATICS (Edexcel)

A compilation of all the required algorithms to be used in the first Decision module of Edexcel's Mathematics AS Level.

- Created by: Benjamin Freed
- Created on: 02-04-13 19:44

First 438 words of the document:

ALGORITHMS for D1 MATHEMATICS (Edexcel)

BinPacking Algorithms

FullBin Algorithm

1) Search for combinations of items which exactly fill the bins.

2) When no more such combinations exist, create a new bin and place an item into it.

3) Place items into the first bin they will fit in.

4) When no bin is capable of taking the item, create a new bin and repeat Step 3.

FirstFit Algorithm

1) Taking the items in the order they are given, place items into the first bin they will fit in.

2) When no bin is capable of taking the item, create a new bin and repeat Step 1.

FirstFit Decreasing Algorithm

1) Sort the list of items into descending order.

2) Taking the items in the new order, place items into the first bin they will fit in.

3) When no bin is capable of taking the item, create a new bin and repeat Step 2.

Sorting Algorithms

Bubble Sort Algorithm

1) Moving along the list, compare pairs of values, swapping the values if in the wrong order or

preserving them as is if they are correctly ordered.

2) When the end of the list has been reached and the pass has been completed, repeat Step 1,

ignoring the final value(s) in the list from previous passes.

3) When a pass has been completed without any swaps, stop the algorithm is complete.

Quick Sort Algorithm

1) Select the middle value in the list using the formulae (N+1)/2 for an odd number or (N+2)/2 for

an even number.

2) Using the selected value as a pivot, move items of higher or lower values than the pivot to either

side of the pivot, keeping them in the order in which they appear.

3) Make a sublist for either side of the pivot and subsequently repeat the algorithm for the

successive sublists.

Binary Search Algorithm

1) Find the middle item in the list using the formulae (N+1)/2 for an odd number or (N+2)/2 for an

even number.

2) If the middle item is the target, stop the algorithm.

3) If the middle item is greater than the target, create a new search list from items lower than the

middle item conversely, if the middle item is less than the target, create a new search list from items

higher than the middle item.

4) Repeat the algorithm until the target is found or until the search list is empty (which demonstrates

that the target is not in the list).

Minimum Spanning Tree Algorithms

Kruskal's Algorithm

## Comments

No comments have yet been made