7 P62678A Turn over 5. The nine distinct numbers in the following list are to be packed into bins of size 50 23        17        19        x        24        8        18        10        21 When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1:    23        17          8 Bin 2:    19          x        10 Bin 3:    24        18 Bin 4:    21 (a) Explain why 13 < x < 21 (3) The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is 23        19        17        24        x        18        10        21        8 (b) Using this information, write down the smallest interval that must contain x, giving your answer as an inequality. (2) When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1:    24        23 Bin 2:    21        19        10 Bin 3:    18        17          x Bin 4:      8 Given that only one of the bins is full and that x is an integer, (c) calculate the value of x. You must give reasons for your answer. (2) (Total for Question 5 is 7 marks) 8 P62678A 6. C G E D B A F 19 24 65 42 21 y 15 24 34 45 x 31 Figure 4 [The total weight of the network is 320 + x + y] (a) State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. (2) The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 < x < 26 and the weight on arc DG is y where 0 < y < 10 An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409 It is also given that the length of the shortest route from F to G via A is 140 (b) Using appropriate algorithms, find the value of x and the value of y. (9) (Total for Question 6 is 11 marks)