Questions - Edexcel D1 - A-Level Maths

Edexcel D1 2003 November Q4

4. (a) Draw an activity network described in this precedence table, using as few dummies as possible.

Activity	Must be preceded by:
A	-
B	A
C	A
D	A
E	C
F	C
G	B, $D , E , F$
H	$B , D , E , F$
I	F, $D$
J	G, H, I
K	$F , D$
L	$K$

A different project is represented by the activity network shown in Fig. 3. The duration of each activity is shown in brackets. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-05_710_1580_1509_239}
\end{figure} Find the range of values of $x$ that will make $D$ a critical activity.
(2)

Edexcel D1 2003 November Q5

5. Nine pieces of wood are required to build a small cabinet. The lengths, in cm, of the pieces of wood are listed below. $$20 , \quad 20 , \quad 20 , \quad 35 , \quad 40 , \quad 50 , \quad 60 , \quad 70 , \quad 75$$ Planks, one metre in length, can be purchased at a cost of $\pounds 3$ each.

The first fit decreasing algorithm is used to determine how many of these planks are to be purchased to make this cabinet. Find the total cost and the amount of wood wasted.
(5) Planks of wood can also be bought in 1.5 m lengths, at a cost of $\pounds 4$ each. The cabinet can be built using a mixture of 1 m and 1.5 m planks.
Find the minimum cost of making this cabinet. Justify your answer.
(4)

Edexcel D1 2003 November Q6

6. (a) Define the terms

tree,
spanning tree,
minimum spanning tree.
(3)
(b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.
(1) \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
\end{figure} (c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.
(4) \section*{Figure 5}
\includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
Figure 5 models a car park. Currently there are two pay-stations, one at $E$ and one at $N$. These two are linked by a cable as shown. New pay-stations are to be installed at $B , H , A , F$ and $C$. The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between $E$ and $N$ must be included in the final network. The minimum amount of new cable is to be used.
(d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.
(3)

Edexcel D1 2003 November Q7

7. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 6} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-10_1018_1557_342_214}

\end{figure} Figure 6 shows a capacitated, directed network of pipes flowing from two oil fields $\mathrm { F } _ { 1 }$ and $\mathrm { F } _ { 2 }$ to three refineries $\mathrm { R } _ { 1 } , \mathrm { R } _ { 2 }$ and $\mathrm { R } _ { 3 }$. The number on each arc represents the capacity of the pipe and the numbers in the circles represent a possible flow of 65.

Find the value of $x$ and the value of $y$.
On Diagram 1 in the answer book, add a supersource and a supersink, and arcs showing their minimum capacities.
Taking the given flow of 65 as the initial flow pattern, use the labelling procedure on Diagram 2 to find the maximum flow. State clearly your flow augmenting routes.
Show the maximum flow on Diagram 3 and write down its value.
Verify that this is the maximum flow by finding a cut equal to the flow.

Edexcel D1 2003 November Q8

8. A company makes three sizes of lamps, small, medium and large. The company is trying to determine how many of each size to make in a day, in order to maximise its profit. As part of the process the lamps need to be sanded, painted, dried and polished. A single machine carries out these tasks and is available 24 hours per day. A small lamp requires one hour on this machine, a medium lamp 2 hours and a large lamp 4 hours. Let $x =$ number of small lamps made per day, $$\begin{aligned} & y = \text { number of medium lamps made per day, }
& z = \text { number of large lamps made per day, } \end{aligned}$$ where $x \geq 0 , y \geq 0$ and $z \geq 0$.

Write the information about this machine as a constraint.
1. Re-write your constraint from part (a) using a slack variable $s$.
2. Explain what $s$ means in practical terms. Another constraint and the objective function give the following Simplex tableau. The profit $P$ is stated in euros.
  Basic variable $x$ $y$ $z$ $r$ $s$ Value
  $r$ 3 5 6 1 0 50
  $s$ 1 2 4 0 1 24
  $P$ - 1 - 3 - 4 0 0 0
Write down the profit on each small lamp.
Use the Simplex algorithm to solve this linear programming problem.
Explain why the solution to part (d) is not practical.
Find a practical solution which gives a profit of 30 euros. Verify that it is feasible.

Edexcel D1 2004 November Q1

1. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-02_753_1575_486_255}

\end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from $S$ to $T$ and the value in brackets on each arc is the flow in that arc.

Find the values of $x , y$ and $z$.
Find, by inspection, the maximal flow from $S$ to $T$ and verify that it is maximal.
(2)

