Edexcel D1 (Decision Mathematics 1)

2. Use the binary search algorithm to try to locate the name Hannah in the following alphabetical list. Clearly indicate how you selected your pivots and which part of the list is being rejected at each stage. \begin{displayquote} Adam
Ben
Charlie
Eleanor
Freya
Greg
Jenny
Richard
Toby \end{displayquote}

3. \begin{figure}[h] \end{figure} Figure 1 represents the distance, in metres, between eight data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G and H . The data collection points are to be linked by cables.

1. Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
   1. Kruskal's algorithm, stating in addition any arcs you reject,
   2. Prim's algorithm, starting from A .
2. State the minimum amount of cable needed.
3. Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3. The maximum matching algorithm will be used to obtain a complete matching.

1. Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.
   (3)
2. Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.

5. The precedence table shows the activities involved in planning an opening ceremony. An activity on arc network is to be drawn to model this planning process.

1. Draw the activity network using exactly two dummies.
2. Explain why each of the two dummies is necessary.

6. \begin{figure}[h] \end{figure} Figure 4 models a network of water pipes that need to be inspected. The number on each arc represents the length, in km , of that pipe. A machine is to be used to inspect for leaks. The machine must travel along each pipe at least once, starting and finishing at the same point, and the length of the inspection route is to be minimised.
[0pt] [The total weight of the network is 185 km ]

1. Starting at A, use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. Given that 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.

7. \begin{figure}[h] \end{figure} Figure 5 shows the possible bus journeys linking towns, S, A, B, C, D, E, F, G, H and T. Each arc represents a bus journey. The number on each arc represents the cost, in pounds, of travelling along that route.

1. Use Dijkstra's algorithm, on the diagram in the answer book to find the cheapest route from S to T. State your cheapest route and its cost.
   (6)
2. Explain how you determined your cheapest route from your labelled diagram. The bus journey from S to B is cancelled due to a driver's illness.
3. Find the cheapest route from S to T that does not include SB , and state its cost.

8. \begin{figure}[h] \end{figure} A company produces two products, X and Y .
Let \(x\) and \(y\) be the hourly production, in kgs, of X and Y respectively.
In addition to \(x \geqslant 0\) and \(y \geqslant 0\), two of the constraints governing the production are $$\begin{gathered} 12 x + 7 y \geqslant 840
4 x + 9 y \geqslant 720 \end{gathered}$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out. Two further constraints are $$\begin{gathered} x \geqslant 20
3 x + 2 y \leqslant 360 \end{gathered}$$

1. Add two lines and shading to Figure 6 in your answer book to represent these inequalities.
2. Hence determine and label the feasible region, R. The company makes a profit of 70 p and 20 p per kilogram of X and Y respectively.
3. Write down an expression, in terms of \(x\) and \(y\), for the hourly profit, £P.
4. Mark points A and B on your graph where A and B represent the maximum and minimum values of P respectively. Make your method clear.
   (4)

9. \begin{figure}[h] \end{figure} Figure 7 shows an activity network. Each activity is represented by an arc and the number in brackets on each arc is the duration of the activity in days.

1. Complete Figure 7 in the answer book showing the early and late event times.
2. List the critical path for this network. The sum of all the activity times is 95 days and each activity requires just one worker. The project must be completed in the minimum time.
3. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must make your method clear.
4. On the grid in your answer book, draw a cascade (Gantt) chart for this network.