AQA D1 (Decision Mathematics 1) 2015 June

1 A quiz team must answer questions from six different topics, numbered 1 to 6. The team has six players, \(A , B , C , D , E\) and \(F\). Each player can only answer questions on one of the topics. The players list their preferred topics. The bipartite graph shows their choices.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-02_711_499_781_760} Initially, \(A\) is allocated topic 2, \(B\) is allocated topic \(3 , C\) is allocated topic 1 and \(F\) is allocated topic 4. By using an alternating path algorithm from this initial matching, find a complete matching.
[0pt] [5 marks]

2 The network below shows 8 towns, \(A , B , \ldots , H\). The number on each edge shows the length of the road, in miles, between towns. During the winter, the council treats some of the roads with salt so that each town can be safely reached on treated roads from any other town. It costs \(\pounds 30\) to treat a mile of road.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-04_876_1611_497_210}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Draw your minimum spanning tree.
   3. Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
2. On one occasion, the road from \(C\) to \(E\) is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.
   [0pt] [2 marks]

3 Four students, \(A , B , C\) and \(D\), are using different algorithms to sort 16 numbers into ascending order.

1. Student \(A\) uses the quicksort algorithm. State the number of comparisons on the first pass.
2. Student \(B\) uses the Shell sort algorithm. State the number of comparisons on the first pass.
3. Student \(C\) uses the shuttle sort algorithm. State the minimum number of comparisons on the final pass.
4. Student \(D\) uses the bubble sort algorithm. Find the maximum total number of comparisons.

4 The network opposite shows roads connecting 10 villages, \(A , B , \ldots , J\). The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.

1. A commuter wishes to drive from village \(A\) to the railway station at \(J\).
   1. Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from \(A\) to \(J\).
   2. State the corresponding route.
2. A taxi driver is in village \(D\) at 10.30 am when she receives a radio call asking her to pick up a passenger at village \(A\) and take him to the station at \(J\). Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?
   [0pt] [2 marks]
   \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}

5 The network shows the paths mown through a wildflower meadow so that visitors can use these paths to enjoy the flowers. The lengths of the paths are shown in metres.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-10_1097_1603_413_214} The total length of all the paths is 1400 m .
The mower is kept in a shed at \(A\). The groundskeeper must mow all the paths and return the mower to its shed.

1. Find the length of an optimal Chinese postman route starting and finishing at \(A\).
2. State the number of times that the mower, following the optimal route, will pass through:
   1. \(C\);
   2. \(D\).

6 The network shows the roads linking a warehouse at \(A\) and five shops, \(B , C , D , E\) and \(F\). The numbers on the edges show the lengths, in miles, of the roads. A delivery van leaves the warehouse, delivers to each of the shops and returns to the warehouse.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-12_1241_1239_484_402}

1. Complete the table, on the page opposite, showing the shortest distances between the vertices.
2. 1. Find the total distance travelled if the van follows the cycle \(A E F B C D A\).
   2. Explain why your answer to part (b)(i) provides an upper bound for the minimum journey length.
3. Use the nearest neighbour algorithm starting from \(D\) to find a second upper bound.
4. By deleting \(A\), find a lower bound for the minimum journey length.
5. Given that the minimum journey length is \(T\), write down the best inequality for \(T\) that can be obtained from your answers to parts (b), (c) and (d).
   [0pt] [1 mark] \section*{Answer space for question 6} REFERENCE

6. 	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)	\(\boldsymbol { F }\)
   \(\boldsymbol { A }\)	-	7
   \(\boldsymbol { B }\)	7	-	5
   \(\boldsymbol { C }\)		5	-	4
   \(\boldsymbol { D }\)			4	-	6
   \(\boldsymbol { E }\)				6	-	10
   \(\boldsymbol { F }\)					10	-

7

1. A simple connected graph has 4 edges and \(m\) vertices. State the possible values of \(m\).
2. A simple connected graph has \(n\) edges and 4 vertices. State the possible values of \(n\).
3. A simple connected graph, \(G\), has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph \(G\).
   [0pt] [2 marks]

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.

9 A company producing chicken food makes three products, Basic, Premium and Supreme, from wheat, maize and barley. A tonne \(( 1000 \mathrm {~kg} )\) of Basic uses 400 kg of wheat, 200 kg of maize and 400 kg of barley.
A tonne of Premium uses 400 kg of wheat, 500 kg of maize and 100 kg of barley.
A tonne of Supreme uses 600 kg of wheat, 200 kg of maize and 200 kg of barley.
The company has 130 tonnes of wheat, 70 tonnes of maize and 72 tonnes of barley available. The company must make at least 75 tonnes of Supreme.
The company makes \(\pounds 50\) profit per tonne of Basic, \(\pounds 100\) per tonne of Premium and \(\pounds 150\) per tonne of Supreme. They plan to make \(x\) tonnes of Basic, \(y\) tonnes of Premium and \(z\) tonnes of Supreme.

1. Write down four inequalities representing the constraints (in addition to \(x , y \geqslant 0\) ).
   [0pt] [4 marks]
2. The company want exactly half the production to be Supreme. Show that the constraints in part (a) become $$\begin{aligned} x + y & \leqslant 130
   4 x + 7 y & \leqslant 700
   2 x + y & \leqslant 240
   x + y & \geqslant 75
   x & \geqslant 0
   y & \geqslant 0 \end{aligned}$$
3. On the grid opposite, illustrate all the constraints and label the feasible region.
4. Write an expression for \(P\), the profit for the whole production, in terms of \(x\) and \(y\) only.
   [0pt] [2 marks]
5. 1. By drawing an objective line on your graph, or otherwise, find the values of \(x\) and \(y\) which give the maximum profit.
      [0pt] [2 marks]
   2. State the maximum profit and the amount of each product that must be made.
      [0pt] [2 marks] \section*{Answer space for question 9}
      \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-21_1349_1728_310_148}
      QUESTION
      PART
      REFERENCE
      \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-24_2488_1728_219_141}