A gardener needs the following lengths of string. All lengths are in metres.
4.3 6.1 5.1 4.7 2.5 5.9 3.4 1.7 2.1 0.4 1.3
She cuts the lengths from balls of string. Each ball contains 10 m of string.
Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.
(2)
Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string.
(3)
[ The total weight of the network is 299]
Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track.
One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.
Use Dijkstra’s algorithm to find the shortest path from A to K.
State the length of the shortest path from A to K.
(6)
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E.
State the edges that will need to be traversed twice.
Find the length of Blanche’s route.
(2)
It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once.
By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear.
(5)
The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one‑way only.
By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book.
(2)
Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms.
The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2.
Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration.
(4)
The final distance matrix after completion of Floyd’s algorithm is shown in Table 3.
Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
Find the length of each of the two cycles.
State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route.
(4)
A linear programming problem in x, y and z is to be solved using the big‑M method. The initial tableau is shown below.
| b.v. | x | y | z | s1 | s2 | s3 | a1 | a2 | Value |
| s1 | 2 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 13 |
| a1 | 1 | –2 | 2 | 0 | –1 | 0 | 1 | 0 | 8 |
| a2 | 3 | 0 | –4 | 0 | 0 | –1 | 0 | 1 | 12 |
| P | 2 – 4M | –3 + 2M | –1 + 2M | 0 | M | M | 0 | 0 | –20M |
Using the information in the above tableau, formulate the linear programming problem. You should
• list each of the constraints as an inequality
• state the two possible objectives
(4)
Obtain the most efficient pivot for a first iteration of the big‑M method. You must give reasons for your answer.
Please turn over for Question 5
(2)
The network in Figure 2 shows the activities that need to be completed for a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times are shown in Figure 2.
Complete Table 1 in the answer book to show the immediately preceding activities for each activity.
It is given that 4 < x 
m
(2)
State the largest possible integer value of m.
(1)
Complete Diagram 1 in the answer book to show the late event times.
State the activities that must be critical.
(3)
Calculate the total float for activity G.
(1)
The resource histogram in Figure 3 shows the number of workers required when each activity starts at its earliest possible time. The histogram also shows which activities happen at each time.
Complete Table 2 in the answer book to show the number of workers required for each activity of the project.
(2)
Draw a Gantt chart on Grid 1 in the answer book to represent the activity network.
(5)
The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to Kn
Step 1 Start
Step 2 Input the value of n
| Step 3 | Let a = 1 | |
| Step 4 | Let b = n – 2 | |
| Step 5 | Let c = b | |
| Step 6 | Let a = a + 1 | |
| Step 7 | Let b = b – 1 |
Step 8 Let c = c + (a
b) + (a – 1)
Step 9 If b 
0 go to Step 6
Step 10 Output c
Step 11 Stop
For K5, complete the table in the answer book to show the results obtained at each step of the algorithm.
(3)
The weights of the ten arcs in Figure 4 are
17 21 24 14 23 13 15 19 28 20
Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
Find the total number of comparisons performed during the sort.
(5)
Find the maximum total number of comparisons required to sort the weights of the 10 arcs of K5 into ascending order using bubble sort.
(1)
It is given that the maximum total number of comparisons required to sort the weights of the arcs of Kn into ascending order using bubble sort is
λn (n – 1)(n + 1)(n – 2)
where λ is a constant.
Determine the maximum total number of comparisons required to sort the weights of the arcs of K50 into ascending order using bubble sort. You must make your method and working clear.
(3)
Figure 5 shows the constraints of a linear programming problem in x and y where R is the feasible region.
The objective is to maximise P = x + ky, where k is a positive constant.
The optimal vertex of R is to be found using the Simplex algorithm.
Set up an initial tableau for solving this linear programming problem using the Simplex algorithm.
(5)
After two iterations of the Simplex algorithm a possible tableau T is
| b.v. | x | y | s1 | s2 | s3 | s4 | Value |
| s1 | 0 | 0 | 1 |  53 | 0 | 1 5 | 1 |
| x | 1 | 0 | 0 | 1 5 | 0 |  52 | 2 |
| s3 | 0 | 0 | 0 |  115 | 1 | 12 5 | 22 |
| y | 0 | 1 | 0 | 2 5 | 0 | 1 5 | 5 |
| P | 0 | 0 | 0 | 15  52 k | 0 |  52  15 k | 5k + 2 |
State the value of each variable after the second iteration.
(1)
It is given that T does not give an optimal solution to the linear programming problem.
After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for P. You should state the row operations you use and make your method and working clear.
(9)
The paper as printed
Spotted a mistake on this page?Report a problem
