Tadaa... as requested. my notes for decision1 xD woo go me. There seems to be a lower 'fact stating:word' ratio in this note, but these are my notes on decision, by chapter, with the algorithm/procedure your meant to follow and an explanation as well as the things you need to show for the method marks...i hope ive not left out anything important; if I have/you spot errors, let me know/edit this yourself. As always, practise papers help show you what your bad at and help you to learn to play the exam 'game'. woo fun. Good luck =]
["WHATT??" i hear you cry. "you said in order?" well... it helps if you know what the words i might end up using means so i'll start with chapter 5.]
Graph: finite vertices connected by edges.
Vertices/Nodes: where two separate lines meet. Usually shown with a black dot.
Edge/Arcs: lines that join up vertices/nodes. The edges/path thing.
Degree/Order/Valency: number of edges connected to a vertex.
Loop: an arc beginning and ending one the same vertex. Loops contribute 2 to the arc count.
Simple graph: A graph with no loops, no multiple edges and every vertex is connected.
Connected graph: A graph where all the points are connected. (the graph is in one piece)
Disconnected graph: If the points are not all linked into a graph. (two smaller connected graphs near each other)
Fully connected graph/Complete graph: Where every vertex is connected to every other vertex. Its total edges,(Kn) = n(n-1)/2 where n=vertices
Weighted graph: A graph where numbers are linked with the edges, representing time/distance/money etc.
Directed graph/digraph: has edges with directions. ie. one way paths.
Planar graph: One which can be drawn without any arcs intersecting. There is a complicated way of deciding if a given graph is planar, otherwise just experiment with stretching the arcs to try and remove intersections.
Adjacency matrix: a matrix (two-way table) that represents a graph where the rows and columns represent the vertices, and the number inside represents the edges joining the weight of the edges joining the vertices.
Bipartite graph: A graph with two sets of vertices where edges only connect from one subset of vertices to the other subset.
Maximum matching: The optimum matching in the bipartite graph.
Complete matching: where all the vertices in one subset connect to all the vertices in the other.
Tree: connected graph with no cycles
Spanning tree: A tree that connects all the vertices (n). It has n-1 edges.
Minimum spanning tree: A spanning tree with the minimum weight for the graph.
Trail or Walk: A sequence of edges that link up to each other through edges.
Path: A trail where no vertex is visited more than once.
Cycle or Circuit: A closed path/trail with at least one edge. (closed = finishes at start)
Hamiltonian cycle: A cycle/circuit/path/trail that visits every vertex. It has (n-1)!/2 permutations.
Eulerian trail: A trail that uses every edge of a graph (the graph would be Eulerian/traversible) It is not a path as it visits the vertices more than once, although there are exceptions e.g a hexagonal graph. Each node must have even order/valency for a graph to be Eulerian.
Traversible graph: graph with a Eulerian/semi-Eulerian trail
Semi-Eulerian: non-closed Eulerian trail (doesn't finish at the start vertex) There must be exactly 2 odd order nodes & the rest must be even. The trail must begin at one of the odd order nodes and finish at the other one.
The following algorithms are used to find the minimum spanning tree for graphs.
The order the edges are selected will be different for the two algorithms, but the minimum spanning tree will be the same whichever algorithm you use.
- 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.
[Kruskals algorithm chooses the edges in order of size; so for working/method marks, list the order of the edges that are selected and the lengths. If the new edge makes it a cycle, (therefore no longer a tree) you NEED to write it down and put a line through it (legibly). Label the last length used as n-1.]
- from the start vertex, add the lowest weight to the tree.
- from any vertex already used, choose the edge with the lowest value avoiding cycles.
- if there are n-1 edges stop. If not, repeat.
[Prim's Algorithm chooses the edges that are next to the tree already. Working for this you should include a list of the order the edges were selected, the lengths, and label n-1
For both algorithms it might be helpful to number the list of edges you selected, and add to your drawing of the tree as you go along. This will help you to spot cycles and show you stopped at n-1. If you'd excuse my bad analogies, how I remember the algorithms for the exam is kruskal = "krus"-ing out, cross out an edge. Prim = neat and tidy (so systematic, not jumping around edges)]
Matrix Form of Prim's
- On the matrix, 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. (row with start vertex)
- 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.
[careful this is not confused with the upper bound matrix. List out the order of the edges selected along with their weights.]
Shortest Path Problem (Dijkstra's Algorithm)
This algorithm finds the shortest route from one vertex to another, by considering all the posibilities.
This algorithm only applies to graphs with no negative lengths.
The algorithm can be used starting from the end vertex if there are multiple starting points.
The algorithm requires drawing on/labeling the graph.
- 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 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 (where 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 total distance is the number in the final box and the shortest route can be traced backwards from the labels.
[Another random analogy: D-J box man = Dijkstra. You draw boxes.. and his name has the letters d and j in... haha..... . . . .
Chinese Postman Problem
This algorithm finds the shortest path going along every edge. Just like how a postman has to deliver letters to every street without doubling back on himself unnecessarily.
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.
Finding the path
- list the order of each vertex (should be even by now)
- List the number of times each vertex would appear in the trail (half the orders, except the start vertex which is one more) Are you sure? Look at Jan 11 Q5C and it's answers
- Try out the path using general common sense [not much required] and check with the list.
[That finding the path method doesnt actually find you the path it's to check youve found the path, but i dont see how you would need to check... =/ but it gets you the marks so use it anyway...]
For semi-Eulerian trails where you start and end in different places, you do the same thing, but ignore the start vertex and end vertex when you pair them up to make the graph Eulerian.
The sum of the total distance of the Eulerian trail is the sum of all the edges plus the minimum pairings (not including the start and end, as the order of start vertex and end vertex is odd on semi-Eulerian trails.)
[erm i dont think i have a way of remembering this one....halve a Eulerian?]
Travelling Salesman Problem
This algorithm is meant to help find the shortest/minimum route so that every vertex is visited. It only applies to complete networks.
However, it doesnt always give you a route/answer. But you get the range that the answer could lie within. Lower bound<Answer≤Upper bound [woo...]
The upper bound of the range is an actual tour (it exsists), but it may be improved upon. (not necesarily.)
The lower bound of the range cannot be improved upon, however, it may not exsist.
When applied to each vertex, the best lower bound is one with highest length, and the best upper bound is one with the lowest length.
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.
The alternating path algorithm improves an initial matching
- Find vertex not matched.
- match it
- If you need to, remove the initial match to it
- repeat untill there are no more improvements(maximum matching)/you have got a complete matching.
[for working, use a symbol that looks something like ≠ but more like -/- to show mathings that have been removed, eg. A-F≠C-G which shows 'A' being matched to 'F' which disconnects 'C'. 'C' is then connected to 'G'. The symbol ≠ implies is not equal to, rather thank links so yeah. dont use it.It will also help to draw out the diagram after one set of unmatching and rematching, to see how your new graph looks.]
- check the book for these not gonna lie these seem a bit dodgy*
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 positions 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 until everything is in order, ie. no more swaps are made. Its called bubble as the lighter number rises to the top... but my teacher thinks it should be called dead weight as the heavy number is the one that moves... to the bottom.]
- 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...until 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. failure to come up with a weird analogy.]
- Separate into sublists using INT(n/2) this gives the number of lists to be used
- Pair up the first number in the first half with the first number in the second half, second with second etc. but keeping the order the same. [write each pair on separate lines diagonally so order can be seen.]
- Compare the pairs and shuttle sort them to get the larger number at the back.
- Merge/re-piece the list but with the numbers that have been swapped in their new positions.
- Quarter the list and do the same with each sublist.
- Repeat untill each sublist only has 1 number.
[as you will only need to write out the sublists, and then the merges the guy wont know how you sorted the sublists etc. Write out comparisons and swaps at each stage.]
- Use the first number as the pivot. [Underline it].
- Keeping the order of the numbers, move the smaller ones in front of the pivot, keeping larger ones behind. [write this pass out]
- The first number in each sublist is now a new pivot. [box the pivot you have just used and underline new ones]
- Repeat untill every number has been used as a pivot [everything is boxed] - Maybe I'm wrong but I believe that you only box the first in each sublist, until each sublist only has 1 number.
An Algorithm must have a finite number of instructions that achieves some task.
Each instruction has to be defined precisely in structured, pseudo English. This is a simplistic form of English.
Each variable value must have been inputted to solve the problem.
It must work for any set of values input.
Line numbers are used to indicate the order of instructions. They go up in multiples of 10 so that modifications can made without needing to re-number everything.
An algorithm can be represented in flowcharts. There is a certain layout/format that must be used for flowcharts. It may vary from other subjects (electronics etc.)
- Oval boxes used for start/stop/input/output.
- Square boxes for calculating/instructions/processes
- Diamond for decisions
The labels in the algorithm mark 'milestones' in the algorithm. They provide a point in the algorithm that could be jumped to.
An 'If...Then' statement is a decision. It asks a question. If true, you'll be redirected, if false continue.
'For' statements apply a loop for a range of number of inputs, e.g. 'for x=3 to 100' means the algorithm is applied for all the numbers from 3,4,5.......98,99,100.
A 'For' statement is used if the exact number of inputs is known, when it is not known, an 'If' statement is used.
Tracing Algorithms means following the algorithm out line by line manually.
List the Inputs then the Outputs along the top of a two-way table. The side is used for line numbers. Fill it out, line at a time, step by step in order.
[I dont know why labels are used, it's more convienient to say 'go to line 30' for example... also, while tracing algorithms, lines that have labels on etc. do not need to be shown. Algorithms shouldnt be too hard, they easily make sense, they use actual words...]
This is used to help optimize the situation.
Lines on the graph represent the constraints/boundaries in the situation and can be expressed as an inequality.
The feasible region is the unshaded side of the line/the excluded region.
When there is a region bounded by other lines, it is known as a finite region.
The objective of the situation, which can be expressed as an objective function which can be used to find an objective line.
The objective line can be moved [keeping the gradient] until it intersects a vertex, which is used to find the optimal value. (where it leaves the region last)
When the optimum value is found, substitute the (x,y) co-ordinates on the vertex and the objective can be worked out.
- always check that you have added up properly. eg. in minimum spanning tree etc.
- make sure the question has been actually been answered. Where is the answer? Is it clear?
- show working, ie. list vertices from the route taken from the matrix's in order.
- rest well before, dont stress out.
- Jan 2011 is the last time exam board will allow couloured pencils for working...(no hightlighters). Either get a fat pencil, or go over lines a few times on diagrams.
- keep you answers precise and clear.
- If your stuck, dont stay on the same question for too long. Decision papers can be quite long, and there are usually alot of marks towards the end.
- leaving a hard question may trigger a brain wave later on in the exam.
- as with all things, practise!