7.03a Algorithm definition: input, output, deterministic, finite

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.

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 King Elyias has been presented with eight flagons of fine wine. Intelligence reports indicate that at least one of the eight flagons has been poisoned. King Elyias will have the wine tasted by the royal wine tasters to establish which flagons are poisoned. Samples for testing are made by using wine from one or more flagons. If a royal wine taster tastes a sample of wine which includes wine from a poisoned flagon, the taster will die. The king has to make a very generous payment for each sample tasted. To minimise payments, the royal mathematicians have devised the following scheme:
Test a sample made by mixing wine from flagons \(1,2,3\) and 4.
If the taster dies, then test a sample made by mixing wine from flagons \(5,6,7\) and 8 .
If the taster lives, then there is no poison in flagons \(1,2,3\) or 4 . So there is poison in at least one of flagons 5, 6, 7 and 8, and there is no need to test a sample made by mixing wine from all four of them. If the sample from flagons \(1,2,3\) and 4 contains poison, then test a fresh sample made by mixing wine from flagons 1 and 2, and proceed similarly, testing a sample from flagons 3 and 4 only if the taster of the sample from flagons 1 and 2 dies. Continue, testing new samples made from wine drawn from half of the flagons corresponding to a poisoned sample, and testing only when necessary.

1. Record what happens using the mathematicians' scheme when flagon number 7 is poisoned, and no others.
2. Record what happens using the mathematicians' scheme when two flagons, numbers 3 and 7, are poisoned.

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.

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.

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.

2 The algorithm gives a method for drawing two straight lines, if certain conditions are met. Start with the equations of the two straight lines
Line 1 is \(a x + b y = c , \quad a , b , c > 0\) Line 2 is \(d x + e y = f , \quad d , e , f > 0\) Let \(X =\) minimum of \(\frac { c } { a }\) and \(\frac { f } { d }\) Let \(Y =\) minimum of \(\frac { c } { b }\) and \(\frac { f } { e }\) If \(X = \frac { c } { a }\) then \(X ^ { * } = \frac { c - b Y } { a }\) and \(Y ^ { * } = \frac { f - d X } { e }\) If \(X = \frac { f } { d }\) then \(X ^ { * } = \frac { f - e Y } { d }\) and \(Y ^ { * } = \frac { c - a X } { b }\) Draw an \(x\)-axis labelled from 0 to \(X\), and a \(y\)-axis labelled from 0 to \(Y\) Join ( \(0 , Y\) ) to ( \(X , Y ^ { * }\) ) with a straight line
Join ( \(X ^ { * } , Y\) ) to ( \(X , 0\) ) with a straight line

1. Apply the algorithm with \(a = 1 , b = 5 , c = 25 , d = 10 , e = 2 , f = 85\).
2. Why might this algorithm be useful in an LP question?

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.

5

1. The following instructions operate on positive integers greater than 4.
   Step 10 Choose any positive integer greater than 4, and call it \(n\).
   Step 15 Write down \(n\).
   Step 20 If \(n\) is even then let \(n = \frac { n } { 2 }\) and write down the result.
   Step 30 If \(n\) is odd then let \(n = 3 n + 1\) and write down the result.
   Step 40 Go to Step 20.
   1. Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
   2. Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
   3. Add an instruction to stop the process when \(n\) becomes 1 .
   4. It is not known if, when modified to stop cycling through \(4,2,1\), the instructions form an algorithm. What would need to be known for it to be an algorithm?
2. Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .

   Item	A	B	C	D	E	F
   Weight \(( \mathrm { kg } )\)	2	1	6	3	3	5

   The first-fit algorithm is as follows. \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
   1. Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
   2. Place the items in increasing order of weight, and then apply the first-fit algorithm.
   3. Place the items in decreasing order of weight, and then apply the first-fit algorithm. An optimal solution is one which uses the least number of boxes.
   4. Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
   5. First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?

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.

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

1. Run the algorithm.
2. 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).
3. Modify Tania's algorithm to answer the birthday problem. (Do not attempt to run your modified algorithm.)
4. Why have 29 February birthdays been excluded?

2. This question should be answered on the sheet provided. \begin{figure}[h] \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.

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.
2. Explain what the algorithm achieves for any set of data \(x _ { 1 }\) to \(x _ { n }\).

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.

\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}

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] \end{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.
2. Explain what the algorithm achieves.
3. 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)
4. Find the set of positive initial values of \(a\) for which the algorithm will work.
   (2 marks)

4 The diagram represents a map of an army truck-driving course that includes several bridges. The start and a 'safe point' just after each bridge have been given (stage; state) labels. The number below each bridge shows its weight limit, in tonnes. \includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-4_698_1413_438_365} An army cadet needs to drive a truck through the course from start to finish, crossing exactly three bridges.

1. Draw a network, using the (stage; state) labels given, to represent the routes through the course. The weights on the arcs should show the weight limits for the bridges. The cadet wants to find out the weight of the heaviest truck she can use.
2. Which network problem does she need to solve?
3. Set up a dynamic programming tabulation to solve the cadet's problem. Write down the weight of the heaviest truck she can use and write down the (stage; state) labels for the route she should take.