Edexcel FD1 2020 June — Question 5

Exam BoardEdexcel
ModuleFD1 (Further Decision 1)
Year2020
SessionJune
TopicSorting Algorithms

5. The nine distinct numbers in the following list are to be packed into bins of size 50 $$\begin{array} { l l l l l l l l l } 23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21 \end{array}$$ When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23178
Bin 2: \(19 \quad x \quad 10\)
Bin 3: 2418
Bin 4: 21
  1. Explain why \(13 < x < 21\) 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 $$\begin{array} { l l l l l l l l l } 23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8 \end{array}$$
  2. Using this information, write down the smallest interval that must contain \(x\), giving your answer as an inequality. When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 2423
    Bin 2: 211910
    Bin 3: \(1817 x\)
    Bin 4: 8
    Given that only one of the bins is full and that \(x\) is an integer,
  3. calculate the value of \(x\). You must give reasons for your answer.