Edexcel FD1 (Further Decision 1) 2021 June

1. \begin{figure}[h] \end{figure} A Hamiltonian cycle for the graph in Figure 1 begins \(\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots\).

1. Complete the Hamiltonian cycle.
2. Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.

2. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
2. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
3. Schedule the activities using Grid 1 in the answer book.

3. \begin{table}[h] \end{table} Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.
2. State the weight of the minimum spanning tree. \begin{table}[h]

   \cline { 2 - 9 } \multicolumn{1}{c|}{}	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)	\(\mathbf { G }\)	\(\mathbf { H }\)
   \(\mathbf { J }\)	31	27	50	29	43	25	49	35

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the distances, in miles, between town J and towns A , B , \(\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .
   Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.
3. Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
4. Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.

4. \begin{figure}[h] \end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

1. Set up the initial time matrix.
2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	A	B	C	D	E	F
   A	-	57	95	147	63	220
   B	57	-	72	204	120	197
   C	95	72	-	242	158	125
   D	147	204	242	-	84	275
   E	63	120	158	84	-	191
   F	220	197	125	275	191	-

   A route is needed that minimises the total time taken to traverse each road at least once.
   The route must start at B and finish at E .
3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
4. Write down the length of the route.

1. 30312522318136101524
   1. The list of ten numbers above 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.
   The ten numbers are to be packed into bins of size \(n\), where \(n\) is a positive integer.
   When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.

   Bin 1:	30	12	2
   Bin 2:	5	23	10
   Bin 3:	18	15
   Bin 4:	36
   Bin 5:	24

2. Explain why the value of the integer \(n\) must be either 44 or 45
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45

6. \begin{figure}[h] \end{figure} In Figure 4 the weights on the arcs represent distances.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to H .
   2. State the length of the shortest path from A to H . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
2. Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
3. Explain why your answer to part (b) can only be an approximation.

7. \begin{figure}[h] \end{figure} Figure 5 shows a partially completed activity network for a project that consists of 14 activities.

1. Complete the precedence table in the answer book for the 8 activities in Figure 5. The precedence table for the remaining 6 activities is given below.

   Activity	Immediately preceding activities
   I	D, E, G, H
   J	D, E, G, H
   K	E, G, H
   L	I, J, K
   M	J, K
   N	J, K

2. Complete the activity network in the answer book for the project. Your completed activity network must contain only the minimum number of dummies. Given that all 14 activities have the same duration,
3. explain why activity D cannot be critical.

8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should

• maximise the total time spent cycling and running
• train for at most 39 hours
• spend at least \(40 \%\) of her time swimming
• spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

• \(x\) represent the number of hours swimming
• \(y\) represent the number of hours cycling
• \(z\) represent the number of hours running
  1. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.
     (5)

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how

• the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable
• the rows for the two objective functions are formed
  (6)

The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.

b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(\mathrm { S } _ { 2 }\)	\(S _ { 3 }\)	Value
\(y\)	0	1	0	1	0	1	11
\(s _ { 2 }\)	0	0	5	-2	1	-5	62
\(x\)	1	0	1	0	0	-1	28
\(P\)	0	0	-1	1	0	1	11

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.