OCR D1 (Decision Mathematics 1) 2009 January

1 The flow chart shows an algorithm for which the input is a three-digit positive integer.
\includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-2_1294_1493_356_328}

1. Trace through the algorithm using the input \(A = 614\) to show that the output is 297 . Write down the values of \(A , B , C\) and \(D\) in each pass through the algorithm.
2. What is the output when \(A = 616\) ?
3. Explain why the counter \(C\) is needed.

2

1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.

3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.

4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$

1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
2. State the number of comparisons and the number of swaps that were made in the first pass.
3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
   [0pt]
6. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4
   4 x + 6 y + 5 z \leqslant 24
   x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
7. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
8. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
9. Write down an expression for the objective function to be maximised. State any assumption that you have made.
10. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
11. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.