OCR D1 (Decision Mathematics 1) 2015 June

1 The following list is to be sorted into increasing order, from smallest to largest. $$\begin{array} { l l l l l l } 15 & 7 & 9 & 26 & 10 & 4 \end{array}$$ Bubble sort is to be used, starting at the left-hand end of the list, so that after the completion of the first pass the largest value will be at the right-hand end of the list.

1. Write down the list that results at the end of the first pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
2. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 4 & 10 & 15 & 26 \end{array}$$ Write down the list that results at the end of the fourth pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
3. How many comparisons are needed in total to sort the list using bubble sort? Shuttle sort is then used to sort the original list, into increasing order, starting at the left-hand end of the list.
4. Write down the list that results at the end of the first pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
5. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 15 & 26 & 10 & 4 \end{array}$$ Write down the list that results at the end of the fourth pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
6. How many comparisons and how many swaps are made in the fifth pass? In sorting the original list, both methods use a total of 9 swaps.
7. Which of the two methods is the more efficient at sorting this list? Support your answer with a reason.

2

1. A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8
   G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
2. Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
3. By considering the minimum spanning tree for the reduced network formed when vertex \(A\) and all arcs joined to \(A\) are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.

   	A	\(B\)	C	D	E	\(F\)	G	\(H\)
   A	-	10	-	9	10	-	-	-
   B	10	-	8	5	-	-	-	-
   C	-	8	-	9	-	10	-	-
   D	9	5	9	-	6	7	8	-
   E	10	-	-	6	-	一	9	7
   F	-	-	10	7	-	-	5	-
   G	-	-	-	8	9	5	-	8
   H	-	-	-	-	7	-	8	-

4. Apply the nearest neighbour method, starting at \(A\), to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-05_846_833_365_614} The vertices of the feasible region are \(A ( 3.5,2 ) , B ( 1.5,3 ) , C ( 0.5,1.5 ) , D ( 1,0.5 )\).
The objective is to maximise \(P = x + 3 y\).

1. Find the coordinates of the optimum vertex and the corresponding value of \(P\).
2. Find the optimum point if \(x\) and \(y\) must both have integer values. The objective is changed to maximise \(P = x + k y\).
3. If \(k\) is positive, explain why the optimum point cannot be at \(C\) or \(D\).
4. If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the optimum point.

4 A farmer has 40 acres of land that can be used for growing wheat, potatoes and soya beans. The farmer can expect a profit of \(\pounds 80\) for each acre of wheat, \(\pounds 31\) for each acre of potatoes and \(\pounds 100\) for each acre of soya beans. Land that is left unplanted incurs no cost and generates no profit. The farmer wants to choose how much land to use for growing each crop to maximise the profit. It takes 4 hours to plant each acre of wheat, 2 hours to plant each acre of potatoes and 1 hour to plant each acre of soya beans. There are 60 hours available in total for planting. At most 25 acres can be used for wheat and at most 10 acres can be used for soya beans.
Let \(x\) denote the number of acres used for wheat, \(y\) denote the number of acres used for potatoes and \(z\) denote the number of acres used for soya beans.

1. Express the profit, \(\pounds P\), as a function of \(x , y\) and \(z\).
2. Explain why the constraint \(4 x + 2 y + z \leqslant 60\) is needed. Write down three more constraints on the values of \(x , y\) and \(z\), other than that they must be non-negative.
3. Set up an initial Simplex tableau to represent the farmer's problem. Perform one iteration of the Simplex algorithm, choosing a pivot from the column with the most negative value in the objective row. Show how each row that has changed was calculated. Julie uses the Simplex algorithm to solve the farmer's problem. Her final tableau is given below. The order of the rows and the use of the slack variables in Julie's tableau may be different from yours.

   P	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	0	9	0	20	0	80	0	2000
   0	1	0.5	0	0.25	0	-0.25	0	12.5
   0	0	-0.5	0	-0.25	1	0.25	0	12.5
   0	0	0	1	0	0	1	0	10
   0	0	0.5	0	-0.25	0	-0.75	1	17.5

4. Write down the values of \(x , y\) and \(z\) from Julie's final tableau. Hence advise the farmer on how many acres to use for each crop and how much land should be left unplanted.

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
2. Write down the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(G\). Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at \(A\).
3. Explain why Sheng-Li will need to repeat some streets.
4. Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at \(A\), to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from \(A\), with Sheng-Li delivering to one side of \(A B\) and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel \(A - B - C - E\). At this point Sheng-Li is called back to \(A\). He travels along \(E - C - A\), delivering leaflets on one side of \(C A\). Nadia completes the leaflet delivery on her own.
5. Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
   [0pt] [4]

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

• Two of the green faces are opposite one another.
• The other green face is opposite the yellow face.
• The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h] \end{figure} Fig. 1

1. Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
2. How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
   \end{figure} Fig. 3
3. Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled \(1,2,3\) or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
   From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled \(1,2,3\) and 4 and four nodes each having order two.
5. Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
7. Using your answer to part (vi), show the two possible colourings of the back of the tower.