1
Q
1.1 How can algorithms be written?
A
Code, flowcharts, or a set of instructions
2
Q
1.1 What can be used to implement an algorithm?
A
A trace table
3
Q
1.2 What does the shape of each box in a flowchart tell you about the function?
A
Oval - Start/End
Rectangle - Instruction
Diamond - Decision
4
Q
1.3 Describe a bubble sort
A
Compare adjacent items in a list:
- If they are in order, leave them
- If they are not in order, swap them
- After the first pass, the last item will be in the correct place
- When a pass is completed with no swaps, the sort is complete
5
Q
1.3 What is the expression for the maximum number of comparisons in a bubble sort?
A
(n(n -1))/2
6
Q
1.4 Describe quick sort
A
Select a pivot and split the items into 2 sub-lists:
- One contains the items less than the pivot
- The other contains the items greater than the pivot
- Select further pivots from within each sub-list and repeat the process
7
Q
1.5 What are the 3 bin packing algorithms? Describe them
A
First-fit: Items in order listed, place each item in the first available bin
First-fit descending: Sort into descending order, then apply the first-fit algorithm
Full-bin: Use inspection to select items that will fill a bin first. Remaining items packed with first-fit
8
Q
1.5 What are the advantages and disadvantages of first-fit?
A
+ve - Quick to implement
-ve - Unlikely to lead to an optimal solution
9
Q
1.5 What are the advantages and disadvantages of first-fit descending?
A
+ve - Usually an optimal solution, easy to implement
-ve - May not find optimal solution, takes a long time
10
Q
1.5 What are the advantages and disadvantages of full-bin?
A
+ve - Usually an optimal solution
-ve - Difficult especially when numbers are large/awkward
11
Q
1.6 What is the order of an algorithm?
A
If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time by a factor of approximately f(m)/f(n)
12
Q
1.6 What order does bubble sort have? Explain how you get this
A
A list has n items, the first pass will require (n-1) comparisons, a second pass will require (n-2) comparisons, in the worse case this continues, the total number of comparisons would be:
1+2+3+…+(n-3)+(n-2)+(n-1) = (1/2)(n-1)n = (1/2)n^2 - (1/2)n
Since this is a quadratic expression, bubble sort is taken to have quadratic order
13
Q
1.6 What are the rules for linear, quadratic, and cubic order?
A
If the size of a problem is increased by some factor k then:
- an algorithm of linear order will take approximately k times as long to complete
- an algorithm of quadratic order will take approximately k^2 times as long to complete
- an algorithm of quadratic order will take approximately k^3 times as long to complete
14
Q
2 What is a graph?
A
A finite number of vertices (or nodes) connected by edges (or arcs)
15
Q
2 What is a weighted graph? What is it also known as?
A
A graph that has numbers assigned to each edge, also called a network
16
Q
2 What is a tree?
A
A connected graph with no cycle
17
Q
2 What is a subgraph?
A
A graph whose vertices and edges belong to another graph but it is only part of the original
18
Q
2 What is a walk?
A
A route through a graph along edges from one vertex to another
19
Q
2 What is a path?
A
A walk in which no vertex is visited more than once
20
Q
2 What is a trail?
A
A walk in which no edge is visited more than once
21
Q
2 What is a cycle? What is it also known as?
A
A walk in which the end vertex is the same as the starting vertex (also a closed path)
22
Q
2 What is a Hamiltonian Cycle?
A
A cycle in which all vertices are visited
23
Q
2 What does it mean if a graph is connected?
A
If all the vertices are joined to the graph
24
Q
2 What is a loop?
A
An edge that starts and finishes at the same vertex
25
2 What is a simple graph?
A graph with no loops and where there is at most one edge connecting any pairs of vertices
26
2 What is a digraph?
A graph where edges have a direction
27
2 What is a spanning tree?
A subgraph which includes all original vertices that is also a tree
28
2 What is the expression for the number of edges in a spanning tree for a connected graph of n vertices?
n-1
29
2 What is a complete graph?
Every vertex is connected to each other by a single edge (think k1, k2, k3, ...)
30
2 What is the expression for the number of Hamiltonian cycles in a complete graph with n vertices?
((n-1)!)/2
31
2 What is an isomorphic graph?
A pair of graphs which shows the same information but are drawn differently
32
2 What is an adjacency matrix?
A table describing the number of arcs joining the corresponding vertices
33
2 What is a distance matrix?
A table in which the entries represent the weight of each arc, not the number of arcs
34
2 What is the degree/valency/order of a vertex?
The number of edges coming out of the vertex
35
2 What is the Handshake Lemma?
In any undirected graph, the sum of the degrees of vertices is equal to 2x the number of edges - therefore the number of odd vertices must be even
36
2.5 What is a planar graph?
One that can be drawn in a plane such that no two edges meet except at a vertex
37
2.5 What is the planarity algorithm?
1. Identify a Hamiltonian Cycle (If none present the algorithm cannot be used but this doesn't exclude the possibility that the graph is planar)
2. Draw a polygon w/ vertices labelled to match the Hamiltonian Cycle
3. Draw remaining edges to match original graph
4. Make a list of interior edges
5. Choose any unlabelled edge & label it 'I'. If all edges are labelled then planar
6. Look at unlabelled edges that cross the edge just labelled:
- If there are none, go to 5.
- If any edges cross each other, not planar
- If none of these edges cross each other, give them the opposite label to the edge just labelled
- If all edges are now labelled, it's planar. Otherwise, restart 6.
38
3.1-3.2 What do Kruskal and Prim's algorithms do?
They find the minimum spanning tree (MST) of a network
39
3.1 Describe Kruskal's algorithm
1. Sort the arcs in ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least weight:
i) If it would form a cycle, reject it
ii) If it would not form a cycle, add it to the tree (if arcs are of equal weight consider each in turn)
4. Repeat (3) until all vertices are connected
40
3.2 Describe Prim's algorithm
1. Select any vertex to start the tree from (often given to you in the question)
2. Choose an arc of least weight connecting to the starting vertex that joins a vertex not currently in the tree (if there are a choice of equal arcs then choose randomly)
3. Repeat (2) until all vertices are connected
41
3.3 Describe how you can apply Prim's algorithm to a distance matrix
1. Choose any vertex to start the tree
2. Cross out the row containing that vertex
3. Number the column in the matrix for the chosen vertex
4. Ring the lowest remaining entry in the column (if equal, choose randomly)
5. The ringed entry becomes the next arc added to the tree
6. Repeat 2, 3, 4, & 5 until all rows are deleted
42
3.3 What order is Prim's algorithm?
n^3
43
3.4 What is Dijkstra's algorithm used for?
Dijkstra's ('Dike-stra') algorithm is used to find the shortest path through a network
44
3.4 Describe Dijkstra's algorithm
1. Above every vertex there is a vertex label, order of labelling, final value, and working values
2. Label the starting vertex with a 1 and a final value of 0
3. Record a working value at every vertex that is connected to the vertex chosen
4. If this value is smaller than the current working value, cross the old value out
5. Look at the working values at all vertices without final labels, select the smallest working value and make it the final label
6. Repeat until the destination receives a final label
45
3.4 How do you find the shortest path between 2 points on a network?
Work backwards, whichever arc equals the next vertex when you subtract the arc value is the correct path
46
3.5 What is Floyd's algorithm used for?
Used to find the shortest path between every pair of vertices in a network
47
3.5 Describe Floyd's Algorithm
1. Complete an initial distance table, if no direct route label w/ infinity
2. Complete an initial route table by making every entry the same as the top of the column
3. In the first iteration, copy the highlighted row
4. Consider each unhighlighted position in turn. Compare the value in this position w/ the sum of the corresponding highlighted values:
- If sum is greater or equal to original, no change
- If sum is less than original, write new total in place and label w/ [...]
5. For second iteration copy 2nd row & column from last iteration into a new distance table. Highlight these
6. Repeat 4. w/ new unhighlighted positions. This time any changes will result in a detour through B & so write in B in new route table.
7. If there are n vertices, n iterations are required
48
3.5 What is the order of Floyd's Algorithm?
n^3
49
4.1 What is an Eulerian graph?
A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph whose vertices are all even is Eulerian.
50
4.1 What is a semi-Eulerian graph?
A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph with two odd vertices is semi-Eulerian (one odd vertex is the start and the other is the end of the trail)
51
4.2 What does the route inspection algorithm do?
Finds the length of the shortest route in a network that transverses every arc at least once, and returns to its starting point
52
4.2 If a network is Eulerian, what can you say about the length of its shortest route that transverses every arc?
length of the shortest route = total weight of the network
53
4.2 If a network is semi-Eulerian, what can you say about the length of its shortest route that transverses every arc?
length of the shortest route = total weight of the network plus the length of the shortest path between the two odd vertices
54
4.2 Describe how to implement the route inspection algorithm
- Identify any odd vertices
- Consider all possible pairings of these pairings
- Select the complete pairing that has the least sum
- Add a repeat of the arcs indicated by this pairing to the network
55
4.3 How do you solve route inspection problems with more than four odd nodes?
Use additional information to restrict the number of pairings of odd nodes that need to be considered
4 odd nodes: 3 possible pairings
6 odd nodes: 15 possible pairings
...Increases rapidly
56
5.1 What is a travelling salesman problem?
Visit every vertex, starting & finishing at the same vertex.
57
5.1 What is the difference between the classical and practical travelling salesman problems?
Classical - each vertex is visited only once
Practical - each vertex is visited at least once
58
5.1 What is a tour?
Visits every vertex and returns to the starting vertex (if it visits every vertex only once then it's a Hamiltonian Cycle)
59
5.1 What is a table of least distance?
A table showing the least distances between each pair of vertices. Found by inspection.
60
5.2 How do you find the upper bound for a travelling salesman problem? How can you improve on this upper bound?
Weight of MST x2
Improve on the upper bound by looking for shortcuts
61
5.3 How do you find the lower bound in a travelling salesman problem using a MST method?
- Remove a vertex from the network
- Find the Residual Minimum Spanning Tree (RMST) of the remaining vertices
- Add the removed vertex back in using the two shortest arcs
- Steps can be repeated by removing different vertices
- Pick the solution w/ the highest weight for the LB
62
5.3 How do you know when you have found an optimal solution to a travelling salesman problem?
If the solution is a Hamiltonian Cycle (UB=LB) then it is optimal
63
5.4 How do you use the nearest neighbour algorithm to find an upper bound for a travelling salesman problem?
1. Start w/ any vertex
2. Select the nearest vertex that has not been visited yet
3. Repeat until all vertices have been visited & return to starting vertex
4. Choose a different starting vertex, go to 2.
5. When all vertices have been selected as starting vertices, choose the tour w/ lowest weight as the UB
64
6.1 How do you formulate a linear programming problem?
- Define the decision variables (x, y, z, etc)
- State the objective (maximise/minimise, together with an algebraic expression called the objective function)
- Write the constraints as inequalities
65
6.2 What is the name of the region of a graph that satisfies all the constraints of a linear programming problem? How should you label this?
Feasible Region (generally marked with an 'R' and everywhere not in the region is shaded)
66
6.3 How do you solve a linear programming problem after drawing the feasible region?
Locate the optimal point with objective method or ruler method.
Obj. method: Find the coords of each vertex of the feasible region and select the vertex that gives the optimal value of the objective function
Ruler method: Sketch parallel lines with the same gradient as the objective function, for a max. point look for the last point covered by the lines as it leaves the feasible region, for a min. point look for the first point covered by the lines as it enters the feasible region
67
6.4 How do you find the optimal vertex of a linear programming problem if the solution does not have integer values?
- Consider the four integer coords in a square around the optimal vertex
- See which point obeys all the constraints
- If there are multiple, select the point that has the more optimal solution for the objective function
68
7.1 How do you formulate a linear programming problem for the simplex algorithm?
- Transform inequalities into equations using slack variables
e.g. ax1 + bx2 + cx3 ≤ d can be written as ax1 + bx2 + cx3 + r = d
69
7.2 What does the simplex algorithm do?
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
70
7.2 How do you use the tableaux method for the simplex algorithm?
1. Draw the tableaux - basic variable column on the left, one column for each variable and a value column. One row for each constraint and the bottom row for the objective function
2. Create the initial tableau by entering the coefficients of the variables
3. Look along the objective row for the most negative entry
4. Calculate theta values by dividing the values by their corresponding values in the pivot column
5. Select the row with the smallest theta value to become the pivot row
6. The element in the pivot row and column is the pivot
7. Divide the row in step 5 by the pivot, and change the basic variable at the start of the row. This is now the pivot row
8. Use the pivot row to eliminate the pivot's variables from the other rows. This means the pivot column contains a 1 and 0s
9. Repeat steps 3-8 until there are no more negatives in the objective row
10. The tableau is now optimal and the non-zero values can be read off the basic variable column & value column
71
7.2 How do you solve a minimising simplex problem?
To minimise P=f(a), maximise Q = -P = -f(a)
Then at the end remember to state the solution in terms of P not Q
72
7.3 What must you remember to look for in some simplex problems?
If solutions have to be given as integers or not. If yes, use the box method and find the most optimal solution. State your answer in terms of x, y, and z only (+ any other dimension variables but not slack variables)
73
7.4 Why would you use the two-stage simplex method?
When constraints include ≥, these problems have no basic feasible solution since the origin is not in the feasible region
74
7.4 Describe the two-stage simplex method
1. Use slack, surplus, and artificial variables to write all constraints as equations.
2. Define a new objective function, I, to minimise the sum of all the artificial variables: I=-(a1 + a2 +...an)
3. Use the simplex method to solve this problem.
4. If the minimum sum of the artificial variables is 0 then the solution found is a basic feasible solution of the original problem, which is then used as a starting point for the second stage. Use the simplex method again to solve the problem.
5. If the minimum sum of the artificial variables is not 0 then the original problem has no feasible solution.
75
7.5 What does M represent in the Big-M simplex method?
An arbitrarily large number
76
7.5 Why would you use the Big-M simplex method?
When constraints include ≥, these problems have no basic feasible solution since the origin is not in the feasible region
77
7.5 Describe the Big-M simplex method
1. Introduce a slack variable for each constraint of the form ≤
2. Introduce a surplus variable and an artificial variable for each constraint of the form ≥
3. For each artificial variable a1, a2, a3, ... subtract M(a1 + a2 + a3 + ...) from the objective function.
4. Eliminate the artificial variables from your objective function so that the variables remaining in your objective function are non-basic variables.
5. Formulate an initial tableau, and apply the simplex method in the normal way.
78
8.1 What is a precedence table?
A table which shows which activities must be completed before others are started
79
8.1 How do you draw an arc network for a critical path analysis problem?
- Activities represented by arcs & completion of activities shown as nodes
- Each arc labelled with an activity letter, convention is straight lines for arcs
- Nodes are numbered starting from 0 for the first node which is also called the source node
- Number each node as it is added to the network
- Final node is the sink node
80
8.2 What is a dummy activity?
- An activity that has no time or cost
- Its purpose is to show dependencies between activities
81
8.2 What is special about the relationship between two activities in a critical path analysis problem?
- Every activity must be uniquely represented
- There can be at most one activity between any two nodes
82
8.3 What is duration of an activity? How is it denoted?
- How long it takes to complete
- Denoted in brackets as the 'weight' of each arc
83
8.3 What is an early event time? What is a late event time?
- The earliest time that an activity can start/finish
- The latest time that an activity can start/finish
84
8.3 How are early and late event times shown?
Nodes are replaced by two boxes: top is the early event time, bottom is the late event time
85
8.3 How do you find the early event time of a node?
- Do a forward pass
- Whichever activity preceding it takes the longest to finish
- Think 'forward high'
86
8.3 How do you find the late event time of a node?
- Do a backward pass
- Whichever activity after it takes the shortest time to start
- Think 'backward low'
87
8.4 What is a critical activity?
An activity when any increase in its duration results in an increase in the duration of the whole project
88
8.4 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
- An activity connecting two critical events isn't necessarily a critical activity
89
8.4 How do you identify a critical event node?
The early event time is equal to the late event time
90
8.5 What is the float of an activity?
The amount of time that its start may be delayed without affecting the duration of the project
91
8.5 How do you calculate the float of an activity?
Total float = latest finish time - duration - earliest start time
92
8.5 What is the total float of a critical activity?
0
93
8.6 What is a Gantt chart? How do you draw one?
- Graphical way of representing possible start and finish time for all activities in a project
- Critical activities are across the top marked by solid lines
- Each subsequent activity is marked with solid lines starting at their early event time and spanning their duration
- An activity's float is marked on the end with dotted lines
94
8.6 What do these questions mean?
- Determine how many activities MUST be happening at midday on day x
- Determine how many activities MAY be happening at midday on day x
What must you also remember when answering these questions?
- MUST: An activity is definitely happening on the day either because its float is too small or because it is critical
- MAY: An activity may be happening depending on the length of its float
- IMPORTANT: If asked how many activities MAY be happening, do not also include those that MUST be happening
- Also, always consider the fencepost problem when marking the day on the Gantt Chart
95
8.7 When considering the number of workers on site, what are the rules?
- No worker can carry out more than one activity simultaneously
- Once a workers, or workers, have started an activity, they must complete it
- Once a worker, or workers, have finished an activity, they immediately become available to start another activity
96
8.7 What is resource levelling?
The process of adjusting start and finish times of the activities in order to take into account constraints on resources (resource histograms)
97
8.7 What is a resource histogram?
Shows the number of workers that are active at any given time. Convention is to assume each activity starts at the earliest time possible.
May be possible, once drawn, to determine which activities may be delayed in order to minimise the number of workers required.
In some cases, the number of workers available is less than the number required to complete the project in the min. time. The start & finish times of some activities may have to be delayed to meet this constraint, which extends the time needed for project completion.
98
8.8 How do you create a scheduling diagram?
- Assume one worker is required for each activity
- 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
99
8.8 How do you calculate the lower bound for the number of workers needed to complete a project by the critical time?
Lower bound = (sum of all activity times)/(critical time of the project)
(Round up to the next integer if the result is not an integer)
A Level Further Maths
flashcards
Decks in class (5)
# Cards
