Lower Bound for Bins

1. A gardener needs the following lengths of string. All lengths are in metres.
   0.4
   1.7
   1.3
   2.5
   2.1
   3.4
   4.3
   4.7
   5.1
   5.9
   6.1

She cuts the lengths from balls of string. Each ball contains 10 m of string.

1. 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.

41 28 42 31 36 32 29 The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms.

1. Calculate a lower bound for the number of crates that will be needed to transport the statues. [2]
2. Use the first-fit bin packing algorithm to allocate the statues to the crates. [3]
3. Use the full bin algorithm to allocate the statues to the crates. [2]
4. Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c). [2]

(Total 9 marks)

17 & 9 & 15 & 8 & 20 & 13 & 28 & 4 & 12 & 5 \end{array}$$ The numbers in the list shown above are the weights, in kilograms, of ten boxes. The boxes are to be transported in containers that will each hold a maximum weight of 40 kilograms.

1. Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.
2. Use the first-fit bin packing algorithm to allocate the boxes to the containers.
3. Using the list provided, carry out a quick sort to produce a list of the weights in ascending order. You must make your pivots clear.
4. Use the binary search algorithm to try to locate the weight of 9 in the sorted list. Clearly indicate how you choose your pivots and which part of the list is being rejected at each stage.