7.03b Algorithm awareness: uses and practical limitations

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?

3

1. Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
2. The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
   Step 2: Remove the first item in list \(A\) and call this item \(X\).
   Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
   Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
   Step 5: If there are still items in list A, repeat Step 4.
   Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
   Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
   Step 8: Display list A.

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?

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 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( \(5 ; 0\) ) and the exit as ( \(0 ; 0\) ). He then counted the numbers of plants along paths. These numbers are shown below.

1. Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
2. Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.

2

1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, F, I
   \(M\)	6	\(E , G , J\)
   \(N\)	8	\(H\), \(K\)

   Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
3. Compare the solutions to parts (i) and (ii).

6 Set up a dynamic programming tabulation to find the maximin route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}

3 Throughout this question all clock times are in Greenwich Mean Time (GMT).
An aeroplane needs to arrive at its destination at 3pm. The places it can pass through on its route are shown in the network, together with the flying times, in hours, between them. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-4_609_1523_486_255} Use a dynamic programming tabulation, working backwards from 3pm at the destination, to find the latest time that the aeroplane could set off. If the aeroplane takes off at its latest time, which places does it pass through, and at what time does it reach each of these places?

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 .

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.

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.

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]