Decision Flashcards
1
Q
Algorithm - definition
A
> An algorithm is a finite sequence of step-by-step instructions carried out to solve a problem.
2
Q
Flow chart
A
> In a flow chart, the shape of each box tells you its function.
3
Q
How can unordered lists be sorted?
A
- Bubble sort
- Quick sort
>Quick sort is quicker to implement than bubble sort except when e.g. only the largest item is out of place when putting them in ascending order.
4
Q
Bubble sort
A
> In a bubble sort, you compare adjacent items in a list:
-if they are in order, leave them.
-if they are not in order, swap them.
-the list is in order when a pass is completed without any swaps.
0.5n(n-1) = (n-1) + (n-2) + … + 2 + 1.
Min passes = 1 (already in order)/
Max passes = n (if smallest item is at the end on the list).
5
Q
Quick sort
A
> In a quick sort, you select a pivot then split the items into two sub-lists:
-one sub-list contains items less than the pivot.
-the other sub-list contains items greater than the pivot.
-you then select further pivots within each sub-list and repeat the process.
nlogn
6
Q
The 3 bin-packing algorithms
A
- First-fit algorithm
- First-fit decreasing algorithm
- Full-bin packing algorithm
7
Q
First-fit algorithm
A
> The first-fit algorithm works by considering items in the order they are given.
Quick to implement.
Not likely to lead to a good solution.
8
Q
First-fit decreasing
A
> The first-fit decreasing algorithm requires the items to be in descending order before applying the algorithm.
Usually a good solution and easy to implement.
Not likely to lead to a good solution.
9
Q
Full-bin packing
A
> Full-bin packing uses inspection to select items that will combine to full bins. Remaining items are packed using the first-fit algorithm.
Usually a good solution.
Difficult to do, especially when the numbers are plentiful or awkward.
10
Q
Order of an algorithm
A
> The order of an algorithm can be described as a function of its size.
If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time of the algorithm by a factor of approximately f(m) / f(n).
If the size of a problem is increased by some factor k then an algorithm of linear order will take approx. k times as long to complete, quadratic - k^2 etc.
11
Q
Graph - description
A
> A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs).
12
Q
Weighted graph/network
A
> If a graph has a number associated with each edge (usually called its weight), then the graph is known as a weighted graph or network.
13
Q
Subgraph - definition
A
> A subgraph is a graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph.
It is part of the original graph.
14
Q
Degree/valency/order of a vertex - definition
A
> The degree (or valency or order) of a vertex is the number of edges incident to it.
If the degree of a vertex is even, you say that it has even degree.
If the degree of a vertex is odd it has odd degree.
15
Q
Walk - definition
A
> A walk is a route through a graph along edges from one vertex to the next.
16
Q
Path - definition
A
> A path is a walk in which no vertex is visited more than once.
17
Q
Trail - definition
A
> A trail is a walk in which no edge is visited more than once.
18
Q
Cycle - definition
A
> A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
19
Q
Hamiltonian cycle - definition
A
> A Hamiltonian cycle is a cycle that includes every vertex.
20
Q
Connected
A
> 2 vertices are connected if there is a path between them.
>A graph is connected if all its vertices are connected.
21
Q
Loop - definition
A
> A loop is an edge that starts and finishes at the same vertex.
22
Q
Simple graph - definition
A
> A simple graph is one in which there are no loops and there is at most one edge connecting any pair of vertices.
23
Q
Directed graph - definition
A
> If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a directed graph (or digraph).
24
Q
Euler’s handshaking lemma
A
> In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges.
As a consequence, the number of odd nodes must be even.
This result is called Euler’s handshaking lemma.
Any vertices of odd degree must therefore ‘pair up’.
25
Tree - definition
>A tree is a connected graph with no cycles.
26
Spanning tree - definition
>A spanning tree of a graph is a subgraph which includes all the vertices of the original graph and is also a tree.
27
Complete graph - definition
>A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices.
28
Isomorphic graph - definition
>Isomorphic graphs are graphs which show the same information but may be drawn differently.
29
Adjacency matrix
>Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices.
30
Distance matrix
>In a distance matrix, the entries represent the weight of each arc, not the number of arcs.
31
Planar graph - definition
>A planar graph is one that can be drawn in a plane such that no two edges meet except at a vertex.
32
Planarity algorithm
>The planarity algorithm may be applied to any graph that contains a Hamiltonian cycle.
>It provides a method of redrawing the graph in such a way that it becomes clear whether or not it is planar.
33
Kn
>Complete graph with n vertices.
34
Q. Total no. off edges of K20
>190
>0.5n(n-1)
>0.5 x 20 x 19 = 190
35
Q. Edges in spanning tree with v vertices
>v-1
36
Q. Why can't there be a graph with 4 vertices of degrees 3, 1, 1, 2?
> 3+1+1+2 = 7 = odd.
| >Sum of the degrees of the vertices must be even.
37
Minimum Spanning Tree - definition
>A minimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as possible.
38
Kruskal's Algorithm
>Kruskal's algorithm can be used to find a MST.
>Sort the arcs into ascending order of weight and use the arc with the least weight to start the tree.
>Then add arcs in order of ascending weight, unless an arc would form a cycle, in which case reject it.
39
Prim's algorithm
>Prim's algorithm can be used to find a MST.
>Choose any vertex to start the tree.
>Then select an arc of least weight that joins a vertex already in the tree to a vertex not yet in the tree.
>Repeat this until all vertices are connected.
40
Prim's algorithm and distance matrices
>Prim's algorithm can be applied to a distance matrix.
>Choose any vertex to start the tree.
>Delete the row in the matrix for the chosen vertex and number the column in the matrix for the chosen vertex.
>Ring the lowest undeleted entry in the numbered columns, which becomes the next arc.
>Repeat this until all rows are deleted.
41
Dijkstra's algorithm
>Dijkstra's algorithm can be used to find the shortest path between two vertices in a network:
-label the start vertex with final value 0.
-record a working value at every vertex, Y, that is directly connected to the vertex that has just received its final label, X: final label at X + plus weight of arc XY.
-select the smallest working value. This is the final label for that vertex.
-repeat until the destination vertex receives its final label.
-find the shortest path by tracing back from destination to start. Include an arc AB on the route if B is already on the route and final label B - final label A = weight of arc AB.
>Each vertex is replaced by a box.
42
What does Dijkstra's algorithm do and when is it used?
>Dijkstra's algorithm finds the shortest route between the start vertex and each intermediate vertex completed on the way to the destination vertex.
>It is possible to use Dijkstra's algorithm on networks with directed arcs, such as a route with one-way streets.
43
Floyd's algorithm
>Floyd's algorithm can be used to find the shortest path between every pair of vertices in a network:
>Floyd's algorithm applied to a network with n vertices produces two tables as a result of n iterations.
>One table shows the shortest distances and the other contains information about the corresponding paths taken.
44
Q. Why don't you need to check for cycles when using Prim's?
>Prim's algorithm identifies the next node to link to the existing tree. Linking a new node can't form a cycle.
45
Q. Why isn't this MST unique?
>E.g. AB can be replaced with AT as they both have the same weight of 10.
46
Q. Explain the differences between Prim's and Kruskal's.
1. In Prim's the starting point can be any node, but Kruskal's starts from the arc of least weight.
2. In Prim's, each new node is added to the existing tree as it builds, whereas in K, the arcs are selected according to their weight and may not be connected until the end.
47
Q. Workout the no. of comparisons required for an n x n distance matrix (Prim's) and state the order in terms of number of vertices, n.
>Starting with an n x n matrix, the row corresponding to the starting vertex is crossed out, leaving n - 1 values in the corresponding column.
>The smallest of these is to be found. This requires (n - 1) - 1 comparisons.
>At each stage, the number of columns included increases by 1 and the number of values remaining in each of those columns reduces by 1.
>The total number of comparisons required to complete the algorithm is given by:
> ((n - 1) x 1 - 1) + ((n-2) x 2 - 1) + ((n-3) x 3 -1) +...+ ((n-(n-1)) x (n - 1) - 1).
>Which is sigma (n-1 on the top and r=1 on the bottom) followed by ((n-r) x r -1) = nr - r^2 - 1.
>n(0.5(n-1)n) - 1/6(n-1)n(2n-1) - (n-1).
>(n^3 - 7n + 6)/6
>Order = n^3.
48
Q. Explain the difference between the output of Dijkstra's algorithm and Floyd's algorithm
>The output of Floyd's algorithm gives the shortest distance between every pair of nodes.
>The output of Dijkstra's algorithm gives the shortest distance from the start node to every other.
49
Tables used in Floyd's
1. Route table
| 2. Distance table
50
Q. Floyd's algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration and give the order of Floyd's algorithm.
> (n-1)(n-2) = n^2 -3n +2.
| >Cubic.
51
Q. For any connected network, e = no. of edges in the MST and v = no. of vertices in the network. Write down the relationship between e and v.
e = v-1.
52
Q. Explain why time found in part c is only an estimate
>The time required is not directly proportional to n^3 but this is used as an approximation.
53
Eulerian graph - definition
>An Eulerian graph or network is one which contains a trail that includes every edge and starts and finishes at the same vertex.
>This trail is called an Eulerian circuit.
>Any connected graph whose vertices are all even is Eulerian.
54
Semi-Eulerian graph - definition
>A semi-Eulerian graph or network is one which contains a trail that includes every edge but starts and finishes at different vertices.
>Any connected graph with exactly 2 odd vertices is semi-Eulerian.
55
The route inspection algorithm - info
>The route inspection algorithm can be used to find the shortest route in a network that traverses every arc at least once and returns to its starting point.
>If all the vertices in the network have even degree, then the length of the shortest route will be equal to the total weight of the network.
>If a network has exactly 2 odd vertices, then the length of the shortest route will be equal to the total weight of the network, plus the length of the shortest path between the 2 odd vertices.
>If the network has more than 2 odd vertices, then you need to consider all the possible pairings of odd vertices.
>Also known as the Chinese postman algorithm.
56
Route inspection algorithm - steps
1. Identify any vertices with odd degree.
2. Consider all possible complete pairings of these vertices.
3. Select the complete pairing that has the least sum.
4. Add a repeat of the arcs indicated by this pairing to the network.
57
Walk - definition 2
>A walk in a network is a finite sequence of edges such that the end vertex if one edge is the start vertex of the next.
58
Tour - definition
>A walk which visits every vertex, returning to its starting vertex, is called a tour.
59
Variations of the travelling salesman problem
>There are 2 variations of the travelling salesman problem.
>In the classical problem, each vertex must be visited exactly once before returning to the start.
>In the practical problem, each vertex must be visited at least once before returning to the start.
60
Triangle inequality
>The triangle inequality states:
| - the longest side of any triangle《 the sum of the two shorter sides.
61
Methods to find upper bound for the travelling salesman problem
1. MST method
| 2. Nearest neighbour algorithm
62
Methods to find lower bound for the travelling salesman problem
1. MST method
63
MST method - upper bound - travelling salesman problem
>You can use a minimum spanning tree method to find an UB for the practical salesman problem.
>Find the MST for the network (using Prim's or Kruskal's algorithm).
>An initial UB for the practical travelling salesman problem is found by finding the weight of the MST for the network and doubling it.
>You can improve the initial upper bound by looking for shortcuts.
>Aim to make the UB as low as possible to reduce the interval in which the optimal solution is contained.
64
MST method - lower bound - travelling salesman problem
>You can use a MST method to find a LB from a table of least distances for the classical problem.
>Remove each vertex in turn, together with its arcs.
>Find the residual minimum spanning tree (RMST) and its length.
>Add to the RMST the 'cost' of reconnecting the deleted vertex by the two shortest, distinct arcs and note the totals.
> The greatest of these totals is used for the LB.
>Make the LB as high as possible to reduce the interval in which the optimal solution is contained.
>You have found an optimal solution if the LB gives a Hamiltonian cycle, or the LB has the same value as the UB.
>If you are solving the practical problem you need to apply the algorithm to a table of least distances.
65
Nearest neighbour algorithm- upper bound - travelling salesman problem
>You can use the nearest neighbour algorithm to find an upper bound.
>Select the vertex in turn as a starting point.
>Go to the nearest vertex which has not yet been visited.
>Repeat step 2 until all vertices have been visited and then return to the start vertex using the shortest route.
>Once all vertices have been used as the starting vertex, select the tour with the smallest length as the UB.
66
Complete network of least distances
>If you convert the network into a complete network of least distances, the classical and practical salesman problems are equivalent.
>To create a complete network of least distances you ensure that the triangle inequality holds for all triangles in the network.
>The distance matrix for a complete network of least distances us called a table of least distances. It shows the shortest path between any two points in the network.
67
Residual minimum spanning tree
>The RMST is the minimum spanning tree for the resulting network after removing vertex.
68
Q. Select the better LB giving a reason for your answer.
Better LB is '50' because it is higherm
69
Why can the nearest neighbour algorithm be better than MST method?
>Can be hard to use MST for large networks.
>In general, selecting shortcuts is difficult and time consuming when there are lots of vertices to consider.
>However, the last 2 arcs are 'forced' on you and can both be long arcs.
70
What does the UB given by the nearest neighbour algorithm represent?
>A possible tour.
71
Formulating a problem as a linear programming problem
>To formulate a problem as a linear programming problem:
- define the decision variable (x, y, z, etc.)
- state the objective (maximise or minimise, together with an algebraic expression called the objective function)
- write the constraints as inequalities.
72
Feasible region - definition
>The region of a graph that satisfies all the constraints of a linear programming problem is called the feasible region.
73
How do you solve a linear programming problem?
>You need to find the point in the feasible region which maximises or minimises the objective function.
74
How do you solve a linear programming problem? Maximum point
>For a maximum point, look for the last point covered by an objective line as it leaves the feasible region.
75
How do you solve a linear programming problem? Minimum point
>For a minimum point, look for the first point covered by an objective line as it enters the feasible region.
76
Vertex method
>To find an optimal point using the vertex method:
-first find the coordinates of each vertex of the feasible region.
-evaluate the objective function at each of these points.
-select the vertex that gives the optimal value of the objective function.
>If a linear programming problem requires integer solutions, you need to consider points with integer coordinates near the optimal vertex.
77
Decision variables - definition
>The decision variables in a linear programming problem are the numbers of each of the things that can be varied.
78
Objective - definition
The objective is the aim of the problem.
79
Constraints - definition
>The constraints are the things that will prevent you making, or using, an infinite number of each of the variables.
>Each constraints will give rise to one inequality.
80
Feasible solution - definition
>If you find values for the decision variables that satisfy each constraint you have a feasible solution.
81
Optimal solution - definition
>The optimal solution is the feasible solution that meets the objective.
>There might be more than one optimal solution.
82
Q. They need at least twice as many eggs as flours - inequality
```
> let x = eggs
> let y = flour
> 2y 《 x
```
83
Locating optimal point - methods
1. Objective line/ruler method.
| 2. Vertex testing method.
84
Q. Coordinates the the objective line P=2x + y
(0, 2)
| 1, 0
85
Inequalities and equations
>Inequalities can be transformed into equations using slack variables (so called because they represent the amount of slack between an actual quantity and the maximum possible value of that quantity).
86
Simplex method
>The simplex method allows you to:
- determine if a particular vertex, on the edge if the feasible region, is optimal.
- decide which adjacent vertex you should move to in order to increase the value of the objective function.
87
Slack variables
>Slack variables are essential when using the simplex algorithm.
>They represent the amount of slack between an actual quantity and the maximum possible value of that quantity.
88
Simplex method
>The simplex method starts from a basic feasible solution, at the origin, and then progresses with each iteration to an adjacent point within the feasible region until the optimal solution is found.
89
Solving a maximising linear programming problem using simplex tableau
>To use a simplex tableau to solve a maximising linear programming problem, where constraints are given as inequalities:
1. Draw the tableaux. You need a basic variable column on the left, one column for each variable (including the slack variables) and a value column. You need one row for each constraint and the bottom row for the objective function.
2. Create the initial tableau: enter the coefficients of the variables in the appropriate column and row.
3. Look along the objective row for the most negative entry: this indicates the pivot column.
4. Calculate theta for each of the constraint rows where theta = (the term in the value column)/(the term in the pivot column).
5. Select the row with the smallest, positive theta value to become the pivot row.
6. The element in the pivot row and pivot column is the pivot.
7. Divide all of the elements in the pivot row by the pivot, and change the basic variable at the start of the row to the variable at the top of the pivot column.
8. Use the pivot row to eliminate the pivot's variable from the other rows: this means that the pivot column now contains one 1 and zeros.
9. Repeat bullets 3 to 8 until there are no negative numbers in the objective row.
10. The tableaus is now optimal and the non-zero values can be read off using the basic variable column and value column.
90
Solving a minimising linear programming problem using simplex tableau
>The steps for solving a minimising linear programming problem are identical to those for a maximising one apart from:
- first, define a new objective function that is the negative of the original objective function.
- after you have maximised this new objective function, write your solution as the negative of this value, which will minimise the original objective function.
91
Solving tableau with integers
>When integer solutions are need, test points around the optimal solution to find a set of points which fit the constraints and give a maximum for the objective function.
92
Two-stage simplex method
>The two-stage simplex method for problems that include >/ constraints:
1. Use slack, surplus and artificial variables, as necessary, to write all the constraints as equation.
2. Define a new objective function to minimise the sum of all the artificial variables.
3. If the minimum sum of the artificial values is 0 then the solution found is a basic feasible solution of the original problem, which is then the starting point for the second stage. Use the simplex method again to solve this problem.
4. If the minimum sum of the artificial variables isn't 0 then the original problem has no feasible solution.
93
Linear programming problem with >/ constraints
>Linear programming problems that include >/ may also be solved using the Big-M method instead of the two-stage simplex method.
>The Big-M method uses an arbitrarily large number, M, in the objective function.
>Its purpose is to drive the artificial variables towards 0.
94
M - definition
>An arbitrarily large number.
| >Its purpose is to drive the artificial variables towards 0.
95
Big-M method
>The Big-M method uses the following steps:
1. Introduce a slack variable for each constraint in of the form /.
3. For each artificial variable a1, a2, a3 ... subtract M(a1+a2+a3 ...) from the objective function, where M is an arbitrarily large number.
4. Eliminate the artificial variables from your objective function so that the variables remaining in your objective are non-basic variables.
5. Formulate an initial tableau, and apply the simplex method in the normal way.
96
Basic feasible solution - definition
>All the constraints are satisfied, but applying the simplex method will lead to an improved solution.
97
Why do you pivot on the largest negative value?
>Because you found that by increasing e.g. 'x' initially was the most effective way to increase profit.
98
How do you know when the simplex method is complete?
>There are no negative values in the objective row.
| >I.e. increasing the value of any value will only decrease profit.
99
Q. Verify your solution - simplex
>Insert values into objective function and then into the constraints and ensure they are satisfied.
100
Q. Use the profit equation you wrote down to explain why your final tableau is optimal.
>If we rearrange the profit equation, making P the subject we get:
> P = 20 - 2z - y - s.
>Increasing z, y or s would decrease profit, so the solution is optimal.
101
Q. Simplex. If the optimal solution is when P=45, x=0, y=2.5 and z=15/8, which points should you test if you want an integer solution?
```
> (0, 2, 1)
> (0, 2, 2)
> (0, 3, 1)
> (0, 3, 2)
>Check they fit constraints and so are in the feasible region. If they are then insert into the initial objective function.
```
102
I =
-(a1 + a2 + ...)
103
How do you know when to move onto 2nd stage of simplex?
>I = 0 and there are no negative values in the I row so a basic feasible solution has been found for the original problem.
>If I doesn't equal zero when there are no negative values in the bottom row then the original problem has no feasible solution.
104
Surplus variable - definition
>Surplus variables represent the amount by which the actual quantity exceeds the minimum possible value of that quantity.
105
Artificial variable - definition
>Artificial variables are added to >/ constraints so that s>/ and a basic feasible solution can be found.
106
Q. State with a reason which value you would use as a pivot and explain how you would carry out one iteration of the algorithm.
>The most negative value in the objective row is -(60+6M) in the z column.
>The smallest positive theta value for the z column is 200 in either the a1 or a2 row so either 1 or 5 can be used as the pivot.
>Divide all elements in the chosen pivot row by the pivot value.
>Use the pivot row to eliminate the pivot's variable from all other rows, such that the pivot column now contains 1s and 0s.
>Repeat until there are no negative values in the objective row.
107
When is big M not feasible?
>The solution given by this tableau is not feasible because a2 = 5.5 is an artificial variable which must be zero in a feasible solution.
108
Precedence/dependence table - definition
>A precedence table, or dependence table, is a table that shows which activities must be completed before others are started.
109
Activity network
>In an activity/arc network, the activities are represented by arcs and the completion of those activities, known as events, are shown as nodes.
>Each arc is labelled with an activity letter.
>The beginning and end of an activity are shown at the ends of the arc and an arrow is used to define the direction. The convention is to use straight lines for arcs.
>The nodes are numbered starting from 0 for the first node, which is called the source node.
>Number each node as it is added to the network.
>The final node is called the sink node.
110
Dummy activity
>A dummy activity has no time or cost.
| >Its sole purpose is to show dependencies between activities.
111
Rules for activites
>Every activity must be uniquely represented in terms of its events.
>This require that there can be at most one activity between any two events.
112
Duration
>The length of time an activity takes to complete is known as its duration.
>You can add weights to the arcs in an activity network to represent these times.
113
Early event time
>The early event time is the earlies time of arrival at the event allowing for the completion of all preceding activities.
>The early event times are calculated starting from 0 at the source node and and working towards the sink node.
>This is called a forward pass/scan.
114
Late event time
>The late event time is the latest time that the event can be left without extending the time needed for the project.
>The late event times are calculated starting from the sink node and working backwards towards the source node.
>This is called a backward pass/scan.
115
Critical activity
>An activity is described as a critical activity if any increase in its duration results in a corresponding increase in the duration of the whole project.
116
Critical path
>A path from the source node to the sink node which entirely follows critical activities is called a critical path.
>A critical path is the longest path contained in the network.
>At each node (vertex) on a critical path the early event time is equal to the late event time.
117
Is an activity connecting 2 critical events a critical activity?
>Not necessarily.
118
Total float
>The total float of an activity is the amount of time that its start may be delayed without affecting the duration of the project.
>Total float = latest finish time - duration - earliest start time.
>The total float of any critical activity is 0.
119
Gantt (cascade) chart
>A Gantt chart provides a graphical way to represent the range of possible start and finish times for all activities on a single diagram.
120
Workers
>You need to be able to consider the no. of workers needed to complete a project. You will be told the number of workers that are needed for each activity.
1. No worker can carry out more than one activity simultaneously.
2. Once a worker, or workers, have started an activity, they must complete it.
3. Once a worker, or workers, have finished an activity, they immediately become available to start another activity.
121
Resource levelling
>The process of adjusting the start and finish times in order to take into account constraints on resources is called resource levelling.
122
Scheduling a project
>When you are scheduling a project:
- you should always use the first available worker
- if there is a choice of activities for a worker, assign the one with the lowest value for its late time.
123
Lower bound - workers
>The lower bound for the number of workers needed to complete a project within its critical time is the smallest integer greater than or equal to:
(sum of all of the activity times)/(critical time of the project).
124
Q. Explain why a dummy is needed x2
1. Because S depends only on P but T depends on both P and Q.
2. So that S and R don't share a start and end event, i.e they are uniquely represented.
125
Gantt charts - number scale
>The number scale shows elapsed time.
>So, the first hour is shown between 0 and 1 on the scale. Th second hour is shown between 1 and 2 and so on.
>The critical activities are shown as rectangles in a line at the top.
>The total float of each activity is represented by the range of movement of its rectangle on the chart.
126
Resource histogram
>A resource histogram shows the number of workers that are active at any given time.
>The convention, when constructing the diagram, is to assume that each activity starts at the earliest possible time.
>However, once drawn, it may be possible to use the diagram to identify which activities may be delayed in order to minimise the number of workers needed.
