Problem

Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below.

8, 17, 9, 14, 18, 12, 22, 10, 15, 7

(a) Calculate a lower bound for the number of tour groups required. You must make your method clear.

(b) Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups.

The above list of numbers is to be sorted into descending order.

(c) Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

(d) Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups.

Figure 4 shows the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum’s entrance at A.

(e) Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.

(f) Write down a possible shortest route, giving its length.

Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.

(g) State the finishing vertex of Sally’s new route and calculate the difference in length between this new route and the route found in (f).

(Total 18 marks)