| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.3 This is a straightforward algorithmic execution question requiring only mechanical application of bubble sort and first-fit decreasing bin packing algorithms with no problem-solving or insight. Students simply follow learned procedures step-by-step, making it significantly easier than average A-level maths questions which typically require some mathematical reasoning or technique selection. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
25 22 30 18 29 21 27 21
The list of numbers above is to be sorted into descending order.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Perform the first pass of a bubble sort, giving the state of the list after each exchange.
\item Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
\end{enumerate}
[5]
\end{enumerate}
The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumii}{1}
\item \begin{enumerate}[label=(\roman*)]
\item Show the result of applying the first fit decreasing bin packing algorithm to this situation.
\item Determine whether your solution to $(b)$ $(i)$ has used the minimum number of 50 cm rods.
\end{enumerate}
[4]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q6 [9]}}