| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Algorithm tracing and properties |
| Difficulty | Moderate -0.8 This is a straightforward algorithm tracing question on the Euclidean algorithm (HCF). Parts (i) and (ii) require mechanical execution of given steps with basic arithmetic. Part (iii) involves simple back-substitution to express the HCF as a linear combination, which is a standard textbook exercise requiring minimal problem-solving insight. The calculations are routine and the question structure is highly scaffolded. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt |
| A | B | Q | R 1 | R 2 |
| 30 | 42 | 1 | 12 | |
| 12 | 30 | 2 | 6 | |
| 6 | ||||
| 6 | 12 | 2 | 0 |
**(i)** Apply the first fit algorithm to the items in the order given and comment on the outcome. [3]
- M1: Correct application of first fit algorithm
- A1: Correct packing produced
- A1: Valid comment on outcome (e.g., inefficient use of space)
**(ii)** Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks. [3]
- M1: Correct ordering in descending order
- M1: Correct application of first fit decreasing algorithm
- A1: Correct final packing
**(iii)** Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing. [2]
- M1: Packing with more equal volume distribution
- A1: Valid explanation (e.g., awkward item combinations, weight distribution concerns)3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-004_888_693_422_717}
\captionsetup{labelformat=empty}
\caption{Fig. 3.1}
\end{center}
\end{figure}
(i) Run the algorithm with $\mathrm { A } = 84$ and $\mathrm { B } = 660$, showing all of your calculations.\\
(ii) Run the algorithm with $\mathrm { A } = 660$ and $\mathrm { B } = 84$, showing as many calculations as are necessary.\\
(iii) The algorithm is run with $\mathrm { A } = 30$ and $\mathrm { B } = 42$, and the result is shown in Table 3.2 below.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
A & B & Q & R 1 & R 2 \\
\hline
30 & 42 & 1 & 12 & \\
\hline
12 & 30 & 2 & & 6 \\
\hline
& & & 6 & \\
\hline
6 & 12 & 2 & & 0 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Print 6}
\end{center}
\end{table}
Table 3.2
The first line of the table shows that $12 = 42 - 1 \times 30$.\\
Use the second line to obtain a similar expression for 6 in terms of 30 and 12.\\
Hence express 6 in the form $\mathrm { m } \times 30 - \mathrm { n } \times 42$, where m and n are integers.
\hfill \mbox{\textit{OCR MEI D1 Q3 [12]}}