Edexcel D1 2004 November Q2

2. (a) Define the following terms

planar graph,
Hamiltonian cycle.
(b) (i) Draw a graph of $\mathrm { K } _ { 3,2 }$ in such a way as to show that it is planar.
Explain why the planarity algorithm cannot be used when drawing $\mathrm { K } _ { 3,2 }$ as a planar graph.

Edexcel D1 2004 November Q3

3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.

	1	2	3	4	5	6
A					$\checkmark$
B	$\checkmark$			$\checkmark$
C	$\checkmark$	$\checkmark$		$\checkmark$
D					$\checkmark$
E			$\checkmark$		$\checkmark$	$\checkmark$
F				$\checkmark$

Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
A to 5,
C to 1 ,
E to 6,
F to 4
Show this information, in a distinctive way, on the diagram in the answer book.
(1)
Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
Explain why it is not possible to find a complete matching.

Edexcel D1 2004 November Q4

4. $45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51$

Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.
(2)
Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order. Another list of numbers, in ascending order, is $$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
Use the binary search algorithm to locate the number 73 in this list. \section*{5.} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
\end{figure} Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village $B$ has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from $A$ and $D$. The driver of a snowplough, based at $F$, is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge. Showing all your working and using an appropriate algorithm,

Edexcel D1 2004 November Q8

8. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-10_1042_1847_335_115}

\end{figure} The network in Figure 5 shows activities that need to be undertaken in order to complete a project. Each activity is represented by an arc. The number in brackets is the duration of the activity in hours. The early and late event times are shown at each node. The project can be completed in 24 hours.

Find the values of $x , y$ and $z$.
Explain the use of the dummy activity in Figure 5.
List the critical activities.
Explain what effect a delay of one hour to activity $B$ would have on the time taken to complete the whole project. The company which is to undertake this project has only two full time workers available. The project must be completed in 24 hours and in order to achieve this, the company is prepared to hire additional workers at a cost of $\pounds 28$ per hour. The company wishes to minimise the money spent on additional workers. Any worker can undertake any task and each task requires only one worker.
Explain why the company will have to hire additional workers in order to complete the project in 24 hours.
Schedule the tasks to workers so that the project is completed in 24 hours and at minimum cost to the company.
State the minimum extra cost to the company.

Edexcel D1 2002 January Q3

State the number of edges in a minimum spanning tree for $N$. A minimum spanning tree for a connected network has $n$ edges.
State the number of vertices in the network. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{2f4d2383-823a-4a6f-ad4b-69cf01566052-4_714_1129_380_476}
\end{figure} Figure 1 shows a network of roads. Erica wishes to travel from $A$ to $L$ as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
Use Dijkstra's algorithm to find a quickest route from $A$ to $L$. Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling.
Show that there is another route which also takes the minimum time

Edexcel D1 2004 January Q2

State, giving your reason, whether this tableau represents the optimal solution.
State the values of every variable.
Calculate the profit made on each unit of $y$. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-3_1193_1689_420_201}
\end{figure} Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from $B$ to $L$. Three cuts $\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }$ and $\mathrm { C } _ { 3 }$ are shown on Fig. 1.
Find the capacity of each of the three cuts.
Verify that the flow of 26 is maximal. The government aims to maximise the possible flow from $B$ to $L$ by using one of two options.
Option 1: Build a new road from $E$ to $J$ with capacity 5 .
or
Option 2: Build a new road from $F$ to $H$ with capacity 3.
By considering both options, explain which one meets the government's aim
(3) \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-4_780_1002_358_486}
\end{figure} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at $G$, so he starts and ends his journey at $G$.
Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length.
(6) The engineer lives at $D$. He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at $G$.
State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not.
(3)
\includegraphics[max width=\textwidth, alt={}, center]{a21a4565-800c-45c0-a513-bb813ef1086f-5_1561_1568_347_178} Figure 3 describes an algorithm in the form of a flow chart, where $a$ is a positive integer. List $P$, which is referred to in the flow chart, comprises the prime numbers $2,3,5,7,11,13$, 17, ...
Starting with $a = 90$, implement this algorithm. Show your working in the table in the answer book.
Explain the significance of the output list.
Write down the final value of $c$ for any initial value of $a$.

Edexcel D1 2002 June Q4

Use Dijkstra's algorithm to find the shortest route from $A$ to $I$. Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.
(5) The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at $A$.
1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
2. Find a route of minimum length.
3. Find the total length of this shortest route.
  (5)

