6 P72799A   4. The eleven distinct numbers listed below are to be packed into bins of size 40 15 22 3 9 23 x 5 4 18 20 13 It is known that x • is an integer less than 40 • is the largest number in the list (a) Explain why it is not possible to pack the numbers into 3 bins of size 40 (1) Given that it is possible to pack the numbers into 4 bins of size 40 (b) determine the range of values for x (2) (c) Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40 (3) (d) Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. (4) When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin. (e) Determine the value of x. You must give reasons for your answer. (2) (Total for Question 4 is 12 marks)   7 Turn over P72799A BLANK PAGE 8 P72799A   5. A D G B E 34 18 23 21 33 20 50 12 8 65 42 10 17 22 48 H C F J Figure 5 [The total weight of the network is 423] Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. A B C D E F G H J A – 34 51 31 79 20 8 55 61 B 34 – 17 65 45 54 42 21 27 C 51 17 – 82 28 71 59 22 10 D 31 65 82 – 87 22 23 86 92 E 79 45 28 87 – 65 87 30 18 F 20 54 71 22 65 – 28 75 81 G 8 42 59 23 87 28 – 63 69 H 55 21 22 86 30 75 63 – 12 J 61 27 10 92 18 81 69 12 – Table of shortest distances   9 Turn over P72799A A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J. (a) (i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice. (ii) State the total length of this route. (5) (b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3) Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels. (c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2) (d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2) Pete decides to take the route he found in (c). (e) Interpret the route in terms of the actual towns visited. (1) (Total for Question 5 is 13 marks)