Brainscape's Knowledge GenomeTM

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


See full index

A-Level Further Maths > Decision Maths Knowledge > Flashcards

Decision Maths Knowledge Flashcards

1
Q

For a linear programming problem with slack variables, what are the basic variables?

A

Slack variables

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

What is the total float of an activity between i and j?

A

Float = late j - early i - duration

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

In flow charts, what does each box shape represent?

A

Pill shape - start/end
Rectangle - instruction
Diamond - Decision

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

How does bubble sort work?

A

Compare first two values, if in order, leave them, if notm swap them
Move onto 2nd and 3rd values until pass completed
List in order when a pass is completed with no swaps

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

How does quick sort work?

A

Select the middle value in the list as the pivot, move values to either side based on order
Middle value now in correct place
Select pivots for each side and repeat

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
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
7
Q

How does the first fit algorithm work for bin packing?

A

Take the items in the order given

Place each item in the first available bin that can take it (starting from bin 1)

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

What is the advantage and the disadvantage for the first fit algorithm for bin packing?

A

Advantage: Quick to implement
Disadvantage: Not likely to lead to a good solution

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

How does the first fit decreasing algorithm work for bin packing?

A

Sort the items into descending order

Apply the first fit algorithm to the reordered list

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

What are the advantages and the disadvantage for the first fit decreasing algorithm for bin packing?

A

Advantages: Fairly good solution & easy to implement
Disadvantages: May not get optimal solution

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

How does the full bin algorithm work for bin packing?

A

Use observation to find combinations that will fill a bin, pack these first
Any remaining are packed using first fit

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

What is the advantage and the disadvantage for the first fit decreasing algorithm for bin packing?

A

Advantage: Good solution
Disadvantage: Difficult when considering lots of items

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

What do the entries in an adjacency matrix show?

A

Describes the number of arcs joining the corresponding vertices

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

What value is obtained from an undirected loop in an adjacency matrix, and why?

A

2

Because it can be travelled in either direction

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

What do the entries in a distance matrix represent?

A

The weight of each arc joining the corresponding vertices

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

Outline the planarity algorithm

A

Identify a Hamiltonian cycle
Draw a polygon matching the Hamiltonian cycle
Draw edges inside the polygon to match those not represented by the polygon
List all edges inside the polygon
Choose any unlabelled edge and label it I for inside
Any that cross this inside edge label O for outside
Repeat for unlabelled edges
Planar if no edges cross

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

What is a minimum spanning tree?

A

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

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

Outline Kruskal’s algorithm

A

Sort all arcs into ascending order of weight
Select the arc of least weight to start the tree
Consider the next arc: if it forms a cycle, reject it, if not, add it to the tree
Repeat until all vertices are connected

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

Outline Prim’s algorithm

A

Choose any vertex to start the tree
Select an arc of least weight that joins a vertex already in the tree to one not in the tree
Repeat until all vertices are connected

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

What are the three differences between Prim’s and Kruskal’s?

A

Prim’s consider vertices, Kruskal’s considers edges
Kruskal’s the graph is not always connected
Prim’s can be drawn from a distance matrix

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

What does Dijkstra’s algorithm find?

A

The shortest path between two nodes through a network

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

What does Floyd’s algorithm find?

A

The shortest path between every pair of vertices in a network

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

When using Floyd’s, what is put in place of there being no direct route between two vertices?

A

An infinity sign

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

What is the route inspection algorithm (Chinese postman) used to find?

A

Shortest route in a network that traverses every arc at least once and returns to its starting point

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

Outline route inspection algorithm

A

Identify vertices of odd degree
Consider all possible pairings of these vertices
Select the pairing that has the least sum
Add a repeat of the necessary arcs to the network

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

What is the best upper bound for travelling salesman?

A

Lowest possible value

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

What is the best lower bound for travelling salesman?

A

Highest possible value

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

How is the upper bound found for travelling salesman using minimum spanning trees?

A

Find the minimum spanning tree for the network using Prim’s or Kruskal’s
Double the minimum spanning tree
Seek shortcuts to bypass repeats
Use shortcut that reduces upper bound by the most

29
Q

How is the lower bound found for travelling salesman?

A 
Remove a vertex
Find the residual minimum spanning tree
Add to the RMST the two shortest arcs that reconnect the removed vertex
Repeat for removing every vertex
Highest value is the best lower bound
30
Q

How is the upper bound found for travelling salesman using nearest neighbour?

A

Select each vertex in turn as a starting point
Go to the nearest vertex which has not been visited yet
Repeat until all vertices have been visited and return to start vertex using the shortest route (forming a tour)
Select lowest value

