Edexcel D1 (Decision Mathematics 1) 2009 January

1. Max Lauren John Hannah Kieran Tara Richard Imogen

1. Use a quick sort to produce a list of these names in ascending alphabetical order. You must make your pivots clear.
2. Use the binary search algorithm on your list from part (a) to try to locate the name 'Hugo'.

2. The table shows the distances, in metres, between six vertices, \(\mathbf { A } , \mathbf { B } , \mathbf { C } , \mathbf { D } , \mathbf { E }\) and \(\mathbf { F }\), in a network.

1. Draw the weighted network using the vertices given in Diagram 1 in the answer booklet.
2. Use Kruskal's algorithm to find a minimum spanning tree. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
3. Draw your tree on Diagram 2 in the answer booklet and find its total weight.

3. (a) Draw the activity network described in this precedence table, using activity on arc and exactly two dummies.
(5) (b) Explain why each of the two dummies is necessary.

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching.
2. Explain why it is not possible to find a complete matching. D now has task 2 added to their possible allocation.
3. Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching.
   (3)

5. \begin{figure}[h] \end{figure} (The total weight of the network in Figure 3 is 543 km .)
Figure 3 models a network of railway tracks that have to be inspected. The number on each arc is the length, in km , of that section of railway track.
Each track must be traversed at least once and the length of the inspection route must be minimised.
The inspection route must start and finish at the same vertex.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. It is now permitted to start and finish the inspection at two distinct vertices.
2. State which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.

6. \begin{figure}[h] \end{figure} Figure 4 shows a network of roads through eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc is the length of that road in km .

1. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
   (5) There is a fair in village C and you cannot drive through the village. A shortest route from A to H which avoids C needs to be found.
2. State this new minimal route and its length.
   (2)

7. A linear programming problem is modelled by the following constraints $$\begin{aligned} 8 x + 3 y & \leqslant 480
8 x + 7 y & \geqslant 560
y & \geqslant 4 x
x , y & \geqslant 0 \end{aligned}$$

1. Use the grid provided in your answer book to represent these inequalities graphically. Hence determine the feasible region and label it R . The objective function, \(F\), is given by $$F = 3 x + y$$
2. Making your method clear, determine
   1. the minimum value of the function \(F\) and the coordinates of the optimal point,
   2. the maximum value of the function \(F\) and the coordinates of the optimal point.

8. \begin{figure}[h] \end{figure} The network in Figure 5 shows the activities involved in a process. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, taken to complete the activity.

1. Calculate the early time and the late time for each event, showing them on the diagram in the answer book.
2. Determine the critical activities and the length of the critical path.
3. Calculate the total float on activities F and G . You must make the numbers you used in your calculation clear.
4. On the grid in the answer book, draw a cascade (Gantt) chart for the process. Given that each task requires just one worker,
5. use your cascade chart to determine the minimum number of workers required to complete the process in the minimum time. Explain your reasoning clearly.