| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.3 This is a straightforward application of standard bin-packing algorithms (first-fit and first-fit decreasing) with simple arithmetic, followed by a basic quadratic scaling calculation. All parts require only direct application of learned procedures with no problem-solving or insight needed—significantly easier than average A-level questions. |
| Spec | 7.03d Order of algorithm: dominant term and scaling run-times7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
The memory requirements, in KB, for eight computer files are given below.
43 \quad 172 \quad 536 \quad 17 \quad 314 \quad 462 \quad 220 \quad 231
The files are to be grouped into folders. No folder is to contain more than 1000 KB, so that the folders are small enough to transfer easily between machines.
\begin{enumerate}[label=(\roman*)]
\item Use the first-fit method to group the files into folders. [3]
\item Use the first-fit decreasing method to group the files into folders. [3]
\end{enumerate}
First-fit decreasing is a quadratic order algorithm.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers? [2]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2009 Q1 [8]}}