AQA D1 (Decision Mathematics 1) 2013 June

1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.

1. Represent this information on a bipartite graph.
2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.

2

1. Use the quicksort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. You must indicate the pivot(s) being used on each pass. $$2 , \quad 12 , \quad 17 , \quad 18 , \quad 5 , \quad 13$$
2. For the first pass, write down the number of comparisons.

3 The following network shows the lengths, in miles, of roads connecting ten villages, \(A , B , C , \ldots , J\).
\includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}

1. 1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Find the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Prim's algorithm from different starting points produces the same minimum spanning tree. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
   1. \(A\);
   2. \(F\).

4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.

1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.

5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, \(A , B , \ldots , L\). On a particular day, there are three police cars in the area at \(A , E\) and \(J\). There is an emergency at \(G\) and all three police cars drive to \(G\).

1. 1. Use Dijkstra's algorithm on the network, starting from \(\boldsymbol { G }\), to find the minimum driving time for each of the police cars to arrive at \(G\).
   2. For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
2. Each day, a police car has to drive along each road at least once, starting and finishing at \(A\). For an optimal Chinese postman route:
   1. find the driving time for the police car;
   2. state the number of times that the vertex \(B\) would appear.
      \includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}

6 A student is tracing the following algorithm. The function INT gives the integer part of any number, eg \(\operatorname { INT } ( 2.3 ) = 2\) and \(\operatorname { INT } ( 6.7 ) = 6\). Line 10 Input \(A , B\)
Line \(20 \quad\) Let \(C = \operatorname { INT } ( A \div B )\)
Line 30 Let \(D = B \times C\)
Line \(40 \quad\) Let \(E = A - D\)
Line 50 If \(E = 0\) then go to Line 90
Line 60 Let \(A = B\)
Line \(70 \quad\) Let \(B = E\)
Line 80 Go to Line 20
Line 90 Print \(B\)
Line 100 Stop

1. Trace the algorithm when the input values are:
   1. \(A = 36\) and \(B = 16\);
   2. \(A = 11\) and \(B = 7\).
2. State the purpose of the algorithm.

7 Paul is a florist. Every day, he makes three types of floral bouquet: gold, silver and bronze. Each gold bouquet has 6 roses, 6 carnations and 6 dahlias.
Each silver bouquet has 4 roses, 6 carnations and 4 dahlias.
Each bronze bouquet has 3 roses, 4 carnations and 4 dahlias.
Each day, Paul must use at least 420 roses and at least 480 carnations, but he can use at most 720 dahlias. Each day, Paul makes \(x\) gold bouquets, \(y\) silver bouquets and \(z\) bronze bouquets.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x , y\) and \(z\) that model the above constraints.
2. On a particular day, Paul makes the same number of silver bouquets as bronze bouquets.
   1. Show that \(x\) and \(y\) must satisfy the following inequalities. $$\begin{aligned} & 6 x + 7 y \geqslant 420
      & 3 x + 5 y \geqslant 240
      & 3 x + 4 y \leqslant 360 \end{aligned}$$
   2. Paul makes a profit of \(\pounds 4\) on each gold bouquet sold, a profit of \(\pounds 2.50\) on each silver bouquet sold and a profit of \(\pounds 2.50\) on each bronze bouquet sold. Each day, Paul sells all the bouquets he makes. Paul wishes to maximise his daily profit, \(\pounds P\). Draw a suitable diagram, on the grid opposite, to enable this problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (6 marks)
   3. Use your diagram to find Paul's maximum daily profit and the number of each type of bouquet he must make to achieve this maximum.
3. On another day, Paul again makes the same number of silver bouquets as bronze bouquets, but he makes a profit of \(\pounds 2\) on each gold bouquet sold, a profit of \(\pounds 6\) on each silver bouquet sold and a profit of \(\pounds 6\) on each bronze bouquet sold. Find Paul's maximum daily profit, and the number of each type of bouquet he must make to achieve this maximum.
   (3 marks) Turn over -