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

5 Henry is doing a sponsored cycle ride for charity. He needs to finish at noon on Sunday. He can ride up to 50 miles each day, except Sunday when he can ride at most 20 miles if he is to finish on time. The total length of the ride is 95 miles so Henry has allowed 3 days for the ride. Henry will start his ride at \(A\) and travel through \(B , C , D\) and \(E\), in that order, and finish on Sunday at \(F\). He will stay overnight on Friday and Saturday at two of the places \(B , C , D\) and \(E\). The distances between the places along the route are: $$A - B = 30 \text { miles } , \quad B - C = 15 \text { miles } , \quad C - D = 35 \text { miles } , \quad D - E = 12 \text { miles } , \quad E - F = 3 \text { miles. }$$ To reach \(F\) on Sunday he must have reached at least \(D\) by Saturday night (since the distance from \(D\) to \(F\) is less than 20 miles but \(C\) to \(F\) is more than 20 miles.) Henry wants to use dynamic programming to minimise the maximum distance that he cycles on any day.
The stages will be the days. The places where Henry stays overnight will be the states. Henry starts on Friday morning at \(A\) which has the (stage; state) label ( \(0 ; 0\) ). On Friday night he can either stay at \(B ( 1 ; 0 )\) or at \(C ( 1 ; 1 )\). Depending on where he stays on Friday night, he can spend Saturday night at \(D ( 2 ; 0 )\) or \(E ( 2 ; 1 )\). On Sunday he arrives at \(F ( 3 ; 0 )\).
[0pt]

1. Use this information and the table below to draw a network, labelled with stages and states, to show the possible transitions between states. The arc weights should be the distances between the states. [2] Henry uses dynamic programming, working backwards from stage 3, to find where he should stay overnight to give the route for which the maximum on any day is a minimum. His tabulation is shown below.

   Stage	State	Action	Working	Suboptimal minimax
   \multirow[t]{2}{*}{2}	0	0	15	15
   	1	0	3	3
   \multirow{3}{*}{1}	0	0	\(\max ( 50,15 )\)	50
   	\multirow[t]{2}{*}{1}	0	\(\max ( 35,15 )\)	\multirow[t]{2}{*}{35}
   		1	\(\max ( 47,3 )\)
   \multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	\(\max ( 30,50 )\)	\multirow[b]{2}{*}{45}
   		1	max(45, 35)

2. (a) In the last row of the table, the action value is 1 . Explain what this tells you.
3. (b) In the last row of the table, the working column is \(\max ( 45,35 )\). Explain where each of the values 45 and 35 comes from and how they relate to the (stage; state) values for this row and for a row from the next stage.
4. Use the table to deduce where Henry should make his overnight stops to minimise the maximum distance that he cycles on any day. Explain how you obtained this solution from the table. Henry is so pleased with his ride that he decides to do a longer ride. Again he will cycle up to 50 miles each day, except the last day when he will cycle at most 20 miles. He wants to complete the ride in five days, and he wants to minimise the maximum distance that he rides on any one day. He will start at \(A\) and travel through \(B , C , D , E , F , G , H , I , J\) and \(K\), in that order, and finish at \(L\).
   He will stay overnight on Wednesday, Thursday, Friday and Saturday at four of \(B , C , D , E , F , G , H , I , J\) and \(K\). The distances between the places along the route are:

   \(A - B = 30\) miles,	\(B - C = 15\) miles,	\(C - D = 35\) miles,	\(D - E = 12\) miles,
   \(E - F = 3\) miles,	\(F - G = 30\) miles,	\(G - H = 10\) miles,	\(H - I = 25\) miles,
   \(I - J = 10\) miles,	\(J - K = 10\) miles,	\(K - L = 5\) miles.

5. (a) Which is the furthest place from \(L\) that Henry must reach by Saturday night if he is to finish on time?
   (b) Work backwards to deduce the furthest place from \(L\) that Henry must reach by Friday night, Thursday night and Wednesday night.
6. Find out where Henry could stay each night, and hence define appropriate states for each of stages 1, 2, 3 and 4 . (Note that not every place need correspond to a (stage; state) label.)
7. Set up a dynamic programming tabulation, working backwards from stage 5, to minimise the maximum distance that Henry must ride on any one day. Where should he make his overnight stops?

3

1. 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.
2. 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.
3. 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.
4. Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

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.

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 .

4 An algorithm must have an input, an output, be deterministic and finite.

1. Why is a counter sometimes used in an algorithm? A computer takes 0.2 seconds to sort a list of 500 numbers.
2. How long would you expect the computer to take to sort a list of 5000 numbers? Simon says that he can sort a list of numbers 'just by looking at them'.
3. Explain to Simon why sorting algorithms are needed.
4. Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position. \(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\) For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
5. Explain why quick sort is typically quicker than bubble sort and shuttle sort. When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort. An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
6. Without writing out all the passes, determine

1. Use the binary search algorithm to try to locate the word "Parallelogram" in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.

Arc Centre Chord Circle Circumference Diameter Radius Sector Segment Tangent

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.

1. Explain why a binary search cannot be performed with the list in its present form.
2. 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.
3. 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.
4. Find the maximum number of iterations needed. You should justify your answer.

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.

5. \begin{figure}[h] \end{figure} An algorithm is described by the flowchart shown in Figure 4.

