Problem

The following list of eleven numbers is to be packed into bins of size 14

$5.2 \quad 4.7 \quad 6.5 \quad 4.5 \quad 3.1 \quad 5.1 \quad 1.8 \quad 2.9 \quad 3.4 \quad 3.8 \quad 1.2$

(a) Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14.

(b) The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

(c) Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14.

(d) Explain why the number of bins used in part (c) is optimal.

(e) Use the binary search algorithm to try to locate 3.0 in the list of numbers. Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.