7.03c Working with algorithms: trace, interpret, adapt

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

5 A student is using the algorithm below to find an approximate value of \(\sqrt { 2 }\).
Line 10 Let \(A = 1 , B = 3 , C = 0\) Line \(20 \quad\) Let \(D = 1 , E = 2 , F = 0\) Line 30 Let \(G = B / E\) Line \(40 \quad\) Let \(H = G ^ { 2 }\) Line 50 If \(( H - 2 ) ^ { 2 } < 0.0001\) then go to Line 130
Line 60 Let \(C = 2 B + A\) Line 70 Let \(A = B\) Line 80 Let \(B = C\) Line 90 Let \(F = 2 E + D\) Line 100 Let \(D = E\) Line 110 Let \(E = F\) Line 120 Go to Line 30
Line 130 Print ' \(\sqrt { 2 }\) is approximately', \(B / E\) Line 140 Stop
Trace the algorithm.

6 A student is finding a numerical approximation for the area under a curve.
The algorithm that the student is using is as follows:
Line 10 Input \(A , B , N\) Line 20 Let \(T = 0\) Line 30 Let \(D = A\) Line \(40 \quad\) Let \(H = ( B - A ) / N\) Line \(50 \quad\) Let \(E = H / 2\) Line 60 Let \(T = T + A ^ { 3 } + B ^ { 3 }\) Line \(70 \quad\) Let \(D = D + H\) Line 80 If \(D = B\) then go to line 110
Line 90 Let \(T = T + 2 D ^ { 3 }\) Line 100 Go to line 70
Line \(110 \quad\) Print 'Area \(=\), \(T \times E\) Line 120 End
Trace the algorithm in the case where the input values are:

1. \(A = 1 , B = 5 , N = 2\);
2. \(A = 1 , B = 5 , N = 4\).

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

1. Trace the algorithm, giving your answers to three decimal places where appropriate:
   1. in the case where the input value of \(X\) is 2 ;
   2. in the case where the input value of \(X\) is - 6 .
2. Another student used the same algorithm but omitted LINE 70. Describe the outcome for this student.

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.

3

1. Set up a dynamic programming tabulation to find the minimum weight route from ( \(0 ; 0\) ) to ( \(4 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-03_707_1342_1594_443} Give the route and its total weight.
2. Explain carefully how the route is obtained directly from the values in the table, without referring to the network.

1. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at his home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 1 shows the distances, in tens of miles, that he will drive each day according to the route he chooses. Use dynamic programming to find the shortest route the salesman can take and state the distance he will drive in total using this route.

2. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h] \end{figure} Figure 1 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. The owner of the plane wishes to choose a route that minimises the total distance that she flies. Use dynamic programming to find the route that she should use and state the total length of this route.

1. A company wishes to plan its production of a particular item over the coming four months based on its current orders. In each month the company can manufacture up to three of the item with the costs according to how many it makes being as follows:

There are no items in stock at the start of the period and the company wishes to meet all its orders on time and have no stock left at the end of the 4-month period. If any items are not to be supplied in the month they are made there is also a storage cost incurred of \(\pounds 400\) per item per month. The orders for each of the four months being considered are as follows: Use dynamic programming to find how many of the item the company should make in each of these four months in order to minimise the total cost for this period. \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1285_504_276} \includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1280_1361_276}

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

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

An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.

	Job 1	Job 2	Job 3	Job 4
Machine 1	14	5	8	7
Machine 2	2	12	6	5
Machine 3	7	8	3	9
Machine 4	2	4	6	10

Use the Hungarian algorithm, \emph{reducing rows first}, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time. [11]

A steel manufacturer has 3 factories \(F_1\), \(F_2\) and \(F_3\) which can produce 35, 25 and 15 kilotomnes of steel per year, respectively. Three businesses \(B_1\), \(B_2\) and \(B_3\) have annual requirements of 20, 25 and 30 kilotomnes respectively. The table below shows the cost \(C_{ij}\) in appropriate units, of transporting one kilotome of steel from factory \(F_i\) to business \(B_j\).

		Business
	\(B_1\)	\(B_2\)	\(B_3\)
\(F_1\)	10	4	11
Factory \(F_2\)	12	5	8
\(F_3\)	9	6	7

The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule. [2]
2. Calculate all of the improvement indices \(I_{ij}\) and hence show that this pattern is not optimal. [5]
3. Use the stepping-stone method to obtain an improved solution. [3]
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost. [4]

In a quiz there are four individual rounds, Art, Literature, Music and Science. A team consists of four people, Donna, Hannah, Kerwin and Thomas. Each of four rounds must be answered by a different team member. The table shows the number of points that each team member is likely to get on each individual round. Use the Hungarian algorithm, reducing rows first, to obtain an allocation which maximises the total points likely to be scored in the four rounds. You must make your method clear and show the table after each stage. [9] (Total 9 marks)

1. Describe a practical problem that could be solved using the transportation algorithm. [2]

A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from \(A\), \(B\) and \(C\) and the demand is at \(d\) and \(e\).

1. Explain why it is necessary to add a third demand \(f\). [1]
2. Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.

   	\(d\)	\(e\)	\(f\)	Supply
   \(A\)	5	3		45
   \(B\)	4	6		35
   \(C\)	2	4		40
   Demand	50	60

   [5]
3. Calculate shadow costs and improvement indices for this pattern. [5]
4. Use the stepping-stone method once to obtain an improved solution and its cost. [5]

(Total 16 marks)

A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job: \begin{array}{c|c|c|c|c} & Windows & Conservatory & Doors & Greenhouse
\hline Team A & 27 & 80 & 8 & 81
Team B & 28 & 60 & 5 & 71
Team C & 30 & 90 & 7 & 73
\end{array} Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment. [10 marks]