| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2020 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Algorithm tracing and properties |
| Difficulty | Standard +0.3 This is a straightforward algorithm tracing question with standard definitions (finite, deterministic) and basic complexity analysis. Part (a) is mechanical tracing, parts (b-d) test recall of standard definitions and simple reasoning about loop iterations, and part (e) requires comparing O(n) vs O(log n) complexity—all routine for Further Maths students studying discrete mathematics. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt7.03d Order of algorithm: dominant term and scaling run-times7.03f Worst case complexity: T(n) as function of problem size7.03g Order notation: O(n^k) for k = 0,1,2,3,4 |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | A 0 8 -1 |
| Answer | Marks |
|---|---|
| Output = 6 | B1 |
| Answer | Marks |
|---|---|
| [5] | Allow compressed rows or tables used differently |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (b) | Value of B is reduced by 1 each time that STEP 6 is used |
| until it reaches 0, when STEP 7 and STEP 8 mean that the algorithm stops | B1 |
| Answer | Marks |
|---|---|
| [2] | B reduces by 1 in each pass (NOT just B is a counter) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (c) | For any given input the output is always the same. |
| [1] | The output is a function of the input only | |
| 1 | (d) | B reduces to 0 after n passes through STEP 6, so run time is kn which is a |
| Answer | Marks |
|---|---|
| Hence efficiency is O(n) (as given in question) | B1 |
| [1] | Identifying n passes (allow n ± 1) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (e) | For large enough n, the run time of X increases more rapidly than the run- |
| time of Y. | B1 | Referring to ‘for large values of n’ (or B) and not just |
| Answer | Marks | Guidance |
|---|---|---|
| run-time of X > the run time of Y for all n > N. | B1 | Any reasonable attempt at number of digits in B that |
| Answer | Marks | Guidance |
|---|---|---|
| A | 0 | 8 |
| B | 5 | 4 |
| C | 1 | 1 |
| D | 8 | 7 |
| A | 7 | -5 |
| B | 2 | 1 |
| C | 0 | 0 |
| D | 2 | 1 |
Question 1:
1 | (a) | A 0 8 -1
B 5 4 3
C 1 1 1
D 8 7 6
A 7 -5 6
B 2 1 0
C 0 0
D 2 1
Output = 6 | B1
B1
M1
A1
B1
[5] | Allow compressed rows or tables used differently
Values of B are 5, 4, 3, 2, 1, 0
Values of C are 1, 1, 1, 0, 0
Ignore if there is an extra 0 at the end
Their first two D values = B + 3C
All D values correct: 8, 7, 6, 2, 1
Ignore if there is an extra 0 at the end
6
1 | (b) | Value of B is reduced by 1 each time that STEP 6 is used
until it reaches 0, when STEP 7 and STEP 8 mean that the algorithm stops | B1
B1
[2] | B reduces by 1 in each pass (NOT just B is a counter)
B reaches 0
or referring to STEP 7 and/or STEP 8 or STOP instruction
1 | (c) | For any given input the output is always the same. | B1
[1] | The output is a function of the input only
1 | (d) | B reduces to 0 after n passes through STEP 6, so run time is kn which is a
linear function of n
Hence efficiency is O(n) (as given in question) | B1
[1] | Identifying n passes (allow n ± 1)
Or ‘B reduces by 1 in each pass’ so (run time) is linear,
or equivalent
1 | (e) | For large enough n, the run time of X increases more rapidly than the run-
time of Y. | B1 | Referring to ‘for large values of n’ (or B) and not just
saying that the number of digits is smaller than n.
Not just specific examples.
Alternative method
The number of digits in B is 1 + INT(log B).
10
For any positive values of k and m there will be a value N for which the
run-time of X > the run time of Y for all n > N. | B1 | Any reasonable attempt at number of digits in B that
involves logarithms
A level candidates may give O(log n) ⊂ O(n)
Need not explain this
[1]
A | 0 | 8 | -1
B | 5 | 4 | 3
C | 1 | 1 | 1
D | 8 | 7 | 6
A | 7 | -5 | 6
B | 2 | 1 | 0
C | 0 | 0
D | 2 | 1
Alternative method
The number of digits in B is 1 + INT(log B).
10
For any positive values of k and m there will be a value N for which the
run-time of X > the run time of Y for all n > N.
B11 Algorithm X is given below:
STEP 1: $\quad$ Let $A = 0$\\
STEP 2: Input the value of $B \quad [ B$ must be a positive integer]\\
STEP 3: $\quad C = \operatorname { INT } ( B \div 3 )$\\
STEP 4: $D = B + 3 C$\\
STEP 5: $\quad$ Replace $A$ with $( D - A )$\\
STEP 6: Decrease $B$ by 1\\
STEP 7: If $B > 0$ go to STEP 3\\
STEP 8: Display the value of $\operatorname { ABS } ( A )$ and STOP
\begin{enumerate}[label=(\alph*)]
\item Trace through algorithm X when the input is $B = 5$.
Only record changes to the values of the variables, $A , B , C$ and $D$, using a new column of the table in the Printed Answer Booklet each time one of these variables changes.
\item Explain carefully how you know that algorithm X is finite for all positive integer values of $B$.
\item Explain what it means to say that an algorithm is deterministic.
The run-time of algorithm X is $k \times$ (number of times that STEP 6 is used), for some positive constant $k$.
\item Explain, with reference to your answer to part (b), why the order of algorithm X is $\mathrm { O } ( n )$, where $n$ is the input value of $B$.
For each input $B$, algorithm Y achieves the same output as algorithm X , but the run-time of algorithm Y is $m \times$ (the number of digits in $B$ ), where $m$ is a positive constant.
\item Show that algorithm Y is more efficient than algorithm X .
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2020 Q1 [10]}}