1. 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.
2. Write down the amount of income tax paid by a person with an annual salary of \(\pounds 25000\).
3. Find the maximum annual salary of a person who pays no tax.

1. \begin{figure}[h] \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\),

1. 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\),
2. describe how this would affect the output.
3. State the value of E which cannot be used when using this flow chart.

2.

1. 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)
2. Find the maximum number of iterations needed to locate any particular letter of the alphabet. Justify your answer.
   

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}$$ An incomplete trace through the algorithm is shown below. The next box to be used is the box 'Let \(i = t\) '.

1. Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
2. 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.
3. 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.
4. 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\).
5. 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\).
6. 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\).

3 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows eight vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown. \includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-03_595_1234_1866_386}

1. Use dynamic programming to find the minimum cost of travelling from \(A\) to \(H\). You may use Figure 3 for your working.
2. State the minimum cost and the possible routes corresponding to this minimum cost.

4. A rally consisting of four stages is being planned. The first stage will begin at \(A\) and the last stage will end at \(L\). Various routes are being considered, with the end of one stage being the start of the next. The organisers want the total length of the route chosen to be as small as possible. The table below shows the length, in miles, of each of the possible stages. Use dynamic programming to find the route which satisfies the wish of the organisers.

1. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.

\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]

Use the binary search algorithm to try to locate the name NIGEL in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage. 1. Bhavika 2. Clive 3. Elizabeth 4. John 5. Mark 6. Nicky 7. Preety 8. Steve 9. Trevor 10. Verity (Total 4 marks)

The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper \((R)\), Palmer \((P)\), Boase \((B)\), Young \((Y)\), Thomas \((T)\), Kenney \((K)\), Morris \((M)\), Halliwell \((H)\), Wicker \((W)\), Garesalingam \((G)\).

1. Use the quick sort algorithm to sort the names above into alphabetical order. [5]
2. Use the binary search algorithm to locate the name Kenney. [4]

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

1. Given that \(x = 54\) and \(y = 63\), complete the table in the answer book to show the results obtained at each step when the algorithm is applied. [7]
2. State what the algorithm achieves. [2]

(Total 9 marks)

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]

A student is testing a numerical method for finding an approximation for \(\pi\). The algorithm that the student is using is as follows. Line 10 \quad Input \(A\), \(B\), \(C\), \(D\), \(E\) Line 20 \quad Let \(A = A + 2\) Line 30 \quad Let \(B = -B\) Line 40 \quad Let \(C = \frac{B}{A}\) Line 50 \quad Let \(D = D + C\) Line 60 \quad Let \(E = (D - 3.14)^2\) Line 70 \quad If \(E < 0.05\) then go to Line 90 Line 80 \quad Go to Line 20 Line 90 \quad Print '\(\pi\) is approximately', \(D\) Line 100 \quad End Trace the algorithm in the case where the input values are $$A = 1, \quad B = 4, \quad C = 0, \quad D = 4, \quad E = 0$$ [6 marks]

In this question, the function INT(\(X\)) is the largest integer less than or equal to \(X\). For example, $$\text{INT}(3.6) = 3,$$ $$\text{INT}(3) = 3,$$ $$\text{INT}(-3.6) = -4.$$ Consider the following algorithm. \begin{align} \text{Step 1} \quad & \text{Input } B
\text{Step 2} \quad & \text{Input } N
\text{Step 3} \quad & \text{Calculate } F = N \div B
\text{Step 4} \quad & \text{Let } G = \text{INT}(F)
\text{Step 5} \quad & \text{Calculate } H = B \times G
\text{Step 6} \quad & \text{Calculate } C = N - H
\text{Step 7} \quad & \text{Output } C
\text{Step 8} \quad & \text{Replace } N \text{ by the value of } G
\text{Step 9} \quad & \text{If } N = 0 \text{ then stop, otherwise go back to Step 3} \end{align}

1. Apply the algorithm with the inputs \(B = 2\) and \(N = 5\). Record the values of \(F\), \(G\), \(H\), \(C\) and \(N\) each time Step 9 is reached. [5]
2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = -5\). [4]
3. Apply the algorithm with the inputs \(B = 10\) and \(N = 37\). Record the values of \(F\), \(G\), \(H\), \(C\) and \(N\) each time Step 9 is reached. What are the output values when \(B = 10\) and \(N\) is any positive integer? [4]

The function INT(\(C\)) gives the largest integer that is less than or equal to \(C\). For example: INT(4.8) = 4, INT(7) = 7, INT(0.8) = 0, INT(−0.8) = −1, INT(−2.4) = −3. Consider the following algorithm. Line 10 \quad Input \(A\) and \(B\) Line 20 \quad Calculate \(C = B \div A\) Line 30 \quad Let \(D =\) INT(\(C\)) Line 40 \quad Calculate \(E = A \times D\) Line 50 \quad Calculate \(F = B - E\) Line 60 \quad Output the value of \(F\) Line 70 \quad Replace \(B\) by the value of \(D\) Line 80 \quad If \(B = 0\) then stop, otherwise go back to line 20

1. Apply the algorithm using the inputs \(A = 10\) and \(B = 128\). Record the values of \(A\), \(B\), \(C\), \(D\), \(E\), and \(F\) every time they change. Record the output each time line 60 is reached. [4]
2. Show what happens when the input values are \(A = 10\) and \(B = -13\). [5]