Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

A Level Further Maths > Rest of Decision > Flashcards

Rest of Decision Flashcards

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
Q

Floyd’s algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration

A

(n-1)(n-2) = n^2 - 3n + 2

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

What is the order of Floyd’s algorithm?

A

Cubic

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

What is an Eulerian graph?

A

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

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

What is a semi-Eulerian graph?

A

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

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

If all the vertices in a network have even degree, then the length of the shortest route will be…?

A

The total weight of the network

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

If a network has exactly 2 odd vertices, then the length of the shortest route will be…?

A

The total weight of the network, plus the length of the shortest path between the two odd vertices

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

What is the route inspection algorithm ?

A

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

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

Describe the classical and practical travelling salesman problem

A

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

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

What do you need to convert the network into, in order for the classical and practical travelling salesman problems to be the same?

A

A complete network of least distances

The table representing this = table of least distances

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

Travelling salesman problem: How can you find an upper bound?

A

Use a minimum spanning tree

Or nearest neighbour algorithm

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

Travelling salesman problem: How can you use a minimum spanning tree to find an upper bound?

A

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’

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

Travelling salesman problem: Why do you want to make the upper bound as low as possible?

A

To reduce the interval in which the optimal solution is contained

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

Travelling salesman problem: What can you use to find a lower bound?

A

Minimum spanning tree

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

Travelling salesman problem: How can you find the lower bound using a minimum spanning tree?

A

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

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

Travelling salesman problem: why do you want to make the lower bound as high has possible ?

A

To reduce the interval in which the optimal solution is contained

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

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?

A

If the lower bound gives a Hamiltonian cycle, or if the lower bound has the same value as the upper bound

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

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?

A

It would be necessary to repeat arcs to create a tour

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

Travelling salesman problem: using a minimum spanning tree to find a lower bound: Does this work for both the classical and the practical problem?

A

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
Q

Travelling salesman problem: finding the region of the optimal solution. Do you use less/greater than, or less/greater than or equal to?

A

Is the bound you have found offers a solution, then use equal to.

44
Q

Travelling salesman problem: How do you use the nearest neighbour algorithm to find an upper bound?

A

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
Q

Is the upper bound given by the nearest neighbour algorithm always a possible solution?

A

Yes because it always represents a possible tour

46
Q

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?

A

Quadratic

Cubic

47
Q

Linear programming:

What’s the decision variable?

A

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
Q

Linear programming:

What is the feasible region?

A

The region that contains all the feasible solutions

49
Q

Linear programming:

What are constraints?

A

Things that will prevent you making, or using, an infinite number of each of the variables. Each constraint leads to an inequality

50
Q

Linear programming:

What is the optimal solution?

A

The feasible solution that meets the objective. There might be more than one

51
Q

Linear programming:

What is the objective function?

A

And equation that describes the objective. Like, maximising profit, or minimising cost

52
Q

Linear programming:

As well as the constraints, what other inequalities do you usually add to describe the decision variables?

A

Usually all the variables have to be greater than or equal to 0
Sometimes they also have to be integers

53
Q

Linear programming:

Describe how to formulate a linear programming problem

A

Define the decision variables
State the objective ( Maximise or minimise, together with an objective function)
Write the constraints as inequalities

54
Q

Linear programming:

Do you shade the feasible region or the other areas?

A

All the other areas and not the feasible region, unless stated otherwise

55
Q

Linear programming:

Describe how to find an optimal point using the vertex method

A

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
Q

Linear programming:

What is a slack variable?

A

A variable that represents the amount of slack between an actual quantity and the maximum possible value of that quantity

57
Q

Linear programming: Do you use slack variables for ≥ or ≤ inequalities?

A

Less than or equal to

58
Q

Linear programming:

Write 5x + 6y ≤ 10 as an equation with a slack variable, r

A

5x + 6y + r = 10

where r ≥ 0

59
Q

What does the Simplex method allow you to do?

A

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
Q

Simplex method:

What are the values of the basic values and the other variables?

A

The basic values have the values allocated in the value column of the table
All other variables = 0

61
Q

Simplex method: basic simplex

Which variables are the initial basic variables?

A

The slack variables

62
Q

Simplex method: basic simplex

Graphically what does the Simplex method do?

A

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
Q

Simplex method:

Which column do you use as the pivot column?

A

The column with the most negative value in the profit row

64
Q

Simplex method:

How do you work out which row is the pivot row?

A

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
Q

Simplex method: minimise cost, C
C = 5x + 6y
How would you formulate this problem?

A

Define a new objective function that is the negative of the original objective function, and maximise this
Eg. Q = - 5x - 6y

66
Q

Simplex method: if a problem requires integer solutions, what do you do once you have completed the tableau?

A

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
Q

Two-stage Simplex method: If your constraint inequality is 5x + 6y ≥ 10, how do you formulate this for the simplex method?

A

Use a surplus variable (s) and an artificial variable (a)
5x + 6y - s + a = 10
where x, y, s, a ≥ 0

68
Q

Describe the two-stage simplex method

What do you do?

A

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
Q

Describe the two-stage simplex method

When do you use it?

A

Use it when you have ≥ inequalities

70
Q

Two-stage simplex method: When selecting the pivot column, do you use the P row or the I row?

A

The I row

71
Q

What is M in the big M method?

A

An arbitrarily large positive number

72
Q

Describe when you use the big M method?

A

When you have ≥ inequalities

73
Q 
Big M simplex: Formulate:
x + y ≤ 5
2x - y ≥ 6
Max. P = x + 5y 
into an equation
A 
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
Q

Describe how to carry out the Big-M method

A

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
Q

What is the purpose of M in the Big M method?

A

To drive the artificial variable towards 0

76
Q

What’s the answer to the simplex question: How can you tell this tableau (given) is optimal?

A

There are no negative numbers in the profit row

77
Q

Two stage/Big m method

What’s the answer to the question: Explain why the tableau does not represent a feasible solution?

A

a1 ≠ 0, so the solution is not feasible

78
Q 
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?
A

It contains a “≥ “ constraint, i.e. the origin is not a feasible solution.

79
Q

What is a precedence/dependence table?

A

A table which shows which activities must be completed before others are started

80
Q

Activity network:
Events =
Activities =

A 
Events = nodes
Activities = arcs
81
Q

Activity network:

What is the source node, and what is it numbered with?

A

The starting node, numbered 0

82
Q

Activity network:

What is the final node called?

A

The sink node

83
Q

Activity network:

Why can’t you have two activities leaving an event and entering the same event as each other ?

A

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
Q

Activity network:

What is the answer to the question: explain the significance of the dotted line from event 1 to event 2?

A

It’s a dummy. It shows that activity [B] depends on activity x and y, whereas activity [A] depends on activity x

85
Q

Activity network: What is early event time?

A

The earliest time of arrival at the event allowing for the completion of all preceding activities

86
Q

Activity network: What is late event time?

A

The latest time that the event can be left without extending the time needed for the project

87
Q

Activity network: What is a critical activity?

A

An activity where an increase in its duration results in a corresponding increase in the duration of the whole project

88
Q

Activity network: What is a critical path?

A

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
Q

Activity network: Describe the early event time and late event time of a node on a critical path

A

The early event time is equal to late event time

90
Q

Activity network:

What is the total float of an activity? And how do you calculate it?

A

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
Q

Activity network:

What is the total float on a critical activity?

A

0

92
Q

What are the assumptions made when using a resource histogram?

A

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
Q

What are the rules for scheduling a project?

A

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
Q

How do you calculate the lower bound for the number of workers needed to complete a project within its critical time?

A

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
Q

Exam Question:

Define the term Hamiltonian cycle (2)

A 
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
Q

What is the word for all the edges entering or leaving a node?

A

Edges incident to that node

eg, every arc incident on G

97
Q

Order of an algorithm:

Explain why the order given (xlny) is only approximate

A

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
Q

What is the order of the quick sort algorithm?

A

nlogn

99
Q

What is the order of Prim’s algorithm?

A

V^2 V = no. of vertices

100
Q

What is the order of Kruskal’s algorithm?

A

ElogV
V = no. of vertices
E = no. of edges

101
Q

What is the order of Dijkstra’s algorithm?

A

~ ElogV
V = no. of vertices
E = no. of edges

102
Q 
Big M simplex: Formulate:
x + y ≥ 5
2x - y ≥ 6
Min. P = x + 5y 
into an equation
A 
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
Q

Book question: Describe 2 differences between Prim’s and Kruskal’s

A

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.

A Level Further Maths (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions