Rest of Decision Flashcards
What is an algorithm?
A finite sequence of step-by-step instructions carried out to solve a problem
What does an oval shaped box mean in a flow chart?
The start/end
What does a rectangular box mean in a flowchart?
It’s an instruction
What does a diamond shaped box mean in a flowchart?
A decision
Describe how to carry out 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
Describe how to carry out 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 from within each sub list and repeat the process
What are the three bin packing algorithms?
First fit
First fit decreasing
Full bin
Describe how to carry out first fit bin packing
Take the items in the order given
Place each item in the first available bin that can take it. Start from bin one each time
What is the advantage/disadvantage of first fit bin packing?
Ad: It is quick to implement
Dis: It is not likely to lead to a good solution
Describe how to carry our first fit decreasing bin packing
Sort the items so that they are in descending order
Apply the first fit algorithm to the re-ordered list
What are the advantages/disadvantages of first fit decreasing bin packing?
Ad: You usually get a fairly good solution. It is easy to implement
Dis: You may not get an optimal solution
Describe how to carry out full bin packing
Use observation to find combinations of items that will fill a bin. Pack these items first.
Any remaining items are packed using the first fit algorithm
What are the advantages/disadvantages of full bin packing?
Ad: You usually get a good solution
Dis: It is difficult to do, especially when the numbers are plentiful and awkward
What is the order of an algorithm?
Tells you how changes in the size of a problem affect the approximate time taken for its completion
What order is bubble sort?
Quadratic: 0.5(n-1)n
In any undirected graph, the sum of the degrees of the vertices equals…?
2 x the no. of edges
What is Euler’s handshaking lemma?
The number of orders vertices must be even, including possibly zero
What is a planar graph?
One that can be drawn in a plane such that no two edges meet except at a vertex
What is a minimum spanning tree?
A spanning tree such that the total length of it arcs is as small as possible
Which algorithms find the minimum spanning tree?
Kruskal’s (list all edges) and Prim’s (either pick one node on the graph, and find MST. Or use distance matrix)
What is the main difference between Kruskal’s and Prim’s?
Kruskal’s looks at edges
Prim’s looks at nodes
What can Dijkstra’s algorithm be used for?
Find the shortest path from the start vertex, to any other vertex in the graph
Floyd’s algorithm: explain how you know that the graph contains directed edges, (given the distance table and route table)
The distance table is not symmetrical about the leading diagonal
What is the difference in output between Floyd’s algorithm and Dijkatra’s?
The output of Floyd’s gives the shortest distance between every pair of nodes
The output of Dijkstra’s gives the shortest distance from the start mode to every other node
Floyd’s algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration
(n-1)(n-2) = n^2 - 3n + 2
What is the order of Floyd’s algorithm?
Cubic
What is an Eulerian graph?
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 who is vertices are all even is Eulerian
What is a semi-Eulerian graph?
One which contains a trail that includes every edge that starts and finishes at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian
If all the vertices in a network have even degree, then the length of the shortest route will be…?
The total weight of the network
If a network has exactly 2 odd vertices, then the length of the shortest route will be…?
The total weight of the network, plus the length of the shortest path between the two odd vertices
What is the route inspection algorithm ?
Identify any vertices with odd degree
Consider all possible complete pairings of these vertices
Select the complete pairing that has the least sum
Add a repeat of the arcs indicated by this pairing to the network
Describe the classical and practical 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
What do you need to convert the network into, in order for the classical and practical travelling salesman problems to be the same?
A complete network of least distances
The table representing this = table of least distances
Travelling salesman problem: How can you find an upper bound?
Use a minimum spanning tree
Or nearest neighbour algorithm
Travelling salesman problem: How can you use a minimum spanning tree to find an upper bound?
Find the minimum spanning tree, this guarantees that each vertex is included
Double the minimum connector so that completing the cycle is guaranteed
Seek ‘shortcuts’
Travelling salesman problem: Why do you want to make the upper bound as low as possible?
To reduce the interval in which the optimal solution is contained
Travelling salesman problem: What can you use to find a lower bound?
Minimum spanning tree
Travelling salesman problem: How can you find the lower bound using a minimum spanning tree?
Remove each vertex in turn, together with its arcs
Find the residual minimum spanning tree and its length
Add to the RMST the ‘cost’ of reconnecting the deleted vertex by the two shortest, district, arcs and note the total
The greatest of these totals is used for the lower bound
Travelling salesman problem: why do you want to make the lower bound as high has possible ?
To reduce the interval in which the optimal solution is contained
Travelling salesman problem: How do you know if you have found the optimal solution when using a minimum spanning tree to find a lower bound?
If the lower bound gives a Hamiltonian cycle, or if the lower bound has the same value as the upper bound
Travelling salesman problem: using a minimum spanning tree to find the lower bound: Why does this generally not give you a solution to the original problem?
It would be necessary to repeat arcs to create a tour
Travelling salesman problem: using a minimum spanning tree to find a lower bound: Does this work for both the classical and the practical problem?
This algorithm only produces a lower bound for the classical problem. If you are solving the practical problem you need to apply the algorithm to a table of least distances
Travelling salesman problem: finding the region of the optimal solution. Do you use less/greater than, or less/greater than or equal to?
Is the bound you have found offers a solution, then use equal to.
Travelling salesman problem: How do you use the nearest neighbour algorithm to find an upper bound?
Select each 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 of the vertex using the shortest route
Once all the vertices have been used as a starting vertex, select the tour with the smallest length as the upper bound
Is the upper bound given by the nearest neighbour algorithm always a possible solution?
Yes because it always represents a possible tour
What order does the nearest neighbour algorithm have for an application to a single vertex? Therefore what order does the whole nearest neighbour algorithm have?
Quadratic
Cubic
Linear programming:
What’s the decision variable?
The numbers of each of the things that can be varied
The variables, e.g. x, y, z, that are used in the objective function and inequalities
Linear programming:
What is the feasible region?
The region that contains all the feasible solutions
Linear programming:
What are constraints?
Things that will prevent you making, or using, an infinite number of each of the variables. Each constraint leads to an inequality
Linear programming:
What is the optimal solution?
The feasible solution that meets the objective. There might be more than one
Linear programming:
What is the objective function?
And equation that describes the objective. Like, maximising profit, or minimising cost
Linear programming:
As well as the constraints, what other inequalities do you usually add to describe the decision variables?
Usually all the variables have to be greater than or equal to 0
Sometimes they also have to be integers
Linear programming:
Describe how to formulate a linear programming problem
Define the decision variables
State the objective ( Maximise or minimise, together with an objective function)
Write the constraints as inequalities
Linear programming:
Do you shade the feasible region or the other areas?
All the other areas and not the feasible region, unless stated otherwise
Linear programming:
Describe how 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
Linear programming:
What is a slack variable?
A variable that represents the amount of slack between an actual quantity and the maximum possible value of that quantity
Linear programming: Do you use slack variables for ≥ or ≤ inequalities?
Less than or equal to
Linear programming:
Write 5x + 6y ≤ 10 as an equation with a slack variable, r
5x + 6y + r = 10
where r ≥ 0
What does the Simplex method allow you to do?
Determine if a particular vertex, on the edge of the feasible region, is optimal
Decide which adjacent vertex you should move to in order to increase the value of the objective function
Simplex method:
What are the values of the basic values and the other variables?
The basic values have the values allocated in the value column of the table
All other variables = 0
Simplex method: basic simplex
Which variables are the initial basic variables?
The slack variables
Simplex method: basic simplex
Graphically what does the Simplex method do?
It always 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
Simplex method:
Which column do you use as the pivot column?
The column with the most negative value in the profit row
Simplex method:
How do you work out which row is the pivot row?
Divide each ‘value’ by the number is the pivot column in the same row. The least positive of these is the pivot row. ( 0 is not less positive than 2, eg. Pick the 2 row)
Simplex method: minimise cost, C
C = 5x + 6y
How would you formulate this problem?
Define a new objective function that is the negative of the original objective function, and maximise this
Eg. Q = - 5x - 6y
Simplex method: if a problem requires integer solutions, what do you do once you have completed the tableau?
Look at the points around the optimal solution
Write a table with column headers of point, each constraint inequality, in a feasible region?, Objective function
Pick the point that’s in the feasible solution that has the highest/lowest objective function value
Two-stage Simplex method: If your constraint inequality is 5x + 6y ≥ 10, how do you formulate this for the simplex method?
Use a surplus variable (s) and an artificial variable (a)
5x + 6y - s + a = 10
where x, y, s, a ≥ 0
Describe the two-stage simplex method
What do you do?
I = - (a1 + a2 +….) then maximise I, substitute in for a1 and a2
Write out the first tableau (basic variables = slack and artificial (not surplus!!), then the objective function P, then I) , complete until optimal
If I = 0 then there’s a basic feasible region for the original problem
Get rid of the I row, and the artificial variable columns
The complete using normal simplex
Describe the two-stage simplex method
When do you use it?
Use it when you have ≥ inequalities
Two-stage simplex method: When selecting the pivot column, do you use the P row or the I row?
The I row
What is M in the big M method?
An arbitrarily large positive number
Describe when you use the big M method?
When you have ≥ inequalities
Big M simplex: Formulate: x + y ≤ 5 2x - y ≥ 6 Max. P = x + 5y into an equation
x + y + s1 = 5 2x - y - s2 + a1 = 6 Max. P = x + 5y - Ma1 then substitute in for a1 P = x + 5y - M(6 - 2x + y + s2) And rearrange
Where x, y, s1, s2, a1 ≥ 0 and M is an arbitrarily large number
Describe how to carry out the Big-M method
Formulate the problem using slack, surplus, and artificial variables
Write an initial tableau (slack and artificial are the basic variables, as well as P)
Complete simplex as normal
What is the purpose of M in the Big M method?
To drive the artificial variable towards 0
What’s the answer to the simplex question: How can you tell this tableau (given) is optimal?
There are no negative numbers in the profit row
Two stage/Big m method
What’s the answer to the question: Explain why the tableau does not represent a feasible solution?
a1 ≠ 0, so the solution is not feasible
What is the answer to the question: x + y ≤ 5 2x - y ≥ 6 Max. P = x + 5y Why can't you use the basic simplex algorithm to solve this problem?
It contains a “≥ “ constraint, i.e. the origin is not a feasible solution.
What is a precedence/dependence table?
A table which shows which activities must be completed before others are started
Activity network:
Events =
Activities =
Events = nodes Activities = arcs
Activity network:
What is the source node, and what is it numbered with?
The starting node, numbered 0
Activity network:
What is the final node called?
The sink node
Activity network:
Why can’t you have two activities leaving an event and entering the same event as each other ?
Every activity must be uniquely represented in terms of its events. This requires that there can be at most one activity between any two events
Activity network:
What is the answer to the question: explain the significance of the dotted line from event 1 to event 2?
It’s a dummy. It shows that activity [B] depends on activity x and y, whereas activity [A] depends on activity x
Activity network: What is early event time?
The earliest time of arrival at the event allowing for the completion of all preceding activities
Activity network: What is late event time?
The latest time that the event can be left without extending the time needed for the project
Activity network: What is a critical activity?
An activity where an increase in its duration results in a corresponding increase in the duration of the whole project
Activity network: What is a critical path?
A path from the source node to the sink node which entirely follows critical activities. A critical path is the longest path contained in the network
Activity network: Describe the early event time and late event time of a node on a critical path
The early event time is equal to late event time
Activity network:
What is the total float of an activity? And how do you calculate it?
The amount of time that its start may be delayed without affecting the duration of the project
Float = latest finish time - duration - earliest start time
Activity network:
What is the total float on a critical activity?
0
What are the assumptions made when using a resource histogram?
No worker can carry out more than one activity simultaneously
Once a worker has started an activity they must complete it
Once a worker has finished an activity they immediately become available to start another activity
What are the rules for 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
How do you calculate the lower bound for the number of workers needed to complete a project within its critical time?
It’s the smallest integer greater than or equal to:
The sum of all the activity times divided by the critical time of the project
Exam Question:
Define the term Hamiltonian cycle (2)
A Hamiltonian cycle is • a sequence of edges • that passes through every vertex of a graph • exactly once • and returns to its start vertex.
(Any 2 of the 4)
What is the word for all the edges entering or leaving a node?
Edges incident to that node
eg, every arc incident on G
Order of an algorithm:
Explain why the order given (xlny) is only approximate
The order of an algorithm gives the order of the dominant term in the time needed; other terms will still affect the total time
What is the order of the quick sort algorithm?
nlogn
What is the order of Prim’s algorithm?
V^2 V = no. of vertices
What is the order of Kruskal’s algorithm?
ElogV
V = no. of vertices
E = no. of edges
What is the order of Dijkstra’s algorithm?
~ ElogV
V = no. of vertices
E = no. of edges
Big M simplex: Formulate: x + y ≥ 5 2x - y ≥ 6 Min. P = x + 5y into an equation
x + y - s1 + a1 = 5 2x - y - s2 + a2 = 6 Q = - x - 5y Max. Q = - x - 5y - M(a1 + a2) then substitute in for a1 and a2 Q = - x - 5y - M(5 - x - y + s1 + 6 - 2x + y + s2) And rearrange
Where x, y, s1, s2, a1, a2 ≥ 0 and M is an arbitrarily large number
Book question: Describe 2 differences between Prim’s and Kruskal’s
In Prim’s algorithm, the starting point can be any node, whereas Kruskal’s algorithm starts
from the arc of least weight. In Prim’s algorithm, each new node and arc is added to the
existing tree as it builds, whereas in applying Kruskal’s algorithm, the arcs are selected
according to their weight and may not be connected until the end.
