| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Recurrence relation solution |
| Difficulty | Moderate -0.8 This is a straightforward algorithm trace question requiring systematic execution of given steps with no conceptual insight needed. Part (i) is routine iteration tracking, part (ii) tests understanding of the INT function with negatives (given in the question), and part (iii) recognizes the algorithm converts to base-B representation. All parts are mechanical with clear instructions, making this easier than average A-level content. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt8.02a Number bases: conversion and arithmetic in base n |
| Answer | Marks |
|---|---|
| \(F = N \div B\); \(G = \text{INT}(F)\); \(H = B \times G\); \(C = N - H\); \(N = G\) | For reference only |
| Answer | Marks | Guidance |
|---|---|---|
| F | G | H |
| 2.5 | 2 | 4 |
| 1 | 1 | 2 |
| 0.5 | 0 | 0 |
| A reasonable attempt at first pass (presented in any form) | M1 | |
| \(F = 2.5\) and \(G = 2\); \(H = 4\) (or double their \(G\) value) and \(C = 5 -\) their \(H\) | A1 | |
| \(F\), \(G\), \(H\), \(C\) and \(N\) correct for second pass (if their \(N\) value) | A1 | |
| \(F\), \(G\), \(H\), \(C\) and \(N\) correct for third pass (if their \(N\) value) | A1 | |
| [5] |
| Answer | Marks | Guidance |
|---|---|---|
| F | G | H |
| -2.5 | -3 | -6 |
| -1.5 | -2 | -4 |
| -1 | -1 | -2 |
| -0.5 | -1 | -2 |
| -0.5 | -1 | -2 |
| A reasonable attempt | M1 | |
| First pass correct (or implied) | M1 d | |
| Reaching two lines with the same value for \(G\) | A1 | |
| If described in words only, then M1 for a correct statement; M1 d for all correct statements (sufficient to guarantee result), and A1 for convincingly correct explanation of how they know these to be true and why the result follows | ||
| Does not terminate | B1 | |
| Saying 'does not stop', or equivalent | B1 | |
| [4] |
| Answer | Marks | Guidance |
|---|---|---|
| F | G | H |
| 3.7 | 3 | 30 |
| 0.3 | 0 | 0 |
| First pass correct | M1 | |
| All correct | A1 | |
| The first value is the units digit of \(N\), the second value is the tens digit, the third value is the hundreds digit, and so on. | M1 | |
| Outputs are digits of \(N\); In reverse order | A1 | |
| [4] |
$F = N \div B$; $G = \text{INT}(F)$; $H = B \times G$; $C = N - H$; $N = G$ | For reference only |
## (i)
| F | G | H | C | N |
|---|---|---|---|---|
| 2.5 | 2 | 4 | 1 | 2 |
| 1 | 1 | 2 | 0 | 1 |
| 0.5 | 0 | 0 | 1 | 0 |
A reasonable attempt at first pass (presented in any form) | M1 |
$F = 2.5$ and $G = 2$; $H = 4$ (or double their $G$ value) and $C = 5 -$ their $H$ | A1 |
$F$, $G$, $H$, $C$ and $N$ correct for second pass (if their $N$ value) | A1 |
$F$, $G$, $H$, $C$ and $N$ correct for third pass (if their $N$ value) | A1 |
| [5] |
## (ii)
| F | G | H | C | N |
|---|---|---|---|---|
| -2.5 | -3 | -6 | 1 | -3 |
| -1.5 | -2 | -4 | 1 | -2 |
| -1 | -1 | -2 | 0 | -1 |
| -0.5 | -1 | -2 | 1 | -1 |
| -0.5 | -1 | -2 | 1 | -1 |
A reasonable attempt | M1 |
First pass correct (or implied) | M1 d |
Reaching two lines with the same value for $G$ | A1 |
If described in words only, then M1 for a correct statement; M1 d for all correct statements (sufficient to guarantee result), and A1 for convincingly correct explanation of how they know these to be true and why the result follows | |
Does not terminate | B1 |
Saying 'does not stop', or equivalent | B1 |
| [4] |
## (iii)
| F | G | H | C | N |
|---|---|---|---|---|
| 3.7 | 3 | 30 | 7 | 3 |
| 0.3 | 0 | 0 | 3 | 0 |
First pass correct | M1 |
All correct | A1 |
The first value is the units digit of $N$, the second value is the tens digit, the third value is the hundreds digit, and so on. | M1 |
Outputs are digits of $N$; In reverse order | A1 |
| [4] |
---
**Total = 13**In this question, the function INT($X$) is the largest integer less than or equal to $X$. For example,
$$\text{INT}(3.6) = 3,$$
$$\text{INT}(3) = 3,$$
$$\text{INT}(-3.6) = -4.$$
Consider the following algorithm.
\begin{align}
\text{Step 1} \quad & \text{Input } B \\
\text{Step 2} \quad & \text{Input } N \\
\text{Step 3} \quad & \text{Calculate } F = N \div B \\
\text{Step 4} \quad & \text{Let } G = \text{INT}(F) \\
\text{Step 5} \quad & \text{Calculate } H = B \times G \\
\text{Step 6} \quad & \text{Calculate } C = N - H \\
\text{Step 7} \quad & \text{Output } C \\
\text{Step 8} \quad & \text{Replace } N \text{ by the value of } G \\
\text{Step 9} \quad & \text{If } N = 0 \text{ then stop, otherwise go back to Step 3}
\end{align}
\begin{enumerate}[label=(\roman*)]
\item Apply the algorithm with the inputs $B = 2$ and $N = 5$. Record the values of $F$, $G$, $H$, $C$ and $N$ each time Step 9 is reached. [5]
\item Explain what happens when the algorithm is applied with the inputs $B = 2$ and $N = -5$. [4]
\item Apply the algorithm with the inputs $B = 10$ and $N = 37$. Record the values of $F$, $G$, $H$, $C$ and $N$ each time Step 9 is reached. What are the output values when $B = 10$ and $N$ is any positive integer? [4]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2008 Q7 [13]}}