7.03c Working with algorithms: trace, interpret, adapt

1 A student is using the algorithm below. Trace the algorithm in the case where \(A = 5\) and \(B = 3\).

6 A student is tracing the following algorithm.
Line 10 Let \(A = 6\) Line \(20 \quad\) Let \(B = 7\) Line 30 Input \(C\) Line 40 Let \(D = ( A + B ) / 2\) Line \(50 \quad\) Let \(E = C - D ^ { 3 }\) Line 60 If \(E ^ { 2 } < 1\) then go to Line 120
Line 70 If \(E > 0\) then go to Line 100
Line 80 Let \(B = D\) Line 90 Go to Line 40
Line \(100 \quad\) Let \(A = D\) Line 110 Go to Line 40
Line 120 Stop

1. Trace the algorithm in the case where the input value is \(C = 300\).
2. The algorithm is intended to find the approximate cube root of any input number. State two reasons why the algorithm is unsatisfactory in its present form.
   (3 marks)

8 The following algorithm finds an estimate of the value of the number represented by the symbol e:

1. Trace the algorithm.
2. A student miscopied Line 70 . His line was
   Line 70 Go to Line 10
   Explain what would happen if his algorithm were traced.

6 A student is tracing the following algorithm. The function INT gives the integer part of any number, eg \(\operatorname { INT } ( 2.3 ) = 2\) and \(\operatorname { INT } ( 6.7 ) = 6\). Line 10 Input \(A , B\) Line \(20 \quad\) Let \(C = \operatorname { INT } ( A \div B )\) Line 30 Let \(D = B \times C\) Line \(40 \quad\) Let \(E = A - D\) Line 50 If \(E = 0\) then go to Line 90
Line 60 Let \(A = B\) Line \(70 \quad\) Let \(B = E\) Line 80 Go to Line 20
Line 90 Print \(B\) Line 100 Stop

1. Trace the algorithm when the input values are:
   1. \(A = 36\) and \(B = 16\);
   2. \(A = 11\) and \(B = 7\).
2. State the purpose of the algorithm.

1 The flow chart shows an algorithm for which the input is a three-digit positive integer. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-2_1294_1493_356_328}

1. Trace through the algorithm using the input \(A = 614\) to show that the output is 297 . Write down the values of \(A , B , C\) and \(D\) in each pass through the algorithm.
2. What is the output when \(A = 616\) ?
3. Explain why the counter \(C\) is needed.

5 Consider the following algorithm which is to be applied to a list of numbers.

1. 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.
2. 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.
3. Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
4. 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?

2 Consider the following algorithm.
STEP 1 Input a number \(N\) STEP 2 Calculate \(R = N \div 2\) STEP 3 Calculate \(S = ( ( N \div R ) + R ) \div 2\) STEP 4 If \(R\) and \(S\) are the same when rounded to 2 decimal places, go to STEP 7
STEP 5 Replace \(R\) with the value of \(S\) STEP 6 Go to STEP 3
STEP 7 Output the value of \(R\) correct to 2 decimal places

1. Work through the algorithm starting with \(N = 16\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
2. Work through the algorithm starting with \(N = 2\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
3. What does the algorithm achieve for positive inputs?
4. Show that the algorithm fails when it is applied to \(N = - 4\).
5. Describe what happens when the algorithm is applied to \(N = - 2\). Suggest how the algorithm could be improved to avoid this problem, without imposing a restriction on the allowable input values.

3 Holly has written an algorithm.

1. Work through Holly's algorithm using the input values \(A = 30\) and \(B = 18\). Set out your working using the table in the answer book. Use one row for each step where any values change and only write down values when they change. Write down the values that are printed.
2. Describe what happens when \(A = 18\) and \(B = 30\). You need only record enough rows of the table to be able to show what happens.
3. Without doing further working, state the output values of \(F\) and \(M\) when \(A = 12\) and \(B = 8\).

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\).

1. 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 .
2. Apply the algorithm to the input \(N = 7\).
3. Explain why lines 70 and 110 are needed. The algorithm has order \(\sqrt { N }\).
4. If it takes 0.7 seconds to run the algorithm when \(N = 3000\), roughly how long will it take when \(N = 12000\) ?

4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, \(A\) and \(B\).
Let \(C = 0\) Step 2: If \(B\) is odd, replace \(C\) by \(C + A\).
Step 3: If \(B = 1\), go to step 6.
Step 4: Replace \(A\) by \(2 A\).
If \(B\) is even, replace \(B\) by \(B \div 2\), otherwise replace \(B\) by ( \(B - 1\) ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of \(C\).

1. Demonstrate the use of the algorithm for the inputs \(A = 6\) and \(B = 13\).
2. When \(B = 8\), what is the output in terms of \(A\) ? What is the relationship between the output and the original inputs?

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h] \end{figure}

1. Run the algorithm with \(\mathrm { A } = 84\) and \(\mathrm { B } = 660\), showing all of your calculations.
2. Run the algorithm with \(\mathrm { A } = 660\) and \(\mathrm { B } = 84\), showing as many calculations as are necessary.
3. The algorithm is run with \(\mathrm { A } = 30\) and \(\mathrm { B } = 42\), and the result is shown in Table 3.2 below. \begin{table}[h]

   A	B	Q	R 1	R 2
   30	42	1	12
   12	30	2		6
   			6
   6	12	2		0

   \captionsetup{labelformat=empty} \caption{Print 6}
   \end{table} Table 3.2 The first line of the table shows that \(12 = 42 - 1 \times 30\).
   Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
   Hence express 6 in the form \(\mathrm { m } \times 30 - \mathrm { n } \times 42\), where m and n are integers.

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h] \end{figure}

