| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Algorithm Tracing |
| Difficulty | Easy -1.2 This is a straightforward algorithm tracing question requiring mechanical application of given procedures (Collatz conjecture and first-fit bin packing). Parts (a)(i-ii) and (b)(i-iii) involve simple step-by-step execution with no problem-solving. Part (a)(iv) tests basic understanding of algorithm definition (finiteness), and (b)(iv-v) require simple examples and complexity calculation. All parts are routine D1 content with no novel insight required, making it easier than average A-level questions. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03b Algorithm awareness: uses and practical limitations7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Item | A | B | C | D | E | F |
| Weight \(( \mathrm { kg } )\) | 2 | 1 | 6 | 3 | 3 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) (i) \(6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \ldots\) (can stop at second "4") | M1, A1 | \(6 \to 3 \to 10\) |
| (a) (ii) \(256 \to 128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \ldots\) (as above, or can note repetition from "16") | M1, A1 | \(256 \to 128 \to 64\) |
| (a) (iii) e.g. Step 25 If n is 1 then stop. (Any step number between 21 and 29, or indicated in some other way.) | B1 | ISW, but "Step 35" is wrong. |
| (a) (iv) Need to know that all chosen numbers lead to 1. | B1 | |
| (b) (i) Box 1: 2 1 6; A B C; Box 2: 3 3; D E; Box 3: 5; F; 3 boxes | B1, B1, B1 | |
| (b) (ii) 1 2 3 3 5 6; B A D E F C; Box 1: 1 2 3 3; B A D E; Box 2: 5; F; Box 3: 6; C | B1, B1 | sorted increasing |
| (b) (iii) (6 5 3 3 2 1); (C F D E A B); (C F F E D A B); Box 1: 6 3 1; C D B; Box 2: 5 3 2; F E A | M1, A1 | placing a "3" or D or E into box 1 |
| Answer | Marks | Guidance |
|---|---|---|
| (b) (iv) e.g. (for fitting into boxes of size 10): 6 3 3 2 2 2 2; Reducing order/first fit: Box 1: 6 3; Box 2: 3 2 2 2; Box 3: 2; Optimal: Box 1: 6 2 2; Box 2: 3 3 2 2 | M1, A1 | valid example; correctly doing it |
| (b) (v) \(30 \times (60/60)^2 = 3000\) secs ... 50 minutes | M1, A1 | multiplying 30 by a squared value |
**(a) (i)** $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \ldots$ (can stop at second "4") | M1, A1 | $6 \to 3 \to 10$
**(a) (ii)** $256 \to 128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \ldots$ (as above, or can note repetition from "16") | M1, A1 | $256 \to 128 \to 64$
**(a) (iii)** e.g. Step 25 If n is 1 then stop. (Any step number between 21 and 29, or indicated in some other way.) | B1 | ISW, but "Step 35" is wrong.
**(a) (iv)** Need to know that all chosen numbers lead to 1. | B1 |
**(b) (i)** Box 1: 2 1 6; A B C; Box 2: 3 3; D E; Box 3: 5; F; 3 boxes | B1, B1, B1 |
**(b) (ii)** 1 2 3 3 5 6; B A D E F C; Box 1: 1 2 3 3; B A D E; Box 2: 5; F; Box 3: 6; C | B1, B1 | sorted increasing
**(b) (iii)** (6 5 3 3 2 1); (C F D E A B); (C F F E D A B); Box 1: 6 3 1; C D B; Box 2: 5 3 2; F E A | M1, A1 | placing a "3" or D or E into box 1
## Question 5 (continued):
**(b) (iv)** e.g. (for fitting into boxes of size 10): 6 3 3 2 2 2 2; Reducing order/first fit: Box 1: 6 3; Box 2: 3 2 2 2; Box 3: 2; Optimal: Box 1: 6 2 2; Box 2: 3 3 2 2 | M1, A1 | valid example; correctly doing it
**(b) (v)** $30 \times (60/60)^2 = 3000$ secs ... 50 minutes | M1, A1 | multiplying 30 by a squared value5
\begin{enumerate}[label=(\alph*)]
\item The following instructions operate on positive integers greater than 4.\\
Step 10 Choose any positive integer greater than 4, and call it $n$.\\
Step 15 Write down $n$.\\
Step 20 If $n$ is even then let $n = \frac { n } { 2 }$ and write down the result.\\
Step 30 If $n$ is odd then let $n = 3 n + 1$ and write down the result.\\
Step 40 Go to Step 20.
\begin{enumerate}[label=(\roman*)]
\item Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
\item Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
\item Add an instruction to stop the process when $n$ becomes 1 .
\item It is not known if, when modified to stop cycling through $4,2,1$, the instructions form an algorithm. What would need to be known for it to be an algorithm?
\end{enumerate}\item Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .
\begin{center}
\begin{tabular}{ | l | c | c | c | c | c | c | }
\hline
Item & A & B & C & D & E & F \\
\hline
Weight $( \mathrm { kg } )$ & 2 & 1 & 6 & 3 & 3 & 5 \\
\hline
\end{tabular}
\end{center}
The first-fit algorithm is as follows.\\
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
\begin{enumerate}[label=(\roman*)]
\item Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
\item Place the items in increasing order of weight, and then apply the first-fit algorithm.
\item Place the items in decreasing order of weight, and then apply the first-fit algorithm.
An optimal solution is one which uses the least number of boxes.
\item Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
\item First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2014 Q5 [16]}}