Edexcel D1 2002 November Q4

Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node $C$. The inspection must still traverse each pipe at least once but may finish at any node.
Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
(3)

Edexcel D1 2004 November Q5

find the route the driver should follow, starting and ending at $F$, to clear all the roads of snow. Give the length of this route. The local authority decides to build a road bridge over the river at $B$. The snowplough will be able to cross the road bridge.
Reapply the algorithm to find the minimum distance the snowplough will have to travel (ignore the length of the new bridge). \section*{6.} \section*{Figure 3}
\includegraphics[max width=\textwidth, alt={}]{4bbe6272-3900-42de-b287-599638ca75e4-07_1131_1118_347_502}
Peter wishes to minimise the time spent driving from his home $H$, to a campsite at $G$. Figure 3 shows a number of towns and the time, in minutes, taken to drive between them. The volume of traffic on the roads into $G$ is variable, and so the length of time taken to drive along these roads is expressed in terms of $x$, where $x \geq 0$.
On the diagram in the answer book, use Dijkstra's algorithm to find two routes from $H$ to $G$ (one via $A$ and one via $B$ ) that minimise the travelling time from $H$ to $G$. State the length of each route in terms of $x$.
Find the range of values of $x$ for which Peter should follow the route via $A$. \section*{7.} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-08_1495_1335_322_392}
\end{figure} The company EXYCEL makes two types of battery, X and Y . Machinery, workforce and predicted sales determine the number of batteries EXYCEL make. The company decides to use a graphical method to find its optimal daily production of X and Y . The constraints are modelled in Figure 4 where $$\begin{aligned} & x = \text { the number (in thousands) of type } \mathrm { X } \text { batteries produced each day, }
& y = \text { the number (in thousands) of type } \mathrm { Y } \text { batteries produced each day. } \end{aligned}$$ The profit on each type X battery is 40 p and on each type Y battery is 20 p . The company wishes to maximise its daily profit.
Write this as a linear programming problem, in terms of $x$ and $y$, stating the objective function and all the constraints.
Find the optimal number of batteries to be made each day. Show your method clearly.
Find the daily profit, in $\pounds$, made by EXYCEL.

Edexcel D1 Q6

Draw a bipartite graph to model this situation. Initially it is decided to run the Office application on computer $F$, Animation on computer $H$, and Data on computer $I$.
Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied.
Computer $H$ is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b).

Edexcel D1 2014 January Q1

1. 11
17
10
14
8
13
6
4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.

Edexcel D1 2014 January Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
State the new minimum cost of connecting the nine buildings.

Edexcel D1 2014 January Q4

4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
State the new minimum cost of connecting the nine buildings.
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
Define the term 'matching'.
(2)
Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
(3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
(3)
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 367 metres]}
\end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.

Edexcel D1 2014 January Q11

11
17
10
14
8

Edexcel D1 2014 January Q14

14
8
13
6
4

Edexcel D1 2014 January Q17

17
10
14
8
13
6
4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
State the new minimum cost of connecting the nine buildings.
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
Define the term 'matching'.
(2)
Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
(3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
(3)
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 367 metres]}
\end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
(3)
6. A linear programming problem in $x$ and $y$ is described as follows. Minimise $\quad C = 2 x + 5 y$
subject to $$\begin{aligned} x + y & \geqslant 500
5 x + 4 y & \geqslant 4000
y & \leqslant 2 x
y & \geqslant x - 250
x , y & \geqslant 0 \end{aligned}$$
Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to $x + y \geqslant k$ for some value of $k$.
Determine the greatest value of $k$ for which P is still the optimal point.
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
Complete Diagram 1 in the answer book to show the early event times and late event times.
Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
Schedule the activities, using Grid 2 in the answer book.
8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
Pack B contains 30 posters and 50 flyers.
The charity must send out at least 15000 flyers.
The charity wants between $40 \%$ and $60 \%$ of the total packs produced to be Pack As.
Posters cost 15p each and flyers cost 3p each.
The charity wishes to minimise its costs.
Let $x$ represent the number of Pack As produced, and $y$ represent the number of Pack Bs produced.
Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
You should not attempt to solve the problem.
(Total 6 marks)

Edexcel D1 Q2

2. (a) Use the binary search algorithm to locate the name HUSSAIN in the following alphabetical list. Explain each step of the algorithm.