1. Run the algorithm with \(\mathrm { A } = 84\) and \(\mathrm { B } = 660\), showing all of your calculations.
2. Run the algorithm with \(\mathrm { A } = 660\) and \(\mathrm { B } = 84\), showing as many calculations as are necessary.
3. The algorithm is run with \(\mathrm { A } = 30\) and \(\mathrm { B } = 42\), and the result is shown in Table 3.2 below. \begin{table}[h]

   A	B	Q	R 1	R 2
   30	42	1	12
   12	30	2		6
   			6
   6	12	2		0

   \captionsetup{labelformat=empty} \caption{Print 6}
   \end{table} Table 3.2 The first line of the table shows that \(12 = 42 - 1 \times 30\).
   Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
   Hence express 6 in the form \(\mathrm { m } \times 30 - \mathrm { n } \times 42\), where m and n are integers.

3 The following algorithm (J. M. Oudin, 1940) claims to compute the date of Easter Sunday in the Gregorian calendar system.
The algorithm uses the year, y, to give the month, m, and day, d, of Easter Sunday.
All variables are integers and all remainders from division are dropped. For example, 7 divided by 3 is 2 remainder 1 . The remainder is dropped, giving the answer 2. $$\begin{aligned} & c = y / 100 \\ & n = y - 19 \times ( y / 19 ) \\ & k = ( c - 17 ) / 25 \\ & i = c - ( c / 4 ) - ( c - k ) / 3 + ( 19 \times n ) + 15 \\ & i = i - 30 \times ( i / 30 ) \\ & i = i - ( i / 28 ) \times ( 1 - ( i / 28 ) \times ( 29 / ( i + 1 ) ) \times ( ( 21 - n ) / 11 ) ) \\ & j = y + ( y / 4 ) + i + 2 - c + ( c / 4 ) \\ & j = j - 7 \times ( j / 7 ) \\ & p = i - j \\ & m = 3 + ( p + 40 ) / 44 \\ & d = p + 28 - 31 \times ( m / 4 ) \end{aligned}$$ For example, for 2008: \(\mathrm { y } = 2008\) \(\mathrm { c } = 2008 / 100 = 20\) \(n = 2008 - 19 \times ( 2008 / 19 ) = 2008 - 19 \times ( 105 ) = 13\), etc.
Complete the calculation for 2008.

2 The following algorithm computes the number of comparisons made when Prim's algorithm is applied to a complete network on \(n\) vertices ( \(n > 2\) ). Step 1 Input the value of \(n\) Step 2 Let \(i = 1\) Step 3 Let \(j = n - 2\) Step 4 Let \(k = j\) Step 5 Let \(i = i + 1\) Step 6 Let \(j = j - 1\) Step 7 Let \(k = k + ( i \times j ) + ( i - 1 )\) Step 8 If \(j > 0\) then go to Step 5
Step 9 Print \(k\) Step 10 Stop

1. Apply the algorithm when \(n = 5\), showing the intermediate values of \(i , j\) and \(k\). The function \(\mathrm { f } ( n ) = \frac { 1 } { 6 } n ^ { 3 } - \frac { 7 } { 6 } n + 1\) gives the same output as the algorithm.
2. Showing your working, check that \(\mathrm { f } ( 5 )\) is the same value as your answer to part (i).
3. What does the structure of \(\mathrm { f } ( n )\) tell you about Prim's algorithm?

2 The following is called the '1089' algorithm. In steps 1 to 4 numbers are to be written with exactly three digits; for example 42 is written as 042. Step 1 Choose a 3-digit number, with no digit being repeated.
Step 2 Form a new number by reversing the order of the three digits.
Step 3 Subtract the smaller number from the larger and call the difference D. If the two numbers are the same then \(\mathrm { D } = 000\). Step 4 Form a new number by reversing the order of the three digits of D , and call it R .
Step 5 Find the sum of D and R .

1. Apply the algorithm, choosing 427 for your 3-digit number, and showing all of the steps.
2. Apply the algorithm to a 3-digit number of your choice, showing all of the steps.
3. Investigate what happens if digits may be repeated in the 3 -digit number in step 1 .

3 The following algorithm computes an estimate of the square root of a number which is between 0 and 2.
Step 1 Subtract 1 from the number and call the result \(x\) Step 2 Set oldr = 1
Step 3 Set \(i = 1\) Step 4 Set \(j = 0.5\) Step 5 Set \(k = 0.5\) Step 6 Set change \(= x ^ { i } \times k\) Step 7 Set newr \(=\) oldr + change
Step 8 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 9 Set oldr = newr
Step 10 Set \(i = i + 1\) Step 11 Set \(j = j - 1\) Step 12 Set \(k = k \times j \div i\) Step 13 Set change \(= x ^ { i } \times k\) Step 14 Set newr \(=\) oldr + change
Step 15 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 16 Go to Step 9
Step 17 Print out newr

1. Use the algorithm to find an estimate of the square root of 1.44 , showing all of the steps.
2. Consider what happens if the algorithm is applied to 0.56 , and then use your four values of change from part (i) to calculate an estimate of the square root of 0.56 .

3 An incomplete algorithm is specified in Fig. 3. \(\mathrm { f } ( \mathrm { x } ) = \mathrm { x } ^ { 2 } - 2\) Initial values: \(\mathrm { L } = 0 , \mathrm { R } = 2\).
Step 1 Compute \(\mathrm { M } = \frac { \mathrm { L } + \mathrm { R } } { 2 }\).
Step 2 Compute \(\mathrm { f } ( \mathrm { M } )\).
Step 3 If \(\mathrm { f } ( \mathrm { M } ) < 0\) change the value of L to that of M .
Otherwise change the value of \(R\) to that of \(M\).
Step 4 Go to Step 1. \section*{Fig. 3}

1. Apply two iterations of the algorithm.
2. After 10 iterations \(\mathrm { L } = 1.414063 , \mathrm { R } = 1.416016 , \mathrm { M } = 1.416016\) and \(\mathrm { f } ( \mathrm { M } ) = 0.005100\). Say what the algorithm achieves.
3. Say what is needed to complete the algorithm.

6 In winter in Metland the weather each day can be classified as dry, wet or snowy. The table shows the probabilities for the next day's weather given the current day's weather. You are to use two-digit random numbers to simulate the winter weather in Metland.

1. Give an efficient rule for using two-digit random numbers to simulate tomorrow's weather if today is
   (A) dry,
   (B) wet,
   (C) snowy.
2. Today is a dry winter's day in Metland. Use the following two-digit random numbers to simulate the next 7 days' weather in Metland. $$\begin{array} { l l l l l l l l l l } 23 & 85 & 98 & 99 & 56 & 47 & 82 & 14 & 03 & 12 \end{array}$$
3. Use your simulation from part (ii) to estimate the proportion of dry days in a Metland winter.
4. Explain how you could use simulation to produce an improved estimate of the proportion of dry days in a Metland winter.
5. Give two criticisms of this model of weather.

2 The following algorithm acts on a list of three or more numbers.
Step 1: Set both X and Y equal to the first number on the list.
Step 2: If there is no next number then go to Step 5.
Step 3: If the next number on the list is bigger than X then set X equal to it. If it is less than Y then set Y equal to it. Step 4: Go to Step 2.
Step 5: Delete a number equal to X from the list and delete a number equal to Y from the list.
Step 6: If there is one number left then record it as the answer and stop.
Step 7: If there are two numbers left then record their mean as the answer and stop.
Step 8: Go to Step 1.

1. Apply the algorithm to the list \(5,14,153,6,24,2,14,15\), counting the number of comparisons which you have to make.
2. Apply the algorithm to the list \(5,14,153,6,24,2,14\), counting the number of comparisons which you have to make.
3. Say what the algorithm is finding.
4. The order of the algorithm is quadratic. Explain what this means when it is applied to long lists.

4 Joe is to catch a plane to go on holiday. He has arranged to leave his car at a car park near to the airport. There is a bus service from the car park to the airport, and the bus leaves when there are at least 15 passengers on board. Joe is delayed getting to the car park and arrives needing the bus to leave within 15 minutes if he is to catch his plane. He is the \(10 ^ { \text {th } }\) passenger to board the bus, so he has to wait for another 5 passengers to arrive. The distribution of the time intervals between car arrivals and the distribution of the number of passengers per car are given below.

1. Give an efficient rule for using 2-digit random numbers to simulate the intervals between car arrivals.
2. Give an efficient rule for using 2-digit random numbers to simulate the number of passengers in a car.
3. The incomplete table in your answer book shows the results of nine simulations of the situation. Complete the table, showing in each case whether or not Joe catches his plane.
4. Use the random numbers provided in your answer book to run a tenth simulation.
   [0pt]
5. Estimate the probability of Joe catching his plane. State how you could improve your estimate. [2]

4 The diagram represents a very simple maze with two vertices, A and B. At each vertex a rat either exits the maze or runs to the other vertex, each with probability 0.5 . The rat starts at vertex A . \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-4_79_930_534_571}

1. Describe how to use 1-digit random numbers to simulate this situation.
2. Use the random digits provided in your answer book to run 10 simulations, each starting at vertex A. Hence estimate the probability of the rat exiting at each vertex, and calculate the mean number of times it runs between vertices before exiting. The second diagram represents a maze with three vertices, A, B and C. At each vertex there are three possibilities, and the rat chooses one, each with probability \(1 / 3\). The rat starts at vertex A. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-4_566_889_1082_589}
3. Describe how to use 1-digit random numbers to simulate this situation.
4. Use the random digits provided in your answer book to run 10 simulations, each starting at vertex A. Hence estimate the probability of the rat exiting at each vertex.

2 The following steps define an algorithm which acts on two numbers.
STEP 1 Write down the two numbers side by side on the same row.
STEP 2 Beneath the left-hand number write down double that number. Beneath the right-hand number write down half of that number, ignoring any remainder. STEP 3 Repeat STEP 2 until the right-hand number is 1.
STEP 4 Delete those rows where the right-hand number is even. Add up the remaining left-hand numbers. This is the result.

1. Apply the algorithm to the left-hand number 3 and the right-hand number 8.
2. Apply the algorithm to the left-hand number 26 and the right-hand number 42.
3. Use your results from parts (i) and (ii), together with any other examples you may choose, to write down what the algorithm achieves.

5 The diagram shows the progress of a drunkard towards his home on one particular night. For every step which he takes towards his home, he staggers one step diagonally to his left or one step diagonally to his right, randomly and with equal probability. There is a canal three steps to the right of his starting point, and no constraint to the left. On this particular occasion he falls into the canal after 5 steps. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-5_723_622_488_724}

1. Explain how you would simulate the drunkard's walk, making efficient use of one-digit random numbers.
2. Using the random digits in the Printed Answer Book simulate the drunkard's walk and show his progress on the grid. Stop your simulation either when he falls into the canal or when he has staggered 6 steps, whichever happens first.
3. How could you estimate the probability of him falling into the canal within 6 steps? On another occasion the drunkard sets off carrying a briefcase in his right hand. This changes the probabilities of him staggering to the right to \(\frac { 2 } { 3 }\), and to the left to \(\frac { 1 } { 3 }\).
4. Explain how you would now simulate this situation.
5. Simulate the drunkard's walk (with briefcase) 10 times, and hence estimate the probability of him falling into the canal within 6 steps. (In your simulations you are not required to show his progress on a grid. You only need to record his steps to the right or left.)

2 This question concerns the following algorithm which operates on a given function, f. The algorithm finds a point between A and B at which the function has a minimum, with a maximum error of 0.05 .

1. Working correct to three decimal places, perform two iterations of the algorithm for \(\mathrm { f } ( x ) = 2 x ^ { 2 } - 15 x + 30\), when \(\mathrm { A } = 3\) and \(\mathrm { B } = 4\). Start at Step 1 and stop when you reach Step 8 for the second time.
2. The \(\left( \frac { \sqrt { 5 } - 1 } { 2 } \right)\) factor in Step 3 ensures that either the new ' \(L\) ' is equal to the old ' \(R\) ', or vice versa. Why is this important?
3. This algorithm is used when the function is not known explicitly, but where its value can be found for any given input. Give a practical example of where it might be used.

2 The following algorithm operates on the equations of 3 straight lines, each in the form \(y = m _ { i } x + c _ { i }\).

1. Run the algorithm for the straight lines \(y = 2 x + 8 , y = 2 x + 5\) and \(y = 4 x + 3\) using the table given in your answer book. The first five steps have been completed, so you should continue from Step 6. [7]
2. Describe what the algorithm achieves.