Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
25 Cards in this Set
- Front
- Back
|
First Fit Algoritum |
Taking the boxes in the order listed, place the next box to be packed in the first available slot that can take that box. |
|
|
First-Fit Decreasing Algorithm |
1) Re-order the boxes in order of decreasing size. 2) Apply the First-Fit algorithm to this reordered list. |
|
|
Bubble Sort |
Passes: the first number in the list is compared with the second and whichever is smaller assumes the first position and so on till end of list then end pass. First Number in Correct Place second pass excludes first number |
|
|
Shuttle Sort |
Passes: Compare first two numbers – swap if necessary – rewrite the remainder of the list end pass. Compare second and third number – swap if necessary – rewrite the remainder of the list. Now compare the first two numbers –swap if necessary and re-write the list....IF not swap needed start the next pass |
|
|
Maximum number of comparisons/swaps |
n(n – 1)/2 |
|
|
List Definatly sorted after |
(n-1)th pass |
|
|
Solving Linear Programming Problem |
- Draw all lines on graph - use inequalitys to eliminate areas - discover the fesable Reagon usually the uneliminated area |
|
|
Hamilton Cycle |
– visits every vertex once (and only once apart from the first/last vertex)) – starts and finished at the same vertex – does not use any edges more than once (does not need to include every edge) |
|
|
KRUSKALS - Minimum Spanning |
1) List the edges in ascending order of size/weight 2) Choose the smallest edge 3) Choose the next smallest edge 4) Keep selecting edges in order of size but ignore any that would make a loop. |
|
|
PRIMS Graph - Minimum Spanning |
1) Choose the smallest edge (or the starting point given) 2)Find the smallest edge that is joined to your first choice edge 3) You can only choose edges that connect to the tree already drawn – always choose the smallestavailable – UNLESS it forms a loop 4) Continue until all the nodes are connected |
|
|
PRIMS Table - Minimum Spanning |
1) Choose a starting vertex and delete all elements in that vertex’s row and highlight its column 2) Neglecting all deleted terms, scan all highlighted columns for the lowest available element andcircle that element 3) Delete the circled element’s row and highlight its column 4) Repeat steps 2 and 3 until all rows deleted 5) The spanning tree is formed by the circled arcs |
|
|
DIJSKTRAS - Shortest route |
- Label your starting point 0 and draw a box round it 0
- Look at the vertices connected to your boxed node and label all of them with the distance from start -Choose the smallest label and ‘box it in’ then look at nodes connected to this point - Continue until all nodes are boxed, do not stop just because you may have reached the destination |
|
|
CHINESE POSTMAN (Route inspection problem) |
Travels along every Arc at least once before returning to the start in the minimum distance. - list all of the odd nodes in the network - List the different ways in which the odd nodes could be paired and find the Lowest Weight connection between each of the pairs - choose the pairing which gives the smallest total -add together all of the weights in the network plus additional edges found |
|
|
Travelling Salesman (Lower Bound) |
-delete one of the vertices (often told which one) -find a minimum spanning tree (Kruskals or Prims) for the remaining vertices -add to the spanning tree to weights of the two smallest edges from the deleted vertex |
|
|
Nearest Neighbour (upper Bound) |
- choose a starting node (may be given in the question) - join this node to the nearest node - join your new node to the nearest node (as long as it hasn’t already been used) - when you have included all nodes join the last node you picked back to the start |
|
|
Tree |
- a graph with no cycles. |
|
|
Simple graph |
- a graph with no loops or multiple edges |
|
|
A path |
- a route from one vertex to another which does not repeat any edge. |
|
|
A cycle |
– a route starting and finishing at the same vertex. |
|
|
Connected graph |
– a graph in which there is a route from each vertex to any other vertex |
|
|
Complete graph |
– a simple graph in which every pair of vertices is connected by an edge. |
|
|
Planar graph |
– one which can be drawn with no edges crossing. |
|
|
Eulerian cycle |
– a cycle that travels along every edge of the graph |
|
|
Eulerian graph |
– a graph with no odd vertices. |
|
|
The Simplex Algorithm |
1.Represent the problem in a tableau. 2.Use the objective row to find the pivot column. 3.Use the ratio test to find the pivot element. 4.Divide through the pivot row by the pivot element. 5.Add/subtract multiples of the transformed pivot row to/from the other rows to create zeros in the pivot column. 6.Repeat until no negatives in objective row. 7.Read the solution from the table |
