Rest of Decision Flashcards

(103 cards)

1
Q

What is an algorithm?

A

A finite sequence of step-by-step instructions carried out to solve a problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does an oval shaped box mean in a flow chart?

A

The start/end

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does a rectangular box mean in a flowchart?

A

It’s an instruction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What does a diamond shaped box mean in a flowchart?

A

A decision

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Describe how to carry out a bubble sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Describe how to carry out a quick sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the three bin packing algorithms?

A

First fit
First fit decreasing
Full bin

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Describe how to carry out first fit bin packing

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the advantage/disadvantage of first fit bin packing?

A

Ad: It is quick to implement
Dis: It is not likely to lead to a good solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Describe how to carry our first fit decreasing bin packing

A

Sort the items so that they are in descending order

Apply the first fit algorithm to the re-ordered list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the advantages/disadvantages of first fit decreasing bin packing?

A

Ad: You usually get a fairly good solution. It is easy to implement
Dis: You may not get an optimal solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Describe how to carry out full bin packing

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the advantages/disadvantages of full bin packing?

A

Ad: You usually get a good solution
Dis: It is difficult to do, especially when the numbers are plentiful and awkward

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the order of an algorithm?

A

Tells you how changes in the size of a problem affect the approximate time taken for its completion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What order is bubble sort?

A

Quadratic: 0.5(n-1)n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

In any undirected graph, the sum of the degrees of the vertices equals…?

A

2 x the no. of edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is Euler’s handshaking lemma?

A

The number of orders vertices must be even, including possibly zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a planar graph?

A

One that can be drawn in a plane such that no two edges meet except at a vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a minimum spanning tree?

A

A spanning tree such that the total length of it arcs is as small as possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Which algorithms find the minimum spanning tree?

A

Kruskal’s (list all edges) and Prim’s (either pick one node on the graph, and find MST. Or use distance matrix)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the main difference between Kruskal’s and Prim’s?

A

Kruskal’s looks at edges

Prim’s looks at nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What can Dijkstra’s algorithm be used for?

A

Find the shortest path from the start vertex, to any other vertex in the graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Floyd’s algorithm: explain how you know that the graph contains directed edges, (given the distance table and route table)

A

The distance table is not symmetrical about the leading diagonal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the difference in output between Floyd’s algorithm and Dijkatra’s?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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
26
What is the order of Floyd’s algorithm?
Cubic
27
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
28
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
29
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
30
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
31
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
32
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
33
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
34
Travelling salesman problem: How can you find an upper bound?
Use a minimum spanning tree | Or nearest neighbour algorithm
35
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’
36
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
37
Travelling salesman problem: What can you use to find a lower bound?
Minimum spanning tree
38
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
39
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
40
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
41
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
42
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
43
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.
44
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
45
Is the upper bound given by the nearest neighbour algorithm always a possible solution?
Yes because it always represents a possible tour
46
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
47
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
48
Linear programming: | What is the feasible region?
The region that contains all the feasible solutions
49
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
50
Linear programming: | What is the optimal solution?
The feasible solution that meets the objective. There might be more than one
51
Linear programming: | What is the objective function?
And equation that describes the objective. Like, maximising profit, or minimising cost
52
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
53
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
54
Linear programming: | Do you shade the feasible region or the other areas?
All the other areas and not the feasible region, unless stated otherwise
55
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
56
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
57
Linear programming: Do you use slack variables for ≥ or ≤ inequalities?
Less than or equal to
58
Linear programming: | Write 5x + 6y ≤ 10 as an equation with a slack variable, r
5x + 6y + r = 10 | where r ≥ 0
59
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
60
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
61
Simplex method: basic simplex | Which variables are the initial basic variables?
The slack variables
62
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
63
Simplex method: | Which column do you use as the pivot column?
The column with the most negative value in the profit row
64
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)
65
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
66
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
67
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
68
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
69
Describe the two-stage simplex method | When do you use it?
Use it when you have ≥ inequalities
70
Two-stage simplex method: When selecting the pivot column, do you use the P row or the I row?
The I row
71
What is M in the big M method?
An arbitrarily large positive number
72
Describe when you use the big M method?
When you have ≥ inequalities
73
``` 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
74
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
75
What is the purpose of M in the Big M method?
To drive the artificial variable towards 0
76
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
77
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
78
``` 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.
79
What is a precedence/dependence table?
A table which shows which activities must be completed before others are started
80
Activity network: Events = Activities =
``` Events = nodes Activities = arcs ```
81
Activity network: | What is the source node, and what is it numbered with?
The starting node, numbered 0
82
Activity network: | What is the final node called?
The sink node
83
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
84
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
85
Activity network: What is early event time?
The earliest time of arrival at the event allowing for the completion of all preceding activities
86
Activity network: What is late event time?
The latest time that the event can be left without extending the time needed for the project
87
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
88
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
89
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
90
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
91
Activity network: | What is the total float on a critical activity?
0
92
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
93
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
94
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
95
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)
96
What is the word for all the edges entering or leaving a node?
Edges incident to that node | eg, every arc incident on G
97
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
98
What is the order of the quick sort algorithm?
nlogn
99
What is the order of Prim's algorithm?
V^2 V = no. of vertices
100
What is the order of Kruskal's algorithm?
ElogV V = no. of vertices E = no. of edges
101
What is the order of Dijkstra's algorithm?
~ ElogV V = no. of vertices E = no. of edges
102
``` 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
103
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.