Problem

The twelve numbers in the list below are to be packed into bins of size $n$, where $n$ is a positive integer.

$28 \quad 31 \quad 5 \quad 25 \quad 16 \quad 35 \quad 18 \quad 22 \quad 11 \quad 27 \quad 15 \quad 13$

When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained.

Bin 1: $28 \quad 31 \quad 5$

Bin 2: $25 \quad 16 \quad 18$

Bin 3: $35 \quad 22 \quad 15$

Bin 4: $27 \quad 13 \quad 11$

(a) Based on the packing shown above, determine the possible values of $n$. You must give reasons for your answer.

(b) The original list of twelve 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.

When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained.

Bin 1: $35 \quad 31 \quad 5$

Bin 2: $28 \quad 27 \quad 16$

Bin 3: $25 \quad 22 \quad 18$

Bin 4: $15 \quad 13 \quad 11$

(c) Determine the value of $n$. You must give a reason for your answer.