Question 17 - A-Level Maths

Edexcel D1 2022 January — Question 17

Exam Board	Edexcel
Module	D1 (Decision Mathematics 1)
Year	2022
Session	January
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Sorting Algorithms
Type	Lower Bound for Bins
Difficulty	Moderate -0.8 This is a standard D1 textbook exercise testing routine application of memorized algorithms (bin packing, quicksort, binary search) with no problem-solving or insight required. The calculations are straightforward and follow prescribed procedures exactly as taught, making it easier than average A-level maths questions which typically require some synthesis of techniques.
Spec	7.03k Sorting: quick sort 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

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.

Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.
Use the first-fit bin packing algorithm to allocate the boxes to the containers.
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.
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.

Show LaTeX source

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.\\
(a) Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.\\
(b) Use the first-fit bin packing algorithm to allocate the boxes to the containers.\\
(c) 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.\\
(d) 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.\\

\hfill \mbox{\textit{Edexcel D1 2022 Q17}}

This paper (9 questions)

View full paper

Q0 Q1 11 Q2 7 Q3 5 Q4 10 Q5 10 Q6 14 Q7 Q17