AQA D1 (Decision Mathematics 1) 2011 June

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.

1. Represent this information in a bipartite graph.
2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.

2 Five different integers are to be sorted into ascending order.

1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
3. Use your answers from parts (a) and (b) to write down the value of \(x\).

3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table. One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.

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 table.
   2. Draw your minimum spanning tree.
   3. Find the minimum total cost.
2. Person \(H\) leaves the group. Find the new minimum total cost.

4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway. Carol, the headteacher, wishes to walk from her office ( \(O\) ) to the Drama department (D) .

1. 1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(O\) to \(D\).
   2. Write down the corresponding route.
2. On another occasion, Carol needs to go from her office to the Business Studies department \(( B )\).
   1. Write down her minimum walking time.
   2. Write down the route corresponding to this minimum time.
      \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}

5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point \(A\), and must drive along all the roads at least once before returning to the depot.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}

1. Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at \(A\).
2. Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point \(A\), and drives along all the roads at least once before finishing at his home, located at point \(C\). Find the length of an optimal route for Zac.
3. Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
   1. Find the length of an optimal route for Liz.
   2. State the points from which Liz could start in order to achieve this optimal route.
      \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}

6 A student is tracing the following algorithm.
Line 10 Let \(A = 6\)
Line \(20 \quad\) Let \(B = 7\)
Line 30 Input \(C\)
Line 40 Let \(D = ( A + B ) / 2\)
Line \(50 \quad\) Let \(E = C - D ^ { 3 }\)
Line 60 If \(E ^ { 2 } < 1\) then go to Line 120
Line 70 If \(E > 0\) then go to Line 100
Line 80 Let \(B = D\)
Line 90 Go to Line 40
Line \(100 \quad\) Let \(A = D\)
Line 110 Go to Line 40
Line 120 Stop

1. Trace the algorithm in the case where the input value is \(C = 300\).
2. The algorithm is intended to find the approximate cube root of any input number. State two reasons why the algorithm is unsatisfactory in its present form.
   (3 marks)

7 A builder needs some screws, nails and plugs. At the local store, there are packs containing a mixture of the three items. A DIY pack contains 200 nails, 200 screws and 100 plugs.
A trade pack contains 1000 nails, 1500 screws and 2500 plugs.
A DIY pack costs \(\pounds 2.50\) and a trade pack costs \(\pounds 15\).
The builder needs at least 5000 nails, 6000 screws and 4000 plugs.
The builder buys \(x\) DIY packs and \(y\) trade packs and wishes to keep his total cost to a minimum.

1. Formulate the builder's situation as a linear programming problem.
2. 1. On the grid opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of an objective line.
   2. Use your diagram to find the number of each type of pack that the builder should buy in order to minimise his cost.
   3. Find the builder's minimum cost.

8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}

1. 1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
   2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
2. 1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
   2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
3. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 1}

   	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)
   \(P\)	-	25
   \(Q\)	25	-	20	21	23	11
   \(\boldsymbol { R }\)		20	-
   \(\boldsymbol { S }\)		21		-
   \(T\)		23			-	12
   \(\boldsymbol { U }\)		11			12	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}