7.03c - OCR Spec

OCR MEI D1 2016 June Q2

8 marks Moderate -0.8

2 A bag contains 26 cards. A different letter of the alphabet is written on each one. A card is chosen at random and its letter is written down. The card is returned to the bag. The bag is shaken and the process is repeated several times. Tania wants to investigate the probability of a letter appearing twice. She wants to know how many cards need to be chosen for this probability to exceed 0.5. Tania uses the following algorithm. Step 1 Set $n = 1$ Step 2 Set $p = 1$ Step 3 Set $n = n + 1$ Step 4 Set $p = p \times \left( \frac { 27 - n } { 26 } \right)$ Step 5 If $p < 0.5$ then stop
Step 6 Go to Step 3

Run the algorithm.
Interpret your results. A well-known problem asks how many randomly-chosen people need to be assembled in a room before the probability of at least two of them sharing a birthday exceeds 0.5 (ignoring anyone born on 29 February).
Modify Tania's algorithm to answer the birthday problem. (Do not attempt to run your modified algorithm.)
Why have 29 February birthdays been excluded?

Edexcel D1 Q2

7 marks Moderate -0.8

2. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-03_1239_1442_306_283} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The data $$x _ { 1 } = 8 , \quad x _ { 2 } = 2 , \quad x _ { 3 } = 4 , \quad x _ { 4 } = 3 , \quad x _ { 5 } = 5 , \quad x _ { 6 } = 1 , \quad x _ { 7 } = 7 ,$$ is to be used in the algorithm given in Figure 1.

Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output using the given data.
Explain what the algorithm achieves for any set of data $x _ { 1 }$ to $x _ { n }$.

Edexcel D1 Q5

11 marks Moderate -0.5

5. This question should be answered on the sheet provided. An algorithm is described by the flow chart shown in Figure 1 below. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-05_1337_937_388_404} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output.
Explain what the algorithm achieves.
Attempt to apply the algorithm again, with the initial value of $a$, as specified in Box 2, changed to 5 . Explain what happens.
(2 mark)
Find the set of positive initial values of $a$ for which the algorithm will work.
(2 marks)

OCR D2 2005 June Q4

15 marks Moderate -0.5

4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( $5 ; 0$ ) and the exit as ( $0 ; 0$ ). He then counted the numbers of plants along paths. These numbers are shown below.

Stage 5	(5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants
Stage 4	(4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants	(4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants
Stage 3	( $3 ; 0$ ) to ( $2 ; 1$ ): 8 plants (3;0) to (2;3): 6 plants	(3;1) to (2;0): 7 plants $( 3 ; 1 )$ to (2;2): 6 plants	(3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( $3 ; 2$ ) to ( $2 ; 3$ ): 8 plants
Stage 2	(2; 0) to (1; 0): 4 plants ( $2 ; 0$ ) to ( $1 ; 1$ ): 5 plants	(2; 1) to (1; 0): 6 plants	(2;2) to (1;1): 7 plants	(2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants
Stage 1	(1;0) to (0;0): 4 plants	(1; 1) to (0;0): 4 plants

Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.

OCR D2 2009 June Q2

20 marks Standard +0.3

2

Set up a dynamic programming tabulation to find the maximum weight route from ( $0 ; 0$ ) to ( $3 ; 0$ ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.
Activity Duration Immediate predecessors
$A$ 8 -
$B$ 9 -
C 7 -
D 5 $A$
E 6 $A$
$F$ 4 $B$
$G$ 5 B
$H$ 6 $B$
$I$ 10 C
$J$ 9 $C$
$K$ 6 $C$
$L$ 7 D, F, I
$M$ 6 $E , G , J$
$N$ 8 $H$, $K$
Make a large copy of the network with the activities $A$ to $N$ labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
Compare the solutions to parts (i) and (ii).

OCR D2 2011 June Q6

9 marks Standard +0.3

6 Set up a dynamic programming tabulation to find the maximin route from ( $0 ; 0$ ) to ( $3 ; 0$ ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}

OCR D2 2012 June Q3

9 marks Moderate -0.5

3 Throughout this question all clock times are in Greenwich Mean Time (GMT).
An aeroplane needs to arrive at its destination at 3pm. The places it can pass through on its route are shown in the network, together with the flying times, in hours, between them. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-4_609_1523_486_255} Use a dynamic programming tabulation, working backwards from 3pm at the destination, to find the latest time that the aeroplane could set off. If the aeroplane takes off at its latest time, which places does it pass through, and at what time does it reach each of these places?

OCR Further Discrete AS 2019 June Q3

11 marks Moderate -0.5

3

Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started. Becky needs to sort a list of numbers into increasing order.
She uses the following algorithm:
STEP 1: Let $L$ be the first value in the input list.
Write this as the first value in the output list and delete it from the input list.
STEP 2: If the input list is empty go to STEP 7.
Otherwise let $N$ be the new first value in the input list and delete this value from the input list. STEP 3: $\quad$ Compare $N$ with $L$.
STEP 4: If $N$ is less than or equal to $L$
- write the value of $N$ immediately before $L$ in the output list,
- replace $L$ with the first value in the new output list,
- then go to STEP 2.
STEP 5: If $N$ is greater than $L$
- if $L$ is the value of the last number in the output list, go to STEP 6;
- otherwise, replace $L$ with the next value in the output list and then go to STEP 3.
STEP 6: $\quad$ Write the value of $N$ immediately after $L$ in the output list. Let $L$ be the first value in the new output list and then go to STEP 2. STEP 7: Print the output list and STOP.
Trace through Becky's algorithm when the input list is $$\begin{array} { l l l l l l } 6 & 9 & 5 & 7 & 6 & 4 \end{array}$$ Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
You should not need all the lines in the Answer Booklet. Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
1. How many times did Becky use STEP 3 in sorting the list from part (b)?
2. What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values? A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

OCR Further Discrete AS 2022 June Q1

4 marks Easy -1.2

1 The flowchart below has positive inputs $X , Y$ and $M$. \includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-2_1274_643_392_242}

Trace through the flowchart above using the inputs $X = 1 , Y = 2$ and $M = 2$. You only need to record values when they change.
Explain why the process in the flowchart is finite.

OCR Further Discrete AS 2020 November Q1

10 marks Standard +0.3

1 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

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.
Explain carefully how you know that algorithm X is finite for all positive integer values of $B$.
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$.
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.
Show that algorithm Y is more efficient than algorithm X .

Edexcel D1 2017 January Q1

4 marks Easy -1.8

Use the binary search algorithm to try to locate the name Hilbert in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage.

Edexcel D1 2018 June Q1

10 marks Easy -1.3

1. $$\begin{aligned} & \text { Kerry (K) } \\ & \text { Nikki (N) } \\ & \text { Violet (V) } \\ & \text { Dev (D) } \\ & \text { Henri (H) } \\ & \text { Leslie (L) } \\ & \text { Enlai (E) } \\ & \text { Sylvester (S) } \\ & \text { Joan (J) } \end{aligned}$$ A binary search is to be performed on the names in the list above to locate the name Leslie.

Explain why a binary search cannot be performed with the list in its present form.
Using an appropriate algorithm, alter the list so that a binary search can be performed. You should state the name of the algorithm you use and show the list after each complete iteration.
Use the binary search algorithm to locate the name Leslie in the altered list you obtained in (b). You must make your method clear. The binary search algorithm is to be used to search for a name in an alphabetical list of 727 names.
Find the maximum number of iterations needed. You should justify your answer.

Edexcel D1 2023 June Q3

6 marks Easy -1.8

3. In this question, the function $\operatorname { INT } ( X )$ is the largest integer less than or equal to $X$. For example, $$\begin{aligned} \mathrm { INT } ( 5.7 ) & = 5 \\ \mathrm { INT } ( 8 ) & = 8 \\ \mathrm { INT } ( - 2.3 ) & = - 3 \end{aligned}$$ Consider the following algorithm.
Step 1 Input $N$ Step 2 Calculate $A = N \div 10$ Step 3 Let $B = \operatorname { INT } ( A )$ Step 4 Calculate $C = B \times 10$ Step 5 Calculate $D = N - C$ Step 6 Output $D$ Step $7 \quad$ Replace $N$ by $B$ Step 8 If $N = 0$ then STOP, otherwise go back to Step 2

Complete the table in the answer book, using $N = 4217$, to show the results obtained at each step of the algorithm.
Explain how the output values of the algorithm relate to the original input $N$, where $N$ is any positive integer.

Edexcel D1 2013 Specimen Q1

8 marks Easy -1.8

1.

Hajra

$( \mathrm { H } )$

Vicky

$( \mathrm { V } )$

Leisham

$( \mathrm { L } )$

Alice

$( \mathrm { A } )$

Nicky

$( \mathrm { N } )$

June

$( \mathrm { J } )$

Sharon

$( \mathrm { S } )$

Tom

$( \mathrm { T } )$

Paul

$( \mathrm { P } )$

The table shows the names of nine people.

Use a quick sort to produce the list of names in ascending alphabetical order. You must make your pivots clear.
Use the binary search algorithm on your list to locate the name Paul.

Edexcel D1 2009 January Q1

9 marks Easy -1.8

1. Max Lauren John Hannah Kieran Tara Richard Imogen

Use a quick sort to produce a list of these names in ascending alphabetical order. You must make your pivots clear.
Use the binary search algorithm on your list from part (a) to try to locate the name 'Hugo'.

Edexcel D1 2010 January Q5

7 marks Easy -1.8

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{17bc9fb2-13bf-4ffa-93ac-bef170467570-6_2228_613_269_861} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} An algorithm is described by the flowchart shown in Figure 4.

Given that $\mathrm { S } = 25000$, complete the table in the answer book to show the results obtained at each step when the algorithm is applied. This algorithm is designed to model a possible system of income tax, T, on an annual salary, £S.
Write down the amount of income tax paid by a person with an annual salary of $\pounds 25000$.
Find the maximum annual salary of a person who pays no tax.

Edexcel D1 2013 January Q1

6 marks Moderate -0.8

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-2_1095_1104_292_475} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Hero's algorithm for finding a square root is described by the flow chart shown in Figure 1.
Given that $\mathrm { N } = 72$ and $\mathrm { E } = 8$,

use the flow chart to complete the table in the answer book, working to at least seven decimal places when necessary. Give the final output correct to seven decimal places. The flow chart is used with $\mathrm { N } = 72$ and $\mathrm { E } = - 8$,
describe how this would affect the output.
State the value of E which cannot be used when using this flow chart.

Edexcel D1 2013 January Q2

6 marks Easy -1.8

2.

Starting with a list of all the letters of the alphabet in alphabetical order, demonstrate how a binary search is used to locate the letter P. In each iteration, you must make clear your pivot and the part of the list you are retaining.
(4)
Find the maximum number of iterations needed to locate any particular letter of the alphabet. Justify your answer.

Edexcel D1 2002 June Q5

11 marks Easy -1.2

5. An algorithm is described by the flow chart below. \includegraphics[max width=\textwidth, alt={}, center]{652477eb-87dc-4a5a-8514-c9be39986142-5_1590_1264_363_539}

Given that $a = 645$ and $b = 255$, complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
Explain how your solution to part (a) would be different if you had been given that $a = 255$ and $b = 645$.
State what the algorithm achieves.

Edexcel D1 2016 June Q5

7 marks Easy -1.8

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-06_1388_1648_246_221} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} An algorithm is described by the flow chart shown in Figure 4. Given that $x = 27$ and $y = 5$,

complete the table in the answer book to show the results obtained at each step when the algorithm is applied. Give the final output. The numbers 122 and $\frac { 1 } { 2 }$ are to be used as inputs for the algorithm described by the flow chart.
1. State, giving a reason, which number should be input as $x$.
2. State the output.

Edexcel D1 Q2

4 marks Easy -1.8

2. Use the binary search algorithm to try to locate the name Hannah in the following alphabetical list. Clearly indicate how you selected your pivots and which part of the list is being rejected at each stage. \begin{displayquote} Adam
Ben
Charlie
Eleanor
Freya
Greg
Jenny
Richard
Toby \end{displayquote}

OCR FD1 AS 2017 December Q1

4 marks Moderate -0.8

1 \includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-2_953_559_347_753}

Trace through the flowchart above using the input $N = 97531$. You only need to record values when they change.
Explain why the process in the flowchart is finite.

OCR Further Discrete 2018 December Q4

13 marks Moderate -0.5

4 An algorithm is represented by the flow diagram below. \includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with $n = 4$ and the table of inputs $\mathrm { d } ( i , j )$ : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1 \\ & i = 2 \\ & i = 3 \\ & i = 4 \end{aligned}$$

0	3	5	2
3	0	4	3
5	4	0	1
2	3	1	0

An incomplete trace through the algorithm is shown below.

$n$	$i$	$j$	$\mathrm { d } ( i , j )$	A	$t$	$m$
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

The next box to be used is the box 'Let $i = t$ '.

Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
1. State how the output of the algorithm relates to the network represented by the matrix.
2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
3. Write down a limitation on the distances $\mathrm { d } ( i , j )$ for this algorithm.
Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with $n$ vertices, the run-time for the algorithm is given by $\alpha D + \beta T$, where $\alpha$ and $\beta$ are constants, $D$ is the number of times that a value of $\mathrm { d } ( i , j )$ is looked up and $T$ is the number of times that $t$ is updated.
Show how this means that the algorithm has $\mathrm { O } \left( n ^ { 2 } \right)$ complexity. A computer takes 3 seconds to run the algorithm for a problem with $n = 35$.
Use the complexity to calculate an approximate run-time for a problem with $n = 100$. The run-time using a second algorithm has $\mathrm { O } ( n ! )$ complexity.
A computer takes 2.8 seconds to run the second algorithm for a problem with $n = 35$.
Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with $n = 100$.

AQA D1 2006 January Q6

7 marks Easy -1.8

6 Two algorithms are shown. \section*{Algorithm 1}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $I = ( P * R * T ) / 100$
Line 50	Let $A = P + I$
Line 60	Let $M = A / ( 12 * T )$
Line 70	Print $M$
Line 80	Stop

\section*{Algorithm 2}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $A = P$
Line 50	$K = 0$
Line 60	Let $K = K + 1$
Line 70	Let $I = ( A * R ) / 100$
Line 80	Let $A = A + I$
Line 90	If $K < T$ then goto Line 60
Line 100	Let $M = A / ( 12 * T )$
Line 110	Print $M$
Line 120	Stop

In the case where the input values are $P = 400 , R = 5$ and $T = 3$ :

trace Algorithm 1;
trace Algorithm 2.

AQA D1 2007 January Q5

8 marks Easy -1.2

5 A student is using the following algorithm with different values of $A$ and $B$.

Line 10	Input $A , B$
Line 20	Let $C = 0$ and let $D = 0$
Line 30	Let $C = C + A$
Line 40	Let $D = D + B$
Line 50	If $C = D$ then go to Line 110
Line 60	If $C > D$ then go to Line 90
Line 70	Let $C = C + A$
Line 80	Go to Line 50
Line 90	Let $D = D + B$
Line 100	Go to Line 50
Line 110	Print $C$
Line 120	End

1. Trace the algorithm in the case where $A = 2$ and $B = 3$.
2. Trace the algorithm in the case where $A = 6$ and $B = 8$.
State the purpose of the algorithm.
Write down the final value of $C$ in the case where $A = 200$ and $B = 300$.

Activity	Duration	Immediate predecessors
\(A\)	8	-
\(B\)	9	-
C	7	-
D	5	\(A\)
E	6	\(A\)
\(F\)	4	\(B\)
\(G\)	5	B
\(H\)	6	\(B\)
\(I\)	10	C
\(J\)	9	\(C\)
\(K\)	6	\(C\)
\(L\)	7	D, F, I
\(M\)	6	\(E , G , J\)
\(N\)	8	\(H\), \(K\)

\(n\)	\(i\)	\(j\)	\(\mathrm { d } ( i , j )\)	A	\(t\)	\(m\)
4
					1
	1
				1		100
		1
			0
		2
			3
					2	3
		3
			5
		4
			2
					4	2
	4
				1, 4		100
		1
			2
		2
			3
					2	3
		3
			1
					3	1
		4
			0

Line 10	Input \(P\)
Line 20	Input \(R\)
Line 30	Input \(T\)
Line 40	Let \(I = ( P * R * T ) / 100\)
Line 50	Let \(A = P + I\)
Line 60	Let \(M = A / ( 12 * T )\)
Line 70	Print \(M\)
Line 80	Stop

Line 10	Input \(A , B\)
Line 20	Let \(C = 0\) and let \(D = 0\)
Line 30	Let \(C = C + A\)
Line 40	Let \(D = D + B\)
Line 50	If \(C = D\) then go to Line 110
Line 60	If \(C > D\) then go to Line 90
Line 70	Let \(C = C + A\)
Line 80	Go to Line 50
Line 90	Let \(D = D + B\)
Line 100	Go to Line 50
Line 110	Print \(C\)
Line 120	End

7.03c Working with algorithms: trace, interpret, adapt

OCR MEI D1 2016 June Q2

Edexcel D1 Q2

Edexcel D1 Q5

OCR D2 2005 June Q4

OCR D2 2009 June Q2

OCR D2 2011 June Q6

OCR D2 2012 June Q3

OCR Further Discrete AS 2019 June Q3

OCR Further Discrete AS 2022 June Q1

OCR Further Discrete AS 2020 November Q1

Edexcel D1 2017 January Q1

Edexcel D1 2018 June Q1

Edexcel D1 2023 June Q3

Edexcel D1 2013 Specimen Q1

Edexcel D1 2009 January Q1

Edexcel D1 2010 January Q5

Edexcel D1 2013 January Q1

Edexcel D1 2013 January Q2

Edexcel D1 2002 June Q5

Edexcel D1 2016 June Q5

Edexcel D1 Q2

OCR FD1 AS 2017 December Q1

OCR Further Discrete 2018 December Q4

AQA D1 2006 January Q6

AQA D1 2007 January Q5