Edexcel D1 (Decision Mathematics 1) 2020 January

1. The table below shows the distances, in km , between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.
   (2)
2. Starting by deleting B , and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.
   (3)

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

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the minimum spanning tree.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration, in days, is shown in brackets. Each activity requires one worker. The early event times and late event times are shown at each vertex. The total float on activity D is twice the total float on activity E .

1. Find the values of \(x , y\) and \(z\).
2. Draw a cascade chart for this project on Grid 1 in the answer book.
3. Use your cascade chart to determine a lower bound for the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

4. $$\begin{array} { l l l l l l l l l l } 35 & 17 & 10 & 7 & 28 & 23 & 41 & 15 & 20 & 29 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 60 The ten distinct numbers below are to be sorted into descending order. $$\begin{array} { l l l l l l l l l l } 20 & 24 & 17 & 26 & 8 & 15 & x & y & 19 & 12 \end{array}$$ A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.
   After the second complete pass the list is $$\begin{array} { l l l l l l l l l l } 24 & 26 & 20 & 17 & 15 & y & 19 & 12 & x & 8 \end{array}$$
4. Find the constraints on the values of \(x\) and \(y\).

5.

1. Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies. Given that all critical paths for the network include activity H ,
2. state which activities cannot be critical.
   (2)

6. \begin{figure}[h] \end{figure} [The total weight of the network is 269] Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, 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. Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan's inspection route from H to D. You must make your method and working clear. For Alan's inspection route from H to D
3. 1. state the number of times vertex C will appear,
   2. state the number of times vertex D will appear.
4. Determine whether it would be quicker for Alan to start and finish his inspection route at H , instead of starting at H and finishing at D . You must explain your reasoning and show all your working.