Mathematics: Decision 1 (Notes 1 of 1)

An algorithm is a set of instructions for solving a problem. The order of an algorithm tells you how 'efficient' an algorithm is. It tells you how the time the algorithm takes to run changes as the number of input values changes.Most algorithms are general which means they work for loads of different input values, but this means that for simple cases it might not be the best method to use.Algorithms are largely used in computer programming, and setting computers working on problems which it would take too much time for people to work out by hand.An algorithm may be given in the form of a flow chart or set of instructions... (it is important to follow and take a note of EVERY step!)All algorithms must have a stopping condition otherwise they could keep repeating and repeating forever.There are two algorithms for sorting numbers into ascending, or descending order: bubble sort and shuttle sort.Instructions for the shuttle sort:1) Compare the first two numbers 2) Are they... in the right order? leave them be; ...in the wrong order? swap them. This is the first pass.3) Compare the second and third numbers4) Repeat step two5) If you make a swap compare the swapped number to the number before it and go through step 2 again. Stop comparing numbers when you reach a number that won't be swapped or you work your way back to the front of the list. This is pass two. 6) Continue comparing the next pair of numbers and swapping if necessary until you get to the last pair of numbers in the list.Instructions for the bubble sort:1) Compare the first two numbers, if they're in the right order move on, if they're in the wrong order swap them. 2) Compare the next pair of numbers (2nd and 3rd) and swap if necessary, then move on to the next pair and swap if necessary and repeat until you reach the end of the list. This is the first pass.3) If you made swaps on the last pass then go back to the beginning of the list and start again.Remember to record the number of comparisons and swaps on each pass.For both algorithms the maximum number of passes is n-1 (when n is the number of numbers being sorted). The bubble sort may finish in fewer passes than this but the shuttle sort will always need the maximum number of passes.The shuttle sort and bubble sort will both need the same number of swaps but the bubble sort is LESS efficient because you may have to do many more comparisons then necessary.There are also 2 'bin-packing' algorithms to know about - to aim of these is to pack a set of items into the minimum number of bins while not exceeding the maximum height or weight criteria in each of the bins.Instructions for first-fit:1) Put the first item in the list into the first bin.2) Put the next item in the list into the first bin it will fit into.3) Repeat step 2 until all the items are packed.This algorithm is quick and easy but is unlikely to give the right answer.Instructions for first-fit decreasing:1) Put the list of items into descending order.2) Follow the instructions for first-fit.This algorithm usually gives a better solution, but a better solution yet may be gained by working out the optimum solution yourself. If you add up the space wasted and it is more than the value one 'bin' can hold there may be a better solution..

Linear programming is a way of solving problems to find the 'optimal solution'. For example, how many of each type of cupcake should be made to give maximum profit, given a limit on the amount of flour, eggs and cooking time available. Vocabulary to know:-Decision variable - x,y,z The amount of each thing being produced.-Objective function - The thing you're trying to maximise (or minimise)-Constraints - The factors that limit the problem (non-negativity constraints are often appropriate).-Feasible solution - A solution that satisfies all the constraints.You may be asked to formulate constraints from a wordy problem - just ensure you separate out the information you're given and then work out which way around the inequality sign should go.When drawing a graph to find the feasible region (ie. if there are only two variables)  shade the area you don't want, which will leave you with an unshaded area which satisfies all the constraints.To find the optimal solution write out all the co-ordinates of the vertices of the feasible region - you may be able to see these by eye or have to solve the equations of each line that intersects simultaneously. Substitute all the co-ordinates into the objective function to get the value of the objective function at each point. Depending on if you're maximising or minimising the value the optimum value will be at the biggest or smallest number. Remember to write a statement giving x= and y=, don't just leave co-ordinates. If the optimal solution requires that x and y be integer values, calculate the function for all the vertices as above but then look for points with integer values of x and y near to the optimum vertex. Another way of calculating the optimum solution is to use the simplex method.To do this use slack variables - these are just a way of turning inequalities into equations (if you know x+y+z is less than or equal to 20 then x+y+z+some variable (s) will equal 20 - even if the variable turns out to be 0). You use a different slack variable for each inequality. The simplex method works as follows: (see example)1) Turn the inequalities into equations using slack variables. Move the variables in the objective function onto the other side of the equation to get it equal to 0.2) Set up a tableau with columns for P, x, y, z and the slack variables and a right-hand-side (RHS) column.3) Choose a pivot column - this will either be given in the question or should be the a negative value in the top row (the most negative value will tend to solve the problem quicker).4) Perform a ratio test by dividing each of the values in the RHS column by the corresponding value in the chosen pivot column. Choose the value in the pivot column which gives the smallest number in the ratio test. This is the 'pivot element'.5) Divide the whole of the pivot row by the pivot element to make the new value of the pivot one - write this new row in a new tableau below the initial tableau.6) Make all the other values in the pivot column 0 by adding or subtracting multiples of the new pivot row to each of the rows and write these in the new tableau.7) Keep repeating these steps (4,5,6) until there are no more negative values in the top row.The optimum value of P will be the RHS value in the top row.To read off the values of the variables look down the column to find the 1 and across to the RHS value (if all the values in the column are 0s). If the values in the column are all random and jumbled then that variable equals 0.This method works for the slack variables aswell - to interpret the slack variables in terms of the question look back to what that inequality represented, for example the time or the cost - if the slack variables aren't 0 it means there is spare capacity.

