Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
Outline route inspection algorithm
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
26
What is the best upper bound for travelling salesman?
Lowest possible value
27
What is the best lower bound for travelling salesman?
Highest possible value
28
How is the upper bound found for travelling salesman using minimum spanning trees?
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
How is the lower bound found for travelling salesman?
``` 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
How is the upper bound found for travelling salesman using nearest neighbour?
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
What is the feasible region?
The region of a graph that satisfies all the constraints of a linear programming problem
32
How do you solve a linear programming problem?
Find the point in the feasible region which maximises or minimises the objective function`
33
How can the optimal solution be found using a ruler?
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
How can the optimal solution be found using the vertex method?
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
How do you formulate a linear programming problem?
Define decision variables Write down the objective Write down the constraints
36
How can inequalities be transformed into equations?
Slack variables
37
How would 'x + y +2z =< 20' be transformed into an equation?
x + y + 2z + r = 20 | Where r is the slack variable
38
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
39
If the objective function is to minimise 'P = 3x - y', how would you rearrange this to input into a simplex tableau?
Define Q as -P So Q = -3x + y Q + 3x - y = 0
40
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?
Test the four integer points around the optimal solution against the constraints and objective function Best answer fits constraints and maximises objective function
41
How are constraints transformed to equations when there are >= constraints? Use the example 'x + y + z >= 10'
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
When artificial variables are introduced, what must be done to the simplex tableau?
New objective function I | I = -(a1 + a2 ...)
43
When is there a feasible solution, when artificial variables are involved?
I = 0
44
If there is a feasible solution for two stage simplex, what must be done in the second stage?
Use the simplex method again, with the previous tableau as the starting point Removing the I row, and the artificial variables
45
In the Big-M method of simplex, what is M?
An arbitrarily large method
46
What is the purpose of the M, in the Big-M method?
Drive the artificial variables to 0
47
Outline the Big-M method of simplex
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
What does a precedence table show?
Which activities must be completed before others are started
49
For an activity network, what are represented by the arcs and nodes?
Activities by arcs | Completion of activities (called events) by nodes
50
What is the first node also called?
Source node
51
What is the last node also called?
Sink node
52
What are the two reasons for the use of a dummy activity?
To prevent a delay in starting an activity | Every activity must be uniquely represented in terms of its events
53
How can the length of time of an activity be displayed on an activity network?
Weight of the arc
54
What is the early event time?
The earliest time of arrival at the event allowing for the completion of the preceding activities
55
What is the late event time?
The latest time that the event can be left without extending the time needed for the project
56
How are early event times calculated?
Starting from 0 at the source node and working towards the sink node (called the forward pass)
57
How are late event times calculated?
Starting from the sink node and working backwards towards the source node (called the backward pass)
58
When is an activity critical?
If any increase in its duration would result in an increase in the duration of the whole project
59
What is the critical path?
A path from the source node to the sink node which entirely follows critical activities
60
How do you work out if an activity is critical?
Float = 0
61
What is total float (definition and equation) of an activity?
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
What does a Gantt (cascade) chart provide?
A graphical way to represent the range of possible start and finish times for all activities on a single diagram
63
Using a Gantt chart, where would you take the 10th day to be?
Midpoint between 9 and 10
64
What are the rules for workers?
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
What is used to show the number of workers that are active at any given time?
Resource histogram
66
What is it called to adjust the start and finish times of activities to account for constraints on resources?
Resource levelling
67
For a scheduling diagram, what are the tips?
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
What is the lower bound for the number of workers?
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.
© 2025 Bold Learning Solutions. Terms and Conditions