| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Decreasing Bin Packing |
| Difficulty | Easy -1.2 Part (a) is a straightforward application of the first-fit decreasing algorithm with small numbers requiring only basic arithmetic and list manipulation. Part (b) involves simple cubic scaling with given values. Both parts are routine procedural questions with no problem-solving insight required, making this easier than a typical A-level question. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Sorted list: 8 7 5 4 3 3 3 3 2 2 | M1 | For sorting the list into decreasing order |
| First bag: 8, 2; Second bag: 7, 3; Third bag: 5, 4; Fourth bag: 3, 3, 3; Fifth bag: 2 | M1 | For trying to apply first-fit to their list |
| Correct solution as above | A1 | For a completely correct solution |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| First bag: 8, 2; Second bag: 7, 3; Third bag: 5, 3, 2; Fourth bag: 4, 3, 3 | B1 | For any valid packing into four bags (may be as an incorrect answer to using algorithm, need not be packed in this order) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(\left(\frac{500}{100}\right)^3 \times 4\) or \(125000000 \times 0.000004\) | M1 | For scaling 4 seconds by \(5^3\) or equivalent valid and complete method. Condone minor errors with number of zeros |
| \(= 500\) | A1 | For 500 or 500 seconds or 500 s. Accept 8 minutes 20 seconds or 8.3 minutes |
# Question 1:
## Part (a)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Sorted list: 8 7 5 4 3 3 3 3 2 2 | M1 | For sorting the list into decreasing order |
| First bag: 8, 2; Second bag: 7, 3; Third bag: 5, 4; Fourth bag: 3, 3, 3; Fifth bag: 2 | M1 | For trying to apply first-fit to their list |
| Correct solution as above | A1 | For a completely correct solution |
## Part (a)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| First bag: 8, 2; Second bag: 7, 3; Third bag: 5, 3, 2; Fourth bag: 4, 3, 3 | B1 | For any valid packing into four bags (may be as an incorrect answer to using algorithm, need not be packed in this order) |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| $\left(\frac{500}{100}\right)^3 \times 4$ or $125000000 \times 0.000004$ | M1 | For scaling 4 seconds by $5^3$ or equivalent valid and complete method. Condone minor errors with number of zeros |
| $= 500$ | A1 | For 500 or 500 seconds or 500 s. Accept 8 minutes 20 seconds or 8.3 minutes |
---1
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg .
$$\begin{array} { l l l l l l l l l l }
2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3
\end{array}$$
\item Find a packing that uses fewer bags.
\end{enumerate}\item The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2005 Q1 [6]}}