31
Q

What is the feasible region?

A

The region of a graph that satisfies all the constraints of a linear programming problem

32
Q

How do you solve a linear programming problem?

A

Find the point in the feasible region which maximises or minimises the objective function`

33
Q

How can the optimal solution be found using a ruler?

A

Have a graph displaying the constraints and feasible region
Move a ruler parallel to the objective function
If maximising, last value in feasible region is optimal solution (reverse for minimising)

34
Q

How can the optimal solution be found using the vertex method?

A

First find the co-ordinates 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

35
Q

How do you formulate a linear programming problem?

A

Define decision variables
Write down the objective
Write down the constraints

36
Q

How can inequalities be transformed into equations?

A

Slack variables

37
Q

How would ‘x + y +2z =< 20’ be transformed into an equation?

A

x + y + 2z + r = 20

Where r is the slack variable

38
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

39
Q

If the objective function is to minimise ‘P = 3x - y’, how would you rearrange this to input into a simplex tableau?

A

Define Q as -P
So Q = -3x + y
Q + 3x - y = 0

40
Q

When the optimal solution to the problem is found and it is not an integer, but an integer solution is required, how would you find the best point?

A

Test the four integer points around the optimal solution against the constraints and objective function
Best answer fits constraints and maximises objective function

41
Q

How are constraints transformed to equations when there are >= constraints?
Use the example ‘x + y + z >= 10’

A

Requires a surplus variable and an artificial variable
Transform to: ‘x + y + z - s1 + a1 = 10’
s1 is the surplus variable
a1 is the artificial variable

42
Q

When artificial variables are introduced, what must be done to the simplex tableau?

A

New objective function I

I = -(a1 + a2 …)

43
Q

When is there a feasible solution, when artificial variables are involved?

A

I = 0

44
Q

If there is a feasible solution for two stage simplex, what must be done in the second stage?

A

Use the simplex method again, with the previous tableau as the starting point
Removing the I row, and the artificial variables

45
Q

In the Big-M method of simplex, what is M?

A

An arbitrarily large method

46
Q

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

A

Drive the artificial variables to 0

47
Q

Outline the Big-M method of simplex

A

Introduce a slack variable for each =< constraint
Introduce a surplus variable and an artificial variable for each >= constraint
For each artificial variable, subtract M lots of them from the objective function
Eliminate the artificial variables from your objective function so only non-basic variables remain
Formulate an initial tableau and apply simplex method

48
Q

What does a precedence table show?

A

Which activities must be completed before others are started

49
Q

For an activity network, what are represented by the arcs and nodes?

A

Activities by arcs

Completion of activities (called events) by nodes

50
Q

What is the first node also called?

A

Source node

51
Q

What is the last node also called?

A

Sink node

52
Q

What are the two reasons for the use of a dummy activity?

A

To prevent a delay in starting an activity

Every activity must be uniquely represented in terms of its events

53
Q

How can the length of time of an activity be displayed on an activity network?

A

Weight of the arc

54
Q

What is the early event time?

A

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

55
Q

What is the late event time?

A

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

56
Q

How are early event times calculated?

A

Starting from 0 at the source node and working towards the sink node (called the forward pass)

57
Q

How are late event times calculated?

A

Starting from the sink node and working backwards towards the source node (called the backward pass)

58
Q

When is an activity critical?

A

If any increase in its duration would result in an increase in the duration of the whole project

59
Q

What is the critical path?

A

A path from the source node to the sink node which entirely follows critical activities

60
Q

How do you work out if an activity is critical?

A

Float = 0

61
Q

What is total float (definition and equation) of an activity?

A

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

62
Q

What does a Gantt (cascade) chart provide?

A

A graphical way to represent the range of possible start and finish times for all activities on a single diagram

63
Q

Using a Gantt chart, where would you take the 10th day to be?

A

Midpoint between 9 and 10

64
Q

What are the rules for workers?

A

No worker can carry out more than one activity simultaneously
Once a worker has started an activity, they must finish it
Once a worker has finished an activity, they immediately become available to start another activity

65
Q

What is used to show the number of workers that are active at any given time?

A

Resource histogram

66
Q

What is it called to adjust the start and finish times of activities to account for constraints on resources?

A

Resource levelling

67
Q

For a scheduling diagram, what are the tips?

A

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

68
Q

What is the lower bound for the number of workers?

A

Smallest integer greater than or equal to:

Sum of all activity times / critical time of the project

A-Level Further Maths (8 decks)

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