Decision Maths

You will be given a start point, from this choose the adge with the lowest 'weight'.

Then choose the next edge with the lowest 'weight' from the previously connected arc's.

Do not make a cycle.

• choose an unused edge with the lowest weight, but not making a cycle
• add to the tree
• if there are n-1 edges stop. If not, repeat.

• On the matrix (table), write down all the vertices across the top and down the side.
• Label the column with the start vertex with a 1
• Cross out the corresponding row. 
• Ring the smallest value in ANY labeled column that hasn't been deleted
• label the corresponding vertex with 2 etc. delete the row
• repeat untill every row has been deleted.

• number start vertex as 0 and draw a box around it
• number each vertex connected to the start vertex with the total distance (from start to there) [and where its from (label on the previous vertex)]
• choose the smallest unboxed number and box it.
• number the total distance to every connected vertex from the last box [and where from.] - Cross out (legibly) numbers that are already there; unless the number already there is smaller than the one you want to put (then you dont put anything). Dont go back to already boxed vertices.
• Repeat last two steps until everything has been boxed and you haved reached the end.

The shortest path would be the sum of all the lengths on the Eulerian graph.

If your graph has an odd numbered order on any vertex, it is not Eulerian. If it is Eulerian, skip this section. Making the Graph Eulerian

• list all the odd vertices, all the possible pairings of these vertices. The number of possible pairings is determined by (n-1)×(n-3)×(n-5)×.....×1
• Work out the weight that each pairing would be. (shortest path from one to the other)
• Choose the pairings with the minimum weight.
• Draw in these pairings as new edges onto the graph.

This algorithm is meant to help find the shortest/minimum route so that every vertex is visited. It only applies to complete networks.

Upper Bound Algorithm

• choose start vertex and go to nearest unvisted vertex from there.
• repeat untill all vertices have been visited, then return to beginning.

[this algorithm could also be applied to a matrix. This time, cross out the column instead of the row, so you cannot return to a previous vertex. Remember to list out the answer afterwards.] 

Lower Bound Algorithm

• delete the start vertex and all the edges connected to that
• find the minimum spanning tree for the remaining network
• add this to the two shortest edges from the start vertex.

There are four sorting algorithms that you will need to learn. Each algorithm would vary in efficiency (number of comparisons and swaps made) depending on the order of the list you are sorting.

Comparison = the number of times an item is compared with the next in each pass. Swaps = amount of posistions an item has moved in the pass.

The algorithms are written for a set of ascending numbers. It can also be used to descending numbers by doing it opposite or sorting words alphabetically.

• Compare first two numbers. The larger number moved to second, leaving behind the smaller number at the front.
• the second and third numbers are compared. The lighter number gets moved to the front.
• etc.. untill you get to the end of the row. This is known as a pass.
• repeat from beginning again untill nothing has moved (no swaps made).

[write out the number of comparisons and passes made at every pass. Show every pass made untill everything is in order, ie. no more swaps are made.]

• Compare first two numbers.
• Move larger number to second place.
• Compare first three numbers.
• Move it into position by comparing it with second, first.
• etc...untill all number have been compared.

[write out each pass and the comparisons and swaps at each one too. you will also need to underline the ones that are being compared, so on the original list the first two, then first three, first four.... etc.]

• Devide a list into n/2 sublists, ignoring any remainders. 

• Shuttle sort each list.

• Merge the sublists.

• Devide the number of sublists by 2 and repeat steps 2 and 3 until there is only one sublist.

• Use the first number as the pivot. [Box it].
• Keeping the order of the numbers, move the smaller ones infront of the pivot, keeping larger ones behind. [write this pass out]
• The first number in each sublist is now a new pivot. [Box this number]
• Repeat step 2 and 3 untill every number has been used as a pivot. [Everything is boxed]