A graph is made up of dots (nodes/vertices) joined together by lines (arcs/edges), There are special types of graph:Connected graphs - every node is connected, directly or indirectly, to every other node.Simple graph - no node is connected to another node by more than one arc, or has an arc connecting it to itself.Directed graph - arcs may be given a direction arrow meaning that arc can only be 'travelled down' in one direction.Planar graphs - these can be arranged (on a single plane) in such a way that the arcs do not cross each other.A path is is a route in a graph which flows from the end of one arc to the start of the next and doesn't repeat any vertices.A cycle is a closed path - it ends in the same place as it starts.A tree is a graph that connects every node to every other node, directly or indirectly (ie. it is a connected graph), and has no cycles. A spanning tree is a tree which includes all the vertices.The order of a node is how many arcs are connected to it. If a node as an arc connecting it to itself this counts as two, because it is in contact with the node in two places. Nodes can be of odd or even order but the total of all the orders is always even - this is because it is double the number of arcs. In a simply connected graph with n nodes the maximum order of any node is n-1. The total orders of all the nodes is twice the number of arcs, and so is even. In any graph there are an even number of odd nodes. A graph is traversable if you can start at any point, go along every arc exactly once(without taking your pen of the paper) and end up back where you started.Eulerian graphs have this property because all the nodes have even order.A graph is semi-traversable if there is a route where you can go along every arc exactly once but only if you start and end at particular vertices.Semi-Eulerian graphs have this property because they have exactly two vertices with an odd order and the rest are even - the route must start at one of the odd vertices and end up at the other one.

A network (or weighted graph) is a graph where every edge is assigned a 'weight' - this is a number which could represent the length or number of potholes along that arc.They can be used to model or solve real-life geographical problems.There are a number of algorithms to learn which find minimum spanning trees, solve travelling salesperson problems, and find upper and lower bounds of distances between points:A minimum spanning tree  (MST) is a tree which connects all the points with the total weight of the arcs being as small as possible. There are normally so many points that seeing whether you have the MST is difficult, which is where algorithms are helpful.Prim's Algorithm1) Pick any vertex2) Choose the smallest arc which will join a vertex already in the tree to one not yet in the tree. If there are two which are equally small pick one randomly.3) Repeat until all the vertices are in the tree.To apply this to a matrix follow the same instructions adding each column to the tree and deleting rows you've already connected to - see the example.Kruskal's Algorithm1) List all the arcs in order from smallest to biggest, if there are two or more of the same length it doesn't matter which way round they go.2) Pick the arc of smallest weight to start the tree.3) Look at the next arc in the list, if it forms a cycle don't use it, if it doesn't form a cycle add it to the tree.3) Repeat until all the vertices are in the tree.You may be asked to comment on the solution in the context of a real world question;  some nodes will end up with a bigger distance between them than they had in the full graph because a direct arc has not been included so you could comment on this.The travelling salesperson problem requires that you visit every vertex in the network once and end up back at your starting point. There isn't an algorithm guaranteed to find the shortest route but there is one to find the upper bound and another to find the lower bound. The optimum route will be somewhere in between these two values (inclusive).To find an upper bound: The nearest neighbour algorithm1) Choose the starting vertex2) Connect it to the vertex with the least weight.3) Repeat step 2 until all the vertices have been connected.4) Finish the cycle by taking the direct route back to the starting vertex.If a question asks you to improve on an upper bound calculated this way by sight then look for shortcuts, eg. if taking an indirect route adds up to less than the direct route between two nodes.Like Prim's the nearest neighbour algorithm can be applied to a matrix.Sometimes the nearest neighbour algorithm doesn't work well because it chooses the best arc at one point so at the end really long nodes might be left. The algorithm also sometimes fails because you get to a point where all the nodes you could go to have already been connected to so you have nowhere to go.To find a lower bound: Minimum spanning trees1) Choose a vertex, find the two arcs with the least weight connected to that vertex, delete the vertex from the graph.2) Find a minimum spanning tree for the rest of the graph (use Prim's or Kruskal's).3) Add the weight of the minimum spanning tree to the total of the two arcs connected to the deleted vertex and this is the lower bound.If you find a route which has the same weight as the lower bound you know you've found the optimum route. If the lower bound and upper bound are the same then that value is the weight of the optimum route.The travelling salesperson problem was looking for a way to visit all the nodes and end up back at the beginning, another problem is if you wanted to travel down every single arc and return to the beginning. This is called the Chinese postman (or route inspection) problem.The route inspection algorithm:1) Pick out all the vertices with odd orders2) Find all the different ways of pairing them up and the weights of these combinations.3) Use the combination with the minimum weight. (The length of inspection route = Total weight of network + Length of extra edges)4) Add extra edges connecting each pair.5) The graph is now traversable (the added edges have made the odd nodes even) so use inspection (look) to find a route through it.Eulerian graphs: The length of inspection route = Total weight of networkThis is because Eulerian graphs are already traversable (they have no odd nodes) so you can pick any start point, travel along each edge exactly once and end up back where you started.Semi-Eulerian graphs: The length of inspection route = Total weight of network + Weight of the shortest path between two verticesThese graphs only have two odd nodes so connect them to make all the nodes even and then look for the route through it.The route inspection algorithm can also be modified for a problem when you want to start at one node and finish at a different one. To do this you have to add extra arcs such that the two nodes you are travelling between are both odd, and the other nodes are all even. This makes the graph semi-traversable and a route can be found 'by inspection'.To find the shortest path connecting two nodes Dijkstra's algorithm can be used:1) Choose the start vertex, this is the first vertex labelled so put a 1 in the order box and give this the permanent label 0.2) Give temporary labels to all the vertices it directly connects to. (The temporary label is just the permanent label at the previous vertex + the weight of the arc between them.)3) Pick the smallest temporary label and make this permanent.4) Repeat steps 2 and 3 until the end vertex has a permanent label - this gives the weight of the shortest path.5) To find the shortest path trace the route backwards working out which arcs were included by considering the difference between the permanent labels of two nodes.

Algorithms

Graph Theory

Networks

Linear Programming