ALLEN
BALL
COOPER
EVANS
HUSSAIN
JONES
MICHAEL
PATEL
RICHARDS
TINDALL
WU
(b) State the maximum number of comparisons that need to be made to locate a name in an alphabetical list of 11 names.
(1 mark)

\begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-002_531_844_360_315} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} (a) Using an appropriate algorithm, obtain a suitable route starting and finishing at $A$.
(b) Calculate the total length of this route.
(2 marks)
4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed $( A )$ - Monday and Wednesday;
Miss Brown ( $B$ ) - Monday, Wednesday and Friday;
Ms. Clough ( $C$ ) - Monday;
Mr. Dingle ( $D$ ) - Tuesday, Wednesday and Thursday;
Mrs. Evans $( E )$ - Wednesday and Thursday.
The manager initially suggests that $A$ might work on Monday, $B$ on Wednesday and $D$ on Thursday.
(a) Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
(2 marks)
(b) Obtain an alternating path, starting at $C$, and use this to improve the initial matching.
(3 marks)
(c) Find another alternating path and hence obtain a complete matching.
(3 marks)
5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_352_904_450_287} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.
(a) Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
(b) Hence determine the critical activities and the length of the critical path. Each activity requires one worker. The project is to be completed in the minimum time.
(c) Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities.
(5 marks)
6. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_469_844_422_1731} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
(a) State the maximum flow along
(i) SAET,
(ii) SBDT,
(iii) SCFT.
(3 marks)
(b) Show these maximum flows on Diagram 1 on the answer sheet.
(1 mark)
(c) Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
(6 marks)
(d) Indicate a maximum flow on Diagram 3.
(2 marks)
(e) Prove that your flow is maximal.
(2 marks)
7. A tailor makes two types of garment, $A$ and $B$. He has available $70 \mathrm {~m} ^ { 2 }$ of cotton fabric and $90 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $A$ requires $1 \mathrm {~m} ^ { 2 }$ of cotton fabric and $3 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $B$ requires $2 \mathrm {~m} ^ { 2 }$ of each fabric. The tailor makes $x$ garments of type $A$ and $y$ garments of type $B$.
(a) Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70
& 3 x + 2 y \leq 90
& x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
The tailor sells type $A$ for $\pounds 30$ and type $B$ for $\pounds 40$. All garments made are sold. The tailor wishes to maximise his total income.
(b) Set up an initial Simplex tableau for this problem.
(3 marks)
(c) Solve the problem using the Simplex algorithm.
(8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure} (d) Obtain the coordinates of the points A, $C$ and $D$.
(e) Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
(3 marks) Answer Book (AB12)
Graph Paper (ASG2) Items included with question papers Answer booklet Paper Reference(s)
6689 \section*{Decision Mathematics D1 (New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Monday 25 June 2001 - Morning} Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G. In the boxes on the answer book, write the name of the examining body (Edexcel), your centre number, candidate number, the unit title (Decision Mathematics D1), the paper reference (6689), your surname, other name and signature. Full marks may be obtained for answers to ALL questions. This paper has seven questions. You must ensure that your answers to parts of questions are clearly labelled. You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit. \section*{END}

The precedence table for activities involved in a small project is shown below

Activity	Preceding Activities
$A$	-
$B$	-
$C$	-
$D$	$B$
$E$	$A$
$F$	$A$
$G$	$B$
$H$	$C , D$
$I$	$E$
$J$	$E$
$K$	$F , G , I$
$L$	$H , J , K$

Draw an activity network, using activity on edge and without using dummies, to model this project.
2. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-005_464_716_370_1740}

\end{figure} Figure 1 shows 7 locations $A , B , C , D , E , F$ and $G$ which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.
(a) Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
(b) Draw your minimum spanning tree and find the least cost of the pipelines.

Edexcel D1 Q4

4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed $( A )$ - Monday and Wednesday;
Miss Brown ( $B$ ) - Monday, Wednesday and Friday;
Ms. Clough ( $C$ ) - Monday;
Mr. Dingle ( $D$ ) - Tuesday, Wednesday and Thursday;
Mrs. Evans $( E )$ - Wednesday and Thursday.
The manager initially suggests that $A$ might work on Monday, $B$ on Wednesday and $D$ on Thursday.

Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
(2 marks)
Obtain an alternating path, starting at $C$, and use this to improve the initial matching.
(3 marks)
Find another alternating path and hence obtain a complete matching.
(3 marks)

Edexcel D1 Q5

5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h]