Edexcel D1 (Decision Mathematics 1) 2018 June

1. \begin{figure}[h] \end{figure}

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.

2. A list of nine numbers needs to be sorted into descending order.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list. Mayleen used a sorting algorithm to sort a list of nine numbers into descending order. Mayleen's list after the first pass through the algorithm is given below. $$\begin{array} { l l l l l l l l l } 30 & 33 & 35 & 27 & 20 & 24 & 21 & 15 & 19 \end{array}$$
2. Explain how you know that Mayleen did not use the bubble sort algorithm. Given that Mayleen used the quick sort algorithm,
3. write down the number that was used as a pivot for the first pass,
4. complete the quick sort to obtain a fully sorted list in descending order. You must make your pivots clear.
5. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60 A tenth number, 18, is added to the list of nine numbers.
6. Determine whether it is possible to pack the ten numbers into 4 bins of size 60 . You must justify your answer.

3. (a) Draw the activity network described in the precedence table below, using activity on arc and exactly four dummies.
(5) Given that D is a critical activity,
(b) state which other activities must also be critical.
(2)

4. \begin{figure}[h] \end{figure} [The total weight of the network is 293] Figure 2 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along the corresponding road.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J . State the quickest route.
   (6) The road represented by edge GJ is closed due to essential maintenance. Sahil needs to travel along all the other roads to check that they are in good repair. Sahil wishes to complete his route as quickly as possible and will start and finish at the same vertex.
2. Use the route inspection algorithm to find the duration of Sahil's quickest route. State the edges that will need to be traversed twice. You should make your method and working clear.
   (6) Given that Sahil will start and finish at vertex C,
3. state the number of times that Sahil will visit vertex E and vertex F in his inspection route.
   (2)

5. \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5. In an initial matching, each of three workers is allocated to a different task. For this initial matching, there are three possible alternating paths that start at C . One alternating path is $$C - 3 = S - 4 = D - 5$$ A second alternating path is $$\mathrm { C } - 1 = \mathrm { H } - 2$$

1. Use this information to deduce the initial matching.
2. Find the third alternating path that starts at C .
3. List the improved matching generated by using the alternating path \(\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5\)
4. Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
   (3)

6. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. State the critical activities.
3. Draw a cascade (Gantt) chart for this project on the grid in the answer book.
4. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. (You do not need to provide a schedule of the activities.)

20
22
24
26
28
30
32
34
36
38
\end{tabular}}} &
\hline & & & & & & & & & & & & & & & & & & & &
\hline \hline & 1 & I & I & । & I & I & I & I & I & I & I & I & I & I & I & I & I & I & 1 &
\hline & 1 & I & I & I & 1 & 1 & & I & I & I & I & I & 1 & I & I & I & I & 1 & । &
\hline \multirow{7}{*}{\includegraphics[max width=\textwidth, alt={}]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-23_1401_67_1168_25} } & & & & & & & & & & & & & & & & & & & I &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & \multicolumn{19}{|r|}{\multirow[b]{2}{*}{(Total 11 marks)}} &
\hline & & & & & & & & & & & & & & & & & & & &
\hline & & & & & & & & & & & & & & & & & & & &
\hline \end{tabular} \end{center} 7. \section*{Diagram 1}