Algorithm tracing and properties

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.

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 .

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.

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

1. 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.
2. Explain carefully how you know that algorithm X is finite for all positive integer values of \(B\).
3. 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\).
4. 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.
5. Show that algorithm Y is more efficient than algorithm X .