| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Fixed Point Iteration |
| Type | Apply iteration to find root (pure fixed point) |
| Difficulty | Easy -1.8 This is a straightforward algorithmic trace question requiring only basic arithmetic operations (addition, counting operations) and linear scaling. No mathematical insight or problem-solving is needed—just careful bookkeeping and following instructions mechanically. Significantly easier than typical A-level questions. |
| Spec | 7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt7.03g Order notation: O(n^k) for k = 0,1,2,3,4 |
| Step 1 | Let \(N = 0 , T = 0\) and \(S = 0\). | |||
| Step 2 |
| |||
| Step 3 | Increase \(N\) by 1 , increase \(T\) by \(X\) and increase \(S\) by \(X ^ { 2 }\). | |||
| Step 4 | If there are still numbers in the list then go back to Step 2. Otherwise go to Step 5. | |||
| Step 5 |
| |||
| Step 6 | Output \(M\) and \(D\). |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Table with columns \(X, N, T, S\): initial row \(0,0,0,0\); then \(3,1,3,9\); \(6,2,9,45\); \(5,3,14,70\); \(7,4,21,119\); \(3,5,24,128\) | M1 | For initial pass through step 3 correct |
| M1 | For updating each of \(N\), \(T\) and \(S\) correctly | |
| Final values of \(N\), \(T\) and \(S\) correct | A1 | |
| \(M = 4.8\) | B1 | For 4.8 (ft their \(T \div N\)) |
| \(D = 1.6\) | B1 | For 1.6 (ft their \(\sqrt{(S \div N) - (M^2)}\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 15 additions and 5 multiplications | B1 | |
| \(20 + 5 = 25\) | B1 | For 'their \(20\)' \(+ 5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(3n + n + 5 = 4n + 5\) | M1 | For any function of \(n\) that gives their answer from (ii) when \(n=5\) |
| \(= 4n + 5\) | A1 | For any expression that simplifies to \(4n+5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \((5000 \div 1000) \times 2 = 10\) seconds | B1 | Or \(2 \div 4005 \times 20005 = 9.99 \approx 10\) seconds |
# Question 5:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Table with columns $X, N, T, S$: initial row $0,0,0,0$; then $3,1,3,9$; $6,2,9,45$; $5,3,14,70$; $7,4,21,119$; $3,5,24,128$ | M1 | For initial pass through step 3 correct |
| | M1 | For updating each of $N$, $T$ and $S$ correctly |
| Final values of $N$, $T$ and $S$ correct | A1 | |
| $M = 4.8$ | B1 | For 4.8 (ft their $T \div N$) |
| $D = 1.6$ | B1 | For 1.6 (ft their $\sqrt{(S \div N) - (M^2)}$) |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| 15 additions and 5 multiplications | B1 | |
| $20 + 5 = 25$ | B1 | For 'their $20$' $+ 5$ |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $3n + n + 5 = 4n + 5$ | M1 | For any function of $n$ that gives their answer from (ii) when $n=5$ |
| $= 4n + 5$ | A1 | For any expression that simplifies to $4n+5$ |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| $(5000 \div 1000) \times 2 = 10$ seconds | B1 | Or $2 \div 4005 \times 20005 = 9.99 \approx 10$ seconds |
---5 Consider the following algorithm which is to be applied to a list of numbers.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Step 1 & Let $N = 0 , T = 0$ and $S = 0$. \\
\hline
Step 2 & \begin{tabular}{l}
Input the first number in the list and call it $X$. \\
Delete the first number from the list to give a list that has one number fewer than before. \\
\end{tabular} \\
\hline
Step 3 & Increase $N$ by 1 , increase $T$ by $X$ and increase $S$ by $X ^ { 2 }$. \\
\hline
Step 4 & If there are still numbers in the list then go back to Step 2. Otherwise go to Step 5. \\
\hline
Step 5 & \begin{tabular}{l}
Calculate $M = ( T$ divided by $N )$. \\
Calculate $V = ( S$ divided by $N ) - ( M$ squared $)$. \\
Calculate $D = \sqrt { } V$. \\
\end{tabular} \\
\hline
Step 6 & Output $M$ and $D$. \\
\hline
\end{tabular}
\end{center}
(i) Apply the algorithm to this list.
$$\begin{array} { l l l l l }
3 & 6 & 5 & 7 & 3
\end{array}$$
Record in a table the values of $X , N , T$ and $S$ at each pass through Step 3 and give the output values.\\
(ii) Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.\\
(iii) Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of $n$ numbers.\\
(iv) The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?
\hfill \mbox{\textit{OCR D1 2005 Q5 [10]}}