Decision Maths 1 Revision

This is revision for the decision 1 maths syllabus.

HideShow resource information
Preview of Decision Maths 1 Revision

First 394 words of the document:

Further Maths Revision.
Bubble Sort ­ Used to order items into ascending or descending order.
To perform the bubble sort algorithm:
1. Start at the beginning of the list and compare the first and second term. If they are in
order leave them. If they are not in order swap them.
2. Then compare the second and third values and continue repeating until a pass is
completed without any swaps.
Quick Sort ­ Used to order items in descending or ascending order.
To perform the quick sort algorithm:
1. Choose the item at the mid point for the pivot.
2. Write all items that are less than the pivot value before the pivot in a sub list, keeping
them in order.
3. Then write the pivot, which will now be in the correct place.
4. Then write all values greater than the pivot after the pivot keeping them in order as
they were in the list originally.
5. Then repeat these stages for each sub list until all values have been chosen as pivots.
Binary Search A binary search is used to find an item in an ordered list.
Binary search is a technique for locating a particular value in a sorted list by finding the
median value and comparing it to the target value.
To perform the binary search:
1. Select the middle value.
2. If the value you are looking for is the middle value stop.
3. If it is in the top half of the list discard the bottom half and the pivot.
4. If it is in the bottom half, discard the top half and pivot.
5. Then repeat steps for remaining items.
First fit bin packing algorithm.
To perform the first fit algorithm:
1. Take the items in the order given.
2. Place each item in the first available bin starting at bin 1.
First fit decreasing bin packing algorithm.
To perform the first fit decreasing algorithm:
1. Reorder the items into descending order.
2. Apply the first fit algorithm to the reordered list.
Full bin packing algorithm.
To perform the full bin algorithm:
1. Gather the items into full bins.
2. Then pack these full bins into the bins first.
3. Any remaining items apply the first fit algorithm.

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

The lower bound is the minimum amount of bins you need. The lower bound is calculated
by the sum of the lengths or heights of the items divided by the space per bin.
Algorithms on graphs
A minimum spanning tree is a spanning tree such that the total length of its arcs is as small as
Kruskal's (greedy) algorithm is an algorithm used to find the minimum spanning tree of a
network, meaning the algorithm finds the shortest, cheapest or fastest route.…read more

Page 3

Preview of page 3

Here's a taster:

Semieulerian graph has precisely only tow odd vertices.
Route Inspection algorithm.
Chinese Postman Algorithm is used to find the shortest route tat traverses every arc at
least once and returns to the starting point.
If all the vertices have an even valency the network is traversable and therefore he length of
the shortest route will be equal to the weight if the network.
If there are only tow odd vertices then repeat the shortest route between them and add it
two the network.…read more

Page 4

Preview of page 4

Here's a taster:

A bipartide graph has two sets of nodes where arcs may never connect nodes in the same
To perform the maximum matching algorithm:
1. Start with any initial matching.
2. Search for an alternating path.
3. Change the status of the alternating path.
4. List the new matching.
5. If the matching is now complete stop. If not look or another alternating path and
repeat.…read more



lots of spelling mistakes in this!

Similar Mathematics resources:

See all Mathematics resources »See all resources »