Questions D1 - A-Level Maths

OCR MEI D1 2005 January Q2

2 Answer this question on the insert provided.

Use Dijkstra's algorithm to find the least weight route from $A$ to $G$ in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
\end{figure}
Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
\end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

OCR MEI D1 2005 January Q4

4 Answer this question on the insert provided. The table shows activities involved in a "perm" in a hair salon, their durations and immediate predecessors. \begin{table}[h]

	Activity	Duration (mins)	Immediate predecessor(s)
A	shampoo	5	-
B	prepare perm lotion	2	-
C	make coffee for customer	3	-
D	trim	5	A
E	clean sink	3	A
F	put rollers in	15	D
G	clean implements	3	D
H	apply perm lotion	5	B, F
I	leave to set	20	C,H
J	clean lotion pot and spreaders	3	H
K	neutralise and rinse	10	I, E
L	dry	10	K
M	wash up and clean up	15	K
N	style	4	G, L

\captionsetup{labelformat=empty} \caption{Table 4}

\end{table}

Complete the activity-on-arc network in the insert to represent the precedences.
Perform a forward pass and a backward pass to find early and late event times. Give the critical activities and the time needed to complete the perm.
Give the total float time for the activity $G$. Activities $\mathrm { D } , \mathrm { F } , \mathrm { H } , \mathrm { K }$ and N require a stylist.
Activities $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { E } , \mathrm { G } , \mathrm { J }$ and M are done by a trainee.
Activities $I$ and $L$ require no-one in attendance.
A stylist and a trainee are to give a perm to a customer.
Use the chart in the insert to show a schedule for the activities, assuming that all activities are started as early as possible.
Which activity would be better started at its latest start time?

OCR MEI D1 2005 June Q1

1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-2_486_879_623_607} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.

Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
What is the minimum number of connections which the electrician will have to make if he uses the junction box?
The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
Will this result in the minimum number of connections? Justify your answer.

OCR MEI D1 2005 June Q2

2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_495_717_470_671} \captionsetup{labelformat=empty} \caption{Fig. 2.1}

\end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."

On the insert for this question show Janet's route through the maze. On the insert show John's route.
Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where $\mathbf { X }$ is the marked point. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
\end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to $\mathbf { X }$. John's algorithm does not take him to $\mathbf { X }$. John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting $\mathbf { X }$. He will then move onwards, continuing to keep a hand in contact with the wall on the left.
Will this modified algorithm take John to the point $\mathbf { X }$ in the maze in Fig. 2.2?
Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.

OCR MEI D1 2005 June Q4

8 marks

4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-5_536_828_573_642} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure}

Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.

OCR MEI D1 2006 June Q1

2 marks

1 Answer this question on the insert provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-2_658_739_466_662} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D. Give your route and its weight.
Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.
[0pt] [2]

OCR MEI D1 2006 June Q6

6 Answer parts (ii)(A) and (iii)(B) of this question on the insert provided. A particular component of a machine sometimes fails. The probability of failure depends on the age of the component, as shown in Table 6.

Year of life

first

second

third

fourth

fifth

sixth

Probability of failure during year,

given no earlier failure

0.10

0.05

0.02

0.20

0.30

\section*{Table 6} You are to simulate six years of machine operation to estimate the probability of the component failing during that time. This will involve you using six 2-digit random numbers, one for each year.

Give a rule for using a 2-digit random number to simulate failure of the component in its first year of life. Similarly give rules for simulating failure during each of years 2 to 6 .
(A) Use your rules, together with the random numbers given in the insert, to complete the simulation table in the insert. This simulates 10 repetitions of six years operation of the machine. Start in the first column working down cell-by-cell. In each cell enter a tick if there is no simulated failure and a cross if there is a simulated failure. Stop and move on to the next column if a failure occurs.
(B) Use your results to estimate the probability of a failure occurring. It is suggested that any component that has not failed during the first three years of its life should automatically be replaced.
(A) Describe how to simulate the operation of this policy.
(B) Use the table in the insert to simulate 10 repetitions of the application of this policy. Re-use the same random numbers that are given in the insert.
(C) Use your results to estimate the probability of a failure occurring.
How might the reliability of your estimates in parts (ii) and (iii) be improved?

OCR MEI D1 2006 January Q5

5 Answer this question on the insert provided. Table 5 specifies a road network connecting 7 towns, A, B, $\ldots$, G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads. \begin{table}[h]

	A	B	C	D	E	F	G
A	-	10	-	-	-	12	15
B	10	-	15	20	-	-	8
C	-	15	-	7	-	-	11
D	-	20	7	-	20	-	13
E	-	-	-	20	-	17	9
F	12	-	-	-	17	-	13
G	15	8	11	13	9	13	-

\captionsetup{labelformat=empty} \caption{Table 5}

\end{table}

Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices. Draw the resulting tree, give its total length and describe a practical application.
The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E. Give your route and its length.
A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?

OCR MEI D1 2006 January Q6

6 Answer part (iv) of this question on the insert provided. There are two types of customer who use the shop at a service station. $70 \%$ buy fuel, the other $30 \%$ do not. There is only one till in operation.

Give an efficient rule for using one-digit random numbers to simulate the type of customer arriving at the service station. Table 6.1 shows the distribution of time taken at the till by customers who are buying fuel.
Time taken (mins) 1 1.5 2 2.5
Probability $\frac { 3 } { 10 }$ $\frac { 2 } { 5 }$ $\frac { 1 } { 5 }$ $\frac { 1 } { 10 }$
\section*{Table 6.1}
Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel.
Time taken (mins) 1 1.5 2 2.5 3
Probability $\frac { 1 } { 7 }$ $\frac { 2 } { 7 }$ $\frac { 2 } { 7 }$ $\frac { 1 } { 7 }$ $\frac { 1 } { 7 }$
\section*{Table 6.2}
Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
Complete the table using the random numbers which are provided.
Calculate the mean total time spent queuing and paying.

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]

\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.

Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
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.
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)

Edexcel D1 Q6

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.

State the maximum flow along
1. SAET,
2. SBDT,
3. SCFT.
  (3 marks)
Show these maximum flows on Diagram 1 on the answer sheet.
(1 mark)
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)
Indicate a maximum flow on Diagram 3.
(2 marks)
Prove that your flow is maximal.
(2 marks)

Edexcel D1 Q7

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$.

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.
Set up an initial Simplex tableau for this problem.
(3 marks)
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}
Obtain the coordinates of the points A, $C$ and $D$.
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}
1. The precedence table for activities involved in a small project is shown below
Explain
1. the purpose of the variables $r , s$ and $t$,
2. the final row of the tableau.
Solve this Linear Programming problem by using the Simplex alogorithm. Increase $y$ for your first iteration and than increase $x$ for your second iteration.
Interpret your solution. \section*{Materials required for examination
Graph Paper (ASG2)} Items included with question papers
Answer booklet \section*{Decision Mathematics D1 (New Syllabus)
\textbackslash section*\{Advanced/Advanced Subsidiary\}} \section*{Friday 18 January 2002 - Afternoon} 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 your centre number, candidate number, your surname, initials 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.
1. Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs $1,2,3,4$ or 5 . The table shows each member's preferences for the jobs.
Ann 1 or 2
Bryn 3 or 1
Daljit 2 or 4
Gareth 5 or 3
Nickos 1 or 2
Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
Find a second alternating path from the initial allocation.
2. (i) Use the binary search algorithm to try to locate the name SABINE in the following alphabetical list. Explain each step of the algorithm.
1. ABLE
2. BROWN
3. COOKE
4. DANIEL
5. DOUBLE
6. $F E W$
7. OSBORNE
8. PAUL
9. SWIFT
10. TURNER
  (ii) Find the maximum number of iterations of the binary search algorithm needed to locate a name in a list of 1000 names.
$A$ $B$ $C$ $D$ $E$ $F$
$A$ - 10 12 13 20 9
$B$ 10 - 7 15 11 7
$C$ 12 7 - 11 18 3
$D$ 13 15 11 - 27 8
$E$ 20 11 18 27 - 18
$F$ 9 7 3 8 18 -
The table shows the distances, in metres, between six nodes $A , B , C , D , E$, and $F$ of a network.
Use Prim's algorithm, starting at $A$, to solve the minimum connector problem for this table of distances. Explain your method and indicate the order in which you selected the edges.
Draw your minimum spanning tree and find its total length.
State whether your minimum spanning tree is unique. Justify your answer.
(ii) A connected network $N$ has seven vertices.
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]{3147dad8-2d3c-42fd-b288-7017ff1fce16-010_474_737_379_367}
\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
5. Two fertilizers are available, a liquid $X$ and a powder $Y$. A bottle of $X$ contains 5 units of chemical $A , 2$ units of chemical $B$ and $\frac { 1 } { 2 }$ unit of chemical $C$. A packet of $Y$ contains 1 unit of $A , 2$ units of $B$ and 2 units of $C$. A professional gardener makes her own fertilizer. She requires at least 10 units of $A$, at least 12 units of $B$ and at least 6 units of $C$. She buys $x$ bottles of $X$ and $y$ packets of $Y$.
Write down the inequalities which model this situation.
On the grid provided construct and label the feasible region. A bottle of $X$ costs $\pounds 2$ and a packet of $Y$ costs $\pounds 3$.
Write down an expression, in terms of $x$ and $y$, for the total cost $\pounds T$.
Using your graph, obtain the values of $x$ and $y$ that give the minimum value of $T$. Make your method clear and calculate the minimum value of $T$.
Suggest how the situation might be changed so that it could no longer be represented graphically. Figure 2 \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{6.} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_403_789_372_324}
\end{figure} A company has 3 warehouses $W _ { 1 } , W _ { 2 }$, and $W _ { 3 }$. It needs to transport the goods stored there to 2 retail outlets $R _ { 1 }$ and $R _ { 2 }$. The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses $W _ { 1 } , W _ { 2 }$ and $W _ { 3 }$ have 14, 12 and 14 van loads respectively available per day and retail outlets $R _ { 1 }$ and $R _ { 2 }$ can accept 6 and 25 van loads respectively per day.
On Diagram 1 on the answer sheet add a supersource $W$, a supersink $R$ and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
State the maximum flow along
1. $W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R$,
2. $W W _ { 3 } \quad C \quad R _ { 2 } \quad R$.
Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from $W$ to $R$. Show your working on Diagram 2. List each flow-augmenting route you use, together with its flow.
From your final flow pattern, determine the number of van loads passing through $B$ each day. The company has the opportunity to increase the number of vans loads from one of the warehouses $W _ { 1 } , W _ { 2 } , W _ { 3 }$, to $A , B$ or $C$.
Determine how the company should use this opportunity so that it achieves a maximal flow.
, 啨 \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_307_990_404_1690}
\end{figure} A project is modelled by the activity network shown in Fig 3. The activities are represented by the edges. The number in brackets on each edge gives the time, in days, taken to complete the activity.
Calculate the early time and the late time for each event. Write these in the boxes on the answer sheet.
Hence determine the critical activities and the length of the critical path.
Obtain the total float for each of the non-critical activities.
On the first grid on the answer sheet, draw a cascade (Gantt) chart showing the information obtained in parts (b) and (c). Each activity requires one worker. Only two workers are available.

On the second grid on the answer sheet, draw up a schedule and find the minimum time in which the 2 workers can complete the project. \section*{(New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Thursday 23 May 2002 - Afternoon} Nil Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must 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 your centre number, candidate number, your surname, initials and signature.
When a calculator is used, the answer should be given to an appropriate degree of accuracy. Full marks may be obtained for answers to ALL questions.
This paper has eight 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.
1.

Ashford	6
Colnbrook	1
Datchet	18
Feltham	12
Halliford	9
Laleham	0
Poyle	5
Staines	13
Wraysbury	14

The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.
2. While solving a maximizing linear programming problem, the following tableau was obtained.

Basic

variable

$x$

$y$

$z$

$r$

$s$

$t$

Value

$r$

0

$1 \frac { 2 } { 3 }$

1

0

$- \frac { 1 } { 6 }$

$\frac { 2 } { 3 }$

$y$

0

1

$3 \frac { 1 } { 3 }$

0

1

$- \frac { 1 } { 3 }$

$\frac { 1 } { 3 }$

$x$

1

0

- 3

0

- 1

$\frac { 1 } { 2 }$

1

$P$

0

1

0

1

11

Explain why this is an optimal tableau.
Write down the optimal solution of this problem, stating the value of every variable.
Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of $P$.
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_291_307_395_383}
\end{figure} \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_287_311_397_781}
\end{figure} Five members of staff $1,2,3,4$ and 5 are to be matched to five jobs $A , B , C , D$ and $E$. A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching $M$ is given in Fig. 2. There are several distinct alternating paths that can be generated from $M$. Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$
Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching $M$,
find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_380_965_374_1690}
\end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices $A$ and $I$ represent the two gates in the park and the vertices $B , C , D , E , F , G$ and $H$ represent places of interest.
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. 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. An algorithm is described by the flow chart below.
  \includegraphics[max width=\textwidth, alt={}, center]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_1040_825_372_411}
Given that $a = 645$ and $b = 255$, complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
Explain how your solution to part (a) would be different if you had been given that $a = 255$ and $b = 645$.
State what the algorithm achieves. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_711_1049_411_1640}
\end{figure} A building project is modelled by the activity network shown in Fig. 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. The left box entry at each vertex is the earliest event time and the right box entry is the latest event time.
Determine the critical activities and state the length of the critical path.
State the total float for each non-critical activity.
On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
draw up a schedule to determine the minimum number of workers required to complete the project in the critical time. State the minimum number of workers.
7. A company wishes to transport its products from 3 factories $F _ { 1 } , F _ { 2 }$ and $F _ { 3 }$ to a single retail outlet $R$. The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-015_472_766_520_342}
\end{figure}
On Diagram 1 in the answer booklet add a supersource $S$ to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
1. State the maximum flow along $S F _ { 1 } A B R$ and $S F _ { 3 } C R$.
2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
1. use the labelling procedure to find a maximum flow from $S$ to $R$. Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
2. Prove that your final flow is maximal.

Edexcel D1 Q8

8. A chemical company produces two products $X$ and $Y$. Based on potential demand, the total production each week must be at least 380 gallons. A major customer's weekly order for 125 gallons of $Y$ must be satisfied. Product $X$ requires 2 hours of processing time for each gallon and product $Y$ requires 4 hours of processing time for each gallon. There are 1200 hours of processing time available each week. Let $x$ be the number of gallons of $X$ produced and $y$ be the number of gallons of $Y$ produced each week.

Write down the inequalities that $x$ and $y$ must satisfy. It costs $\pounds 3$ to produce 1 gallon of $X$ and $\pounds 2$ to produce 1 gallon of $Y$. Given that the total cost of production is $\pounds C$,
express $C$ in terms of $x$ and $y$. The company wishes to minimise the total cost.
Using the graphical method, solve the resulting Linear Programming problem. Find the optimal values of $x$ and $y$ and the resulting total cost.
Find the maximum cost of production for all possible choices of $x$ and $y$ which satisfy the inequalities you wrote down in part (a). \section*{(New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Tuesday 5 November 2002 - Morning} \section*{Materials required for examination
Graph Paper (ASG2)} Items included with question papers
Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must 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 your centre number, candidate number, your surname, initials and signature.
When a calculator is used, the answer should be given to an appropriate degree of accuracy. Full marks may be obtained for answers to ALL questions.
This paper has eight questions. Page 8 is blank. 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.
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-016_312_446_360_1873}
\end{figure} A Hamilton cycle for the graph in Fig. 1 begins $A , X , D , V , \ldots$.
Complete this Hamiltonian cycle.
Hence use the planarity algorithm to determine if the graph is planar.
2. The precedence table for activities involved in manufacturing a toy is shown below. A bipartite graph showing this information is drawn in the answer booklet.
Initially, $A , B , D$ and $E$ are allocated to tasks 2, 1, 3 and 5 respectively.
Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly.
2. (a) Explain why it is impossible to draw a network with exactly three odd vertices. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_460_700_1160_388}
\end{figure} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100 .
Determine the value of $x$, showing your working clearly.
3. (a) Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_415_800_383_1720}
\end{figure}
Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
1. Prim's algorithm,
2. Kruskal's algorithm.
  4. The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper ( $R$ ), Palmer ( $P$ ), Boase ( $B$ ), Young ( $Y$ ), Thomas ( $T$ ), Kenney ( $K$ ), Morris ( $M$ ), Halliwell ( $H$ ), Wicker ( $W$ ), Garesalingam ( $G$ ).
Use the quick sort algorithm to sort the names above into alphabetical order.
Use the binary search algorithm to locate the name Kenney.
5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-025_330_1059_315_214}
\end{figure} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.
Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet.
Hence determine the critical activities.
Calculate the total float time for $D$. Each activity requires only one person.
Find a lower bound for the number of workers needed to complete the process in the minimum time. Given that there are only three workers available, and that workers may not share an activity,
schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time.
6. A company produces two types of self-assembly wooden bedroom suites, the 'Oxford' and the 'York'. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite.
On the diagram in the answer book draw straight lines to show which components need to be connected.
Starting with the Hamiltonian cycle $A B C D E F A$, use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
(4)
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-028_997_458_285_468}
\end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people $A , B , C , D , E$ and $F$ to tasks $1,2,3,4,5$ and 6 . An initial matching is obtained by matching the following pairs
A to 3,
B to 4,
$C$ to 1,
$F$ to 5 .
Show this matching in a distinctive way on the diagram in the answer book.
Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
4. (a) Draw an activity network described in this precedence table, using as few dummies as possible. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.
Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use.
Explain why it is not possible to find a complete matching. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-037_385_1072_283_1658}
\end{figure} Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from $S$ to $T$ as quickly as possible.
Use Dijkstra's algorithm to find the shortest time to travel from $S$ to $T$.
Find a route for Avinash to travel from $S$ to $T$ in the shortest time. State, with a reason, whether this route is a unique solution. On a particular day Avinash must include $C$ in his route.
Find a route of minimal time from $S$ to $T$ that includes $C$, and state its time.
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-038_430_497_251_452}
\end{figure}
Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm.
Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
State whether your answer to part (b) is unique. Give a reason for your answer.
Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. Given that it is permitted to start and finish the inspection at two distinct vertices,
find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer.
4.
1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth
A binary search is to be performed on the names in the list above to locate the name Newcastle.
Explain why a binary search cannot be performed with the list in its present form.
Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use.
Use the binary search algorithm on your new list to locate the name Newcastle.

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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-004_816_1298_343_391} \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.
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: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; }
& \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; }
& \text { Ms. Clough } ( C ) \text { - Monday; }
& \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; }
& \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ 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.
(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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-006_542_1389_483_352} \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.
(6 marks)
(b) Hence determine the critical activities and the length of the critical path.
(2 marks)
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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-007_732_1308_433_388} \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.
(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.
(d) Indicate a maximum flow on Diagram 3.
(e) Prove that your flow is maximal.
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}$$ 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.
(c) Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \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. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
Final tree
(b) Minimum total length of cable
Question 4 to be answered on this page
(a) $A$

Monday (M)
$B$ ◯
Tuesday (Tu)
$C \odot$
Wednesday (W)
$D$ ◯
Thursday (Th)
$E$ -
Friday (F)
(b)
(c)

Question 5 to be answered on this page
Key
(a) Early
Time
Late
Time
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201}
$F ( 3 )$
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
H(4) K(6)
(b) Critical activities
Length of critical path $\_\_\_\_$
(c)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
(a) (i) SAET $\_\_\_\_$
(ii) SBDT $\_\_\_\_$
(iii) SCFT $\_\_\_\_$
(b) \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}

\end{figure} (c) \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}

\end{figure} Flow augmenting routes
(d) \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}

\end{figure} (e) $\_\_\_\_$
\section*{Decision Mathematics D1
(New Syllabus)
Advanced/Advanced Subsidiary } Monday 25 June 2001 - Morning
Time: 1 hour 30 minutes Materials required for examination
Answer Book (AB12)
Graph Paper (ASG2) Items included with question papers
Answer booklet 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.

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.
(5)
2. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-016_708_1096_360_408}

\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.
(4)
(b) Draw your minimum spanning tree and find the least cost of the pipelines.
(3)

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: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; }
& \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; }
& \text { Ms. Clough } ( C ) \text { - Monday; }
& \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; }
& \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ 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.
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]

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-006_542_1389_483_352} \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.

Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
(6 marks)
Hence determine the critical activities and the length of the critical path.
(2 marks)
Each activity requires one worker. The project is to be completed in the minimum time.
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)

Edexcel D1 Q6

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

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-007_732_1308_433_388} \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.

State the maximum flow along
1. SAET,
2. SBDT,
3. SCFT.
  (3 marks)
Show these maximum flows on Diagram 1 on the answer sheet.
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.
Indicate a maximum flow on Diagram 3.
Prove that your flow is maximal.

Time taken (mins)	1	1.5	2	2.5	3
Probability	\(\frac { 1 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(\frac { 1 } { 7 }\)

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\)

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\)

Questions D1 (899 questions)

Browse by module

Browse by board

OCR MEI D1 2005 January Q2

OCR MEI D1 2005 January Q4

OCR MEI D1 2005 June Q1

OCR MEI D1 2005 June Q2

OCR MEI D1 2005 June Q4

OCR MEI D1 2006 June Q1

OCR MEI D1 2006 June Q6

OCR MEI D1 2006 January Q5

OCR MEI D1 2006 January Q6

Edexcel D1 2014 January Q1

Edexcel D1 2014 January Q2

Edexcel D1 2014 January Q4

Edexcel D1 2014 January Q11

Edexcel D1 2014 January Q14

Edexcel D1 2014 January Q17

Edexcel D1 Q2

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q8

Edexcel D1 Q2

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

	A	B	C	D	E	F	G
A	-	10	-	-	-	12	15
B	10	-	15	20	-	-	8
C	-	15	-	7	-	-	11
D	-	20	7	-	20	-	13
E	-	-	-	20	-	17	9
F	12	-	-	-	17	-	13
G	15	8	11	13	9	13	-

Time taken (mins)	1	1.5	2	2.5
Probability	\(\frac { 3 } { 10 }\)	\(\frac { 2 } { 5 }\)	\(\frac { 1 } { 5 }\)	\(\frac { 1 } { 10 }\)

Ann	1 or 2
Bryn	3 or 1
Daljit	2 or 4
Gareth	5 or 3
Nickos	1 or 2

	A	B	C	D	E	F	G
A	-	10	-	-	-	12	15
B	10	-	15	20	-	-	8
C	-	15	-	7	-	-	11
D	-	20	7	-	20	-	13
E	-	-	-	20	-	17	9
F	12	-	-	-	17	-	13
G	15	8	11	13	9	13	-

	A	B	C	D	E	F	G
A	-	10	-	-	-	12	15
B	10	-	15	20	-	-	8
C	-	15	-	7	-	-	11
D	-	20	7	-	20	-	13
E	-	-	-	20	-	17	9
F	12	-	-	-	17	-	13
G	15	8	11	13	9	13	-