Key Facts for D1 (OCR)
1. Algorithms
An algorithm is a finite set of instructions for solving a problem. The computer or person can obtain the answer without understanding the underlying mathematics, which has been worked out by someone else.
Algorithms can be presented in standard English prose, or pseudo code (programming language) or as a flow diagram.
In the case of code much use is made of the operator := which means becomes or is replaced by. So a := a + 1 means that one is added to the value of a. a is called a variable.
For flow diagrams
Oval boxes represent the start, end and input and output of data
Rectangular boxes are used for calculations or instructions.
Diamonds are used for questions the answer to which causes branches.
Bubble Sort
The bubble sort algorithm sorts a list into ascending (or descending) order. The first and second elements are compared and swapped if necessary. Then the second and third etc until the list is exhausted. This process is repeated until the whole list has been processed without any swaps occurring.
Shuttle Sort
The shuttle sort is rather similar except that each time a swap is made the process continues working backwards towards the start of the list.
First fit
Take the objects in the order given. Place each in the first available bin
First Fit Ascending
Sort the list into ascending order then do a first fit algorithm
First Fit Descending
Sort the list into descending order then do a first fit algorithm.
The efficiency of an algorithm is a measure of the computer run time required compared to the size of the problem. It depends on the total number of operations.
The order of an algorithm is a measure of how the efficiency changes with increasing problem size. If the number of operations increases linearly with the problem size then the order is one (or linear). If it depends on n2 then the order is two (or quadratic). The time to run the algorithm then depends on the square of the problem size. If the number depends on n! or 2n then the order is said to be exponential and the times become very large quite quickly.
2. Graphs and Networks
A graph consists of nodes (vertices) and arcs (edges).
A simple graph has no loops or multiple arcs.
A sub graph is a smaller set of the nodes and arcs that make up a graph
In a complete graph, represented as Kn each of the n nodes is connected to all the other nodes.
A bipartite graph, represented as Krs has two sets of nodes r and s. Arcs only connect the set r with the set s – not necessarily completely.
A trail is a sequence of continuous arcs.
A path is a trail where no node is repeated.
A closed path has the same finishing node as the starting node.
A cycle is a closed path with no repeated node and no arc used more than once.
The order of a node is the number of arcs connected to it.
A connected graph has a path (not necessarily direct, between every node.
A connected graph is Eulerian if every node is of even order.
A connected graph is semi Eulerian if all but two nodes are even.
An Eulerian graph is traversable (can trace it without taking pencil off paper). If semi Eulerian then the start sand end nodes must be the odd nodes.
Planar graphs can be drawn without any arc crossing any others. When this is the case the Eulerian relationship holds R + N = A + 2
where R is the number of regions, N the nodes and A the arcs.
Arcs can be given weights in which case we have a weighted graph or a network. The weights usually represent distances or costs etc.
Networks can be represented by matrices.
3. Minimum Connector problems
Any tree connecting all of the nodes of a graph is called a spanning tree.
For a tree with n nodes there are n-1 arcs in a spanning tree.
The tree with the least weight is the minimum spanning tree.
Prim’s Algorithm can be used to find the minimum spanning tree T.
Select any node to start with. This is the start of T. Add to it the arc with least weight that adds a node not yet in T. Repeat until all nodes are included. If two or more arcs have the same weight then chose any one of them.
This can also be achieved in matrix form, which would be the implementation used on a computer.
Chose any column to start with. Cross out the corresponding row. Select the arc with least weight out of all the columns so far selected but not yet in a row crossed out. This becomes the new selected column. Continue till all of the nodes are included.
Kruskals Algorithm is an alternative.
Make a list of all the arcs in order of increasing weight. Start with the arc of least weight. Add to the arcs already chosen the arc of next most weight that does not make a loop with those already chosen. Continue till all nodes have been added. If two or more arcs have the same weight chose any one as the selected arc.
4. Finding the Shortest Path
This relies on Dijkstra’s algorithm
1. Label the start node with zero and box this label.
2. Consider the node with the most recently boxed label. Let the node be X and the label D. Consider each node Y connected to X but not yet permanently labelled. For each such node label it with the lesser of D plus the weight of the arc XY and the previous temporary label.
3. Choose the least of all temporary labels in the network and make its label permanent.
4. Repeat steps 2 and 3 until all the nodes are labelled.
5. Go backwards through the network retracing the path from the end to the start. The shortest path from the start to each of the network nodes has now been found.
Dijkstra cannot deal with negative weights or the longest route problem.
5. Route Inspection
The problem is to traverse every arc once only and arrive back at the start. This is easy if all the nodes are even i.e. if the graph is Eulerian. Otherwise the Chinese Postman algorithm must be used.
Find all the nodes of odd order
For each pair of nodes find the connecting path with minimum weight
Pair up the odd nodes so that the sum of the weights from step 2 is minimised.
Duplicate the paths found above.
Find a path containing every arc for the new Eulerian graph found above.
6. The Travelling Salesman Problem (TSP)
A Hamiltonian cycle is a tour that every node once and once only. Many graphs do not have Hamiltonian cycles as given. They can be replaced by complete graphs where non directly connected nodes are replaced by single arcs of the actual minimum distance between the nodes. The problem is then to find the Hamiltonian cycle of least weight for the modified graph. In practice this would involve visiting some nodes more than once.
Unfortunately the problem is exponential in order. So we concentrate on finding reasonably good solutions not the optimum.
Nearest Neighbour Algorithm (a greedy algorithm)
Choose any starting point
Consider the arcs which join the previously chosen nodesa to not yet chosen nodes. Pick one with minimum weight. Choose this arc and the associated node to join the cycle.
Repeat the above until all nodes have been chosen.
Add the arc that joins the last to the first nodes.
The Lower Limit
Chose an arbitrary node say X. Find the total of the two smallest weights of arc incident at X.
For the network without X and all arcs incident to X find the weight of the minimum connector.
The sum of the two totals is the lower bound.
The nearest neighbour algorithm can often be improved by tour improvement.
Tour Improvement.
Let I = 1
Label:
If d(Vi,Vi+2) + d(Vi+1,Vi+3) < d(Vi,Vi+1) + d(VI+2,Vi+3) then swap Vi+1 and Vi+2
I = I +1
If I < n then go back to label
Only very simple tour improvement would be set in the exam.
7. Linear Programming
This as all about optimising problems when subject to constraints like:
Optimise P = x + y
Subject to
2x + y <= 16
2x + 3y <= 24
x >= 0
y >= 0
x and y are known as control variables.
P is called the objective function
If there are only two variables these problems can be solved graphically by plotting the inequalities and shading the non-allowed region. The optimum will always be at a vertex defining the allowed region. Just work out the objective function at each vertex and take the optimum.
If an integer solution is required but a real one has been found then you must explore around the solution found. You have to believe that the optimum will be close to the non-integer solution.
8. The Simplex Algorithm
The simplex algorithm is a procedure for solving linear programming problems without drawing graphs. It is therefore used in computer programmes for their solution.
Formulate the problem as a tableau using slack variables – which must be arranged so that they are >= 0
Ensure that all elements in the last line are non zero – except possibly the first.
Label:
Select any column whose top element is negative. By tradition the most negative is chosen. This is the pivot column.
Divide the element in the last column by the element in the selected column and chose the element with the least result. This is the pivot.
Divide the row by the pivot element so that the element becomes 1.
Combine multiples of this row with the other rows so that the other elements in the row become zero.
If all the elements in the top row are positive then stop. Otherwise chose another pivot and go to Label.
The last column contains the value of the objective function and the non zero variables.
Example
P x y s t l Equation
1 -7 -11 0 0 0 1
0 2 4 1 0 60 2
0 3 3 0 1 60 3
------
1 0 -4 0 7/3 140 4 = 1 + (7/3 x 3)
0 0 2 1 -2/3 20 5 = 2 – (2/3 x 3)
0 1 1 0 1/3 20 6 = (1/3 x 3)
------
1 0 0 2 1 180 7 = 4 + (2 x 5)
0 0 1 ½ -1/3 10 8 = (1/2 x 5)
0 1 0 -1/2 2/3 10 9 = 6 – (1/2 x 5)
------
At the end of each pivot the table can be interpreted as follows:
The columns containing just 0s and a single 1 correspond to basic variables. Put the basic variables equal to the value in the final column corresponding to the row with the single 1. The rest of the variables take the value zero. This turns out to be equivalent to travelling round the vertices in the graphical solution in order. The direction of travel is unknown but depends on the initial choice of the pivot column.
This means that P = 180 when x = 10 and y = 10
That’s all folks
Good luck
Richard Vincent
11th October 2005