| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Fixed Point Iteration |
| Type | Apply iteration to find root (pure fixed point) |
| Difficulty | Moderate -0.8 This is a straightforward algorithm tracing exercise from D1, requiring systematic execution of given steps with basic arithmetic operations (squaring, square roots, INT function). Part (i)-(ii) involve routine trace-throughs, (iii) asks for simple explanation of algorithm logic, and (iv) applies basic big-O scaling (factor of 2 in √N). No novel problem-solving or deep insight required—purely mechanical application of a given algorithm. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt7.03g Order notation: O(n^k) for k = 0,1,2,3,4 |
| Line 10 | Input a positive integer, \(N\) |
| Line 20 | Let \(C = 1\) |
| Line 30 | If \(C ^ { 2 } \geqslant N\) jump to line 110 |
| Line 40 | Let \(X = \sqrt { \left( N - C ^ { 2 } \right) }\) [you may record your answer as a surd or a decimal] |
| Line 50 | Let \(Y = \operatorname { INT } ( X )\) |
| Line 60 | If \(X = Y\) jump to line 100 |
| Line 70 | If \(C > Y\) jump to line 110 |
| Line 80 | Add 1 to \(C\) |
| Line 90 | Go back to line 30 |
| Line 100 | Print \(C , X\) and stop |
| Line 110 | Print 'FAIL' and stop |
3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible.
The function $\operatorname { INT } ( X )$ gives the largest integer that is less than or equal to $X$. For example: $\operatorname { INT } ( 6.9 ) = 6$, $\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7$.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Line 10 & Input a positive integer, $N$ \\
\hline
Line 20 & Let $C = 1$ \\
\hline
Line 30 & If $C ^ { 2 } \geqslant N$ jump to line 110 \\
\hline
Line 40 & Let $X = \sqrt { \left( N - C ^ { 2 } \right) }$ [you may record your answer as a surd or a decimal] \\
\hline
Line 50 & Let $Y = \operatorname { INT } ( X )$ \\
\hline
Line 60 & If $X = Y$ jump to line 100 \\
\hline
Line 70 & If $C > Y$ jump to line 110 \\
\hline
Line 80 & Add 1 to $C$ \\
\hline
Line 90 & Go back to line 30 \\
\hline
Line 100 & Print $C , X$ and stop \\
\hline
Line 110 & Print 'FAIL' and stop \\
\hline
\end{tabular}
\end{center}
(i) Apply the algorithm to the input $N = 500$. You only need to write down values when they change and there is no need to record the use of lines $30,60,70$ or 90 .\\
(ii) Apply the algorithm to the input $N = 7$.\\
(iii) Explain why lines 70 and 110 are needed.
The algorithm has order $\sqrt { N }$.\\
(iv) If it takes 0.7 seconds to run the algorithm when $N = 3000$, roughly how long will it take when $N = 12000$ ?
\hfill \mbox{\textit{OCR D1 2014 Q3 [9]}}