Edexcel D1 (Decision Mathematics 1) 2010 January

1. \begin{figure}[h] \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.

1. Show this initial matching on Diagram 1 in the answer book.
   (1)
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
   (5)

2. Prim's algorithm finds a minimum spanning tree for a connected graph.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]

   	Cambridge	London	Norwich	Oxford	Portsmouth	Salisbury	York
   Cambridge (C)	-	60	62	81	132	139	156
   London (L)	60	-	116	56	74	88	211
   Norwich (N)	62	116	-	144	204	201	181
   Oxford (O)	81	56	144	-	84	63	184
   Portsmouth (P)	132	74	204	84	-	43	269
   Salisbury (S)	139	88	201	63	43	-	248
   York (Y)	156	211	181	184	269	248	-

   \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{table} Figure 2 shows the distances by road, in miles, between seven cities.
3. 1. Use Prim's algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.
   2. Draw your tree using the vertices given in Diagram 2 in the answer book.
      (5)

3. \begin{figure}[h] \end{figure} [The total weight of the network is 167]
Figure 3 represents a network of paths. The number on each arc gives the time, in minutes, to travel along that path.

1. Use Dijkstra's algorithm to find the quickest route from A to H. State your quickest route and the time taken.
   (5) Kevin must walk along each path at least once and return to his starting point.
2. Use an appropriate algorithm to find the time of Kevin's quickest possible route, starting and finishing at A. You should make your method and working clear.

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are $$0.6,4.0,2.5,3.2,0.5,2.6,0.4,0.3,4.0 \text { and } 1.0$$ Guttering is sold in 4 m lengths.

1. Carry out a quick sort to produce a list of the lengths needed in descending order. You should show the result of each pass and identify your pivots clearly.
2. Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the total number of 4 m lengths needed.
3. Does the answer to part (b) use the minimum number of 4 m lengths? You must justify your answer.

5. \begin{figure}[h] \end{figure} An algorithm is described by the flowchart shown in Figure 4.

1. Given that \(\mathrm { S } = 25000\), complete the table in the answer book to show the results obtained at each step when the algorithm is applied. This algorithm is designed to model a possible system of income tax, T, on an annual salary, £S.
2. Write down the amount of income tax paid by a person with an annual salary of \(\pounds 25000\).
3. Find the maximum annual salary of a person who pays no tax.

6. \begin{figure}[h] \end{figure} Figure 5 is the activity network relating to a building project. The number in brackets on each arc gives the time taken, in days, to complete the activity.

1. Explain the significance of the dotted line from event (2) to event (3).
2. Complete the precedence table in the answer booklet.
3. Calculate the early time and the late time for each event, showing them on the diagram in the answer booklet.
4. Determine the critical activities and the length of the critical path.
5. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project.

7. You are in charge of buying new cupboards for a school laboratory. The cupboards are available in two different sizes, standard and large.
The maximum budget available is \(\pounds 1800\). Standard cupboards cost \(\pounds 150\) and large cupboards cost \(\pounds 300\).
Let \(x\) be the number of standard cupboards and \(y\) be the number of large cupboards.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
   (2) The cupboards will be fitted along a wall 9 m long. Standard cupboards are 90 cm long and large cupboards are 120 cm long.
2. Show that this constraint can be modelled by $$3 x + 4 y \leqslant 30$$ You must make your reasoning clear. Given also that \(y \geqslant 2\),
3. explain what this constraint means in the context of the question. The capacity of a large cupboard is \(40 \%\) greater than the capacity of a standard cupboard. You wish to maximise the total capacity.
4. Show that your objective can be expressed as $$\text { maximise } 5 x + 7 y$$
5. Represent your inequalities graphically, on the axes in your answer booklet, indicating clearly the feasible region, R.
6. Find the number of standard cupboards and large cupboards that need to be purchased. Make your method clear.