2 P72094A 1. 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. (a) Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear. (2) (b) Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string. (3) (Total for Question 1 is 5 marks) 3 Turn over P72094A 2. A B C D E F 10 10 10 31 17 6 G H J K 23 25 8 14 14 18 9 3 4 16 23 33 25 Figure 1 [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. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to K. (ii) 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. (b) (i) State the edges that will need to be traversed twice. (ii) 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. (c) 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) (Total for Question 2 is 13 marks)