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.

HideShow resource information
Preview of ALGORITHMS for D1 MATHEMATICS (Edexcel)

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

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

List out all edges with their weights, and choose the edge with minimum weight.
2) Compare the next edge with the lowest weight: if the edge would form a cycle, reject it (giving the
reasoning of "cycle") and move on to the next edge.
3) If the edge does not form a cycle, select it.
4) If (n1) edges have not been selected (letting n = number of vertices), repeat Steps 2 and 3 if
(n1) edges have been selected, end the algorithm.…read more

Page 3

Preview of page 3

Here's a taster:

Critical Path Algorithm
1) Perform a forward pass, recording earliest event times e.
2) Perform a backward pass, recording latest event times l.
3) Calculate the total float for each activity using the formula "F(i,j) = (ljei) ­ (i,j)".
4) Construct a critical path by selecting the activities for which the float is equal to 0.…read more

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »