Algorithm Tracing

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.

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.

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

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)

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}

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

3. \begin{figure}[h] \end{figure} An algorithm for finding the positive real root of the equation \(8 x ^ { 4 } + 5 x - 12 = 0\) is described by the flow chart shown in Figure 2.

1. Use the flow chart, with \(a = 1\), to complete the table in the answer book, stating values to at least 6 decimal places. Give the final output correct to 5 decimal places. Given that the value of the input \(a\) is a non-negative real number,
2. determine the set of values for \(a\) that cannot be used to find the positive real root of \(8 x ^ { 4 } + 5 x - 12 = 0\) using this flow chart.

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

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

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}

1. 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.
2. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
3. State what the algorithm achieves.

5. \begin{figure}[h] \end{figure} An algorithm is described by the flow chart shown in Figure 4. Given that \(x = 27\) and \(y = 5\),

1. 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.
2. 1. State, giving a reason, which number should be input as \(x\).
   2. State the output.

6. The following algorithm determines the number of comparisons made when Prim's algorithm is applied to \(\mathrm { K } _ { n }\) Step 1 Start
Step 2 Input the value of \(n\) Step 3 Let \(a = 1\) Step 4 Let \(b = n - 2\) Step 5 Let \(c = b\) Step 6 Let \(a = a + 1\) Step \(7 \quad\) Let \(b = b - 1\) Step 8 Let \(c = c + ( a \times b ) + ( a - 1 )\) Step 9 If \(b > 0\) go to Step 6
Step 10 Output \(C\) Step 11 Stop

1. For \(\mathrm { K } _ { 5 }\), complete the table in the answer book to show the results obtained at each step of the algorithm. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-11_595_703_175_680} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} The weights of the ten arcs in Figure 4 are $$\begin{array} { l l l l l l l l l l } 17 & 21 & 24 & 14 & 23 & 13 & 15 & 19 & 28 & 20 \end{array}$$
2. 1. Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
   2. Find the total number of comparisons performed during the sort.
3. Find the maximum total number of comparisons required to sort the weights of the 10 arcs of \(\mathrm { K } _ { 5 }\) into ascending order using bubble sort. It is given that the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { n }\) into ascending order using bubble sort is $$\lambda n ( n - 1 ) ( n + 1 ) ( n - 2 )$$ where \(\lambda\) is a constant.
4. Determine the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { 50 }\) into ascending order using bubble sort. You must make your method and working clear.

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

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

6 Two algorithms are shown. \section*{Algorithm 1} \section*{Algorithm 2} In the case where the input values are \(P = 400 , R = 5\) and \(T = 3\) :

1. trace Algorithm 1;
2. trace Algorithm 2.

5 A student is using the following algorithm with different values of \(A\) and \(B\).

1. 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\).
2. State the purpose of the algorithm.
3. Write down the final value of \(C\) in the case where \(A = 200\) and \(B = 300\).

6 A student is solving cubic equations that have three different positive integer solutions.
The algorithm that the student is using is as follows:
Line 10 Input \(A , B , C , D\) Line \(20 \quad\) Let \(K = 1\) Line \(30 \quad\) Let \(N = 0\) Line \(40 \quad\) Let \(X = K\) Line 50 Let \(Y = A X ^ { 3 } + B X ^ { 2 } + C X + D\) Line 60 If \(Y \neq 0\) then go to Line 100
Line \(70 \quad\) Print \(X\), "is a solution"
Line \(80 \quad\) Let \(N = N + 1\) Line 90 If \(N = 3\) then go to Line 120
Line \(100 \quad\) Let \(K = K + 1\) Line 110 Go to Line 40
Line 120 End

1. Trace the algorithm in the case where the input values are:
   1. \(A = 1 , B = - 6 , C = 11\) and \(D = - 6\);
   2. \(A = 1 , B = - 10 , C = 29\) and \(D = - 20\).
2. Explain where and why this algorithm will fail if \(A = 0\).

8 A student is tracing the following algorithm. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-18_1431_955_372_539}

1. Trace the algorithm illustrated in the flowchart for the case where the input value of \(N\) is 5 .
2. Explain the role of \(N\) in the algorithm.

\includegraphics{figure_3} Figure 3 describes an algorithm in the form of a flow chart, where \(a\) is a positive integer. List \(P\), which is referred to in the flow chart, comprises the prime numbers 2, 3, 5, 7, 11, 13, 17, ...

1. Starting with \(a = 90\), implement this algorithm. Show your working in the table in the answer book. [7]
2. Explain the significance of the output list. [2]
3. Write down the final value of \(c\) for any initial value of \(a\). [1]

\includegraphics{figure_3} An algorithm is described by the flow chart shown in Figure 3.

1. Complete the table in the answer book recording the results of each step as the algorithm is applied. (Notice that values of \(A\), \(B\), \(C\) and \(D\) are to be given to 3 decimal places, and the values of \(E\) to 1 significant figure.) [8]
2. Write down the output from the algorithm. [1]

A student is tracing the following algorithm with positive integer values of \(A\) and \(B\). The function INT gives the integer part of a number, eg INT(2.3) = 2 and INT(3.8) = 3. Line 10: Let \(X = 0\) Line 20: Input \(A\), \(B\) Line 30: If INT\((A/2) = A/2\) then go to Line 50 Line 40: Let \(X = X + B\) Line 50: If \(A = 1\) then go to Line 90 Line 60: Let \(A =\) INT\((A/2)\) Line 70: Let \(B = 2 \times B\) Line 80: Go to Line 30 Line 90: Print \(X\) Line 100: End

1. Trace the algorithm in the case where the input values are \(A = 20\) and \(B = 8\). [4]
2. State the purpose of the algorithm. [1]
3. Another student changed Line 50 to Line 50: If \(A = 1\) then go to Line 80 Explain what would happen if this algorithm were traced. [2]