Questions - Edexcel D1 - A-Level Maths

Explain the significance of the dummy activity
1. from event 4 to event 6 ,
2. from event 5 to event 7
  (3)
Calculate the early time and the late time for each event. Write these in the boxes in the answer book.
Calculate the total float on each of activities D and G. You must make the numbers you use in your calculations clear.
Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time.
On the grid in your answer book, draw a cascade (Gantt) chart for this project.

Edexcel D1 2013 January Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-2_1095_1104_292_475} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Hero's algorithm for finding a square root is described by the flow chart shown in Figure 1.
Given that $\mathrm { N } = 72$ and $\mathrm { E } = 8$,

use the flow chart to complete the table in the answer book, working to at least seven decimal places when necessary. Give the final output correct to seven decimal places. The flow chart is used with $\mathrm { N } = 72$ and $\mathrm { E } = - 8$,
describe how this would affect the output.
State the value of E which cannot be used when using this flow chart.

Edexcel D1 2013 January Q2

2. (a) Starting with a list of all the letters of the alphabet in alphabetical order, demonstrate how a binary search is used to locate the letter P. In each iteration, you must make clear your pivot and the part of the list you are retaining.
(4)
(b) Find the maximum number of iterations needed to locate any particular letter of the alphabet. Justify your answer.

Edexcel D1 2013 January Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-3_743_625_758_269} \captionsetup{labelformat=empty} \caption{Figure 2}

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

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-3_746_608_758_1142} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 2 shows the possible allocations of six workers, Charlie (C), George (G), Jack (J), Nurry (N), Olivia (O) and Rachel (R), to six tasks, $1,2,3,4,5$ and 6. Figure 3 shows an initial matching.

Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should give the alternating path you use and list your improved matching.
Explain why it is not possible to find a complete matching. After training, Charlie adds task 5 to his possible allocations.
Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. Give the alternating path you use and list your complete matching.

Edexcel D1 2013 January Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-4_629_1392_187_319} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure}

Explain what is meant, in a network, by the term path.
(2) Figure 4 represents a network of canals. The number on each arc represents the length, in miles, of the corresponding canal.
Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length.
Write down the length of the shortest path from S to F . Next week the canal represented by $\operatorname { arc } \mathrm { AB }$ will be closed for dredging.
Find a shortest path from S to T avoiding AB and state its length.

Edexcel D1 2013 January Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-5_588_1170_212_427} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} [The weight of the network is 379]
Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km , of the corresponding road. During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

Use Prim's algorithm, starting at A , to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs.
Given that it costs $\pounds 80$ per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations. At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.
Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear.
Find the length of the shortest inspection route. If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.
Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route.

Edexcel D1 2013 January Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-6_1630_1461_219_301} \captionsetup{labelformat=empty} \caption{Figure 6}

\end{figure} Lethna is producing floral arrangements for an awards ceremony.
She will produce two types of arrangement, Celebration and Party.
Let $x$ be the number of Celebration arrangements made.
Let $y$ be the number of Party arrangements made.
Figure 6 shows three constraints, other than $x , y \geqslant 0$
The rejected region has been shaded.
Given that two of the three constraints are $y \leqslant 30$ and $x \leqslant 60$,

write down, as an inequality, the third constraint shown in Figure 6. Each Celebration arrangement includes 2 white roses and 4 red roses.
Each Party arrangement includes 1 white rose and 5 red roses.
Lethna wishes to use at least 70 white roses and at least 200 red roses.
Write down two further inequalities to represent this information.
(3)
Add two lines and shading to Diagram 1 in the answer book to represent these two inequalities.
Hence determine the feasible region and label it R . The times taken to produce each Celebration arrangement and each Party arrangement are 10 minutes and 4 minutes respectively. Lethna wishes to minimise the total time taken to produce the arrangements.
Write down the objective function, T , in terms of $x$ and $y$.
Use point testing to find the optimal number of each type of arrangement Lethna should produce, and find the total time she will take.

Edexcel D1 2013 January Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-8_752_1445_210_287} \captionsetup{labelformat=empty} \caption{Figure 7}

\end{figure} Figure 7 is the activity network relating to a building project. The activities are represented by the arcs. The number in brackets on each arc gives the time to complete the activity. Each activity requires one worker. The project must be completed in the shortest possible time.

Explain the reason for the dotted line from event 4 to event 6 as shown in Figure 7.
(2)
Complete Diagram 1 in the answer book to show the early event times and the late event times.
State the critical activities.
Calculate the total float for activity G. You must make the numbers you use in your calculation clear.
Draw a Gantt chart for this project on the grid provided in the answer book.
State the activities that must be happening at time 5.5
Use your Gantt chart to determine the minimum number of workers needed to complete the project in the minimum time. You must justify your answer.

Edexcel D1 2001 June Q1

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)

Edexcel D1 2001 June Q2

2. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-3_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.

Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
(4)
Draw your minimum spanning tree and find the least cost of the pipelines.
(3)

Edexcel D1 2001 June Q3

3. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-4_678_1151_425_399}

\end{figure} Figure 2 shows a new small business park. The vertices $A , B , C , D , E , F$ and $G$ represent the various buildings and the arcs represent footpaths. The number on an arc gives the length, in metres, of the path. The management wishes to inspect each path to make sure it is fit for use. Starting and finishing at $A$, solve the Route Inspection (Chinese Postman) problem for the network shown in Fig. 2 and hence determine the minimum distance thet needs to be walked in carrying out this inspection. Make your method and working clear and give a possible route of minimum length.

Edexcel D1 2001 June Q4

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

\captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-5_732_1238_446_391}

\end{figure} The weighted network shown in Fig. 3 models the area in which Bill lives. Each vertex represents a town. The edges represent the roads between the towns. The weights are the lengths, in km , of the roads.

Use Dijkstra's algorithm to find the shortest route from Bill's home at $S$ to $T$. Complete all the boxes on the answer sheet and explain clearly how you determined the path of least weight from your labelling. Bill decides that on the way to $T$ he must visit a shop in town $E$.
Obtain his shortest route now, giving its length and explaining your method clearly.

Edexcel D1 2001 June Q5

5. $$90,50,55,40,20,35,30,25,45$$

Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass. Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are: $$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes. Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
Show how this is possible.

Edexcel D1 2001 June Q6

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

\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-7_602_1255_494_423}

\end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.

Explain why it is not possible to achieve a flow of 30 through the network from $S$ to $T$.
State the maximum flow along
1. $S A B T$
2. SCET.
Show these flows on Diagram 1 of the answer sheet.
Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from $S$ to $T$. Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
Indicate a maximum flow on Diagram 3.
Prove that your flow is maximal.

Edexcel D1 2001 June Q7

7. This question is to be answered on the sheet provided in the answer booklet. A chemical company makes 3 products $X , Y$ and $Z$. It wishes to maximise its profit $\pounds P$. The manager considers the limitations on the raw materials available and models the situation with the following Linear Programming problem. Maximise $$\begin{gathered} P = 3 x + 6 y + 4 z
x \quad + \quad z \leq 4
x + 4 y + 2 z \leq 6
x + y + 2 z \leq 12
x \geq 0 , \quad y \geq 0 , \quad z \geq 0 \end{gathered}$$ subject to
where $x , y$ and $z$ are the weights, in kg , of products $X , Y$ and $Z$ respectively.
A possible initial tableau is

Basic variable	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	1	0	1	1	0	0	4
$s$	1	4	2	0	1	0	6
$t$	1	1	2	0	0	1	12
$P$	- 3	- 6	- 4	0	0	0	0

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.

Edexcel D1 2002 June Q1

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.

Edexcel D1 2002 June Q2

2. While solving a maximizing linear programming problem, the following tableau was obtained.

Basic variable	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	0	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	0	1	0	1	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$.

Edexcel D1 2002 June Q3

3. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_483_401_489}

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

\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_478_401_1106}

\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]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
\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.

Edexcel D1 2002 June Q5

5. An algorithm is described by the flow chart below.
\includegraphics[max width=\textwidth, alt={}, center]{652477eb-87dc-4a5a-8514-c9be39986142-5_1590_1264_363_539}

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.

Edexcel D1 2002 June Q6

6. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-6_1083_1608_421_259}

\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.
(3)

Edexcel D1 2002 June Q7

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]{652477eb-87dc-4a5a-8514-c9be39986142-7_719_1170_590_438}

\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 2002 June 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.
(3) 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$.
(1) 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).

Edexcel D1 2003 June Q1

Six workers $A , B , C , D , E$ and $F$ are to be matched to six tasks $1,2,3,4,5$ and 6 .

The table below shows the tasks that each worker is able to do.

Worker	Tasks
$A$	$2,3,5$
$B$	$1,3,4,5$
$C$	2
$D$	3,6
$E$	$2,4,5$
$F$	1

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.
(5)

Edexcel D1 2003 June Q2

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]{9ca3e12a-63fa-49c9-91fc-eedfb024417a-2_684_1045_1653_488}

\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 .
(b) Determine the value of $x$, showing your working clearly.
(4)

Edexcel D1 2003 June Q3

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]{9ca3e12a-63fa-49c9-91fc-eedfb024417a-3_636_1219_482_358}

\end{figure} (b) Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using

Prim's algorithm,
Kruskal's algorithm.

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

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	1	0	1	1	0	0	4
\(s\)	1	4	2	0	1	0	6
\(t\)	1	1	2	0	0	1	12
\(P\)	- 3	- 6	- 4	0	0	0	0

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	0	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	0	1	0	1	1	11

Worker	Tasks
\(A\)	\(2,3,5\)
\(B\)	\(1,3,4,5\)
\(C\)	2
\(D\)	3,6
\(E\)	\(2,4,5\)
\(F\)	1

Questions — Edexcel D1 (480 questions)

Browse by module

Browse by board

Edexcel D1 2012 January Q7

Edexcel D1 2013 January Q1

Edexcel D1 2013 January Q2

Edexcel D1 2013 January Q3

Edexcel D1 2013 January Q4

Edexcel D1 2013 January Q5

Edexcel D1 2013 January Q6

Edexcel D1 2013 January Q7

Edexcel D1 2001 June Q1

Edexcel D1 2001 June Q2

Edexcel D1 2001 June Q3

Edexcel D1 2001 June Q4

Edexcel D1 2001 June Q5

Edexcel D1 2001 June Q6

Edexcel D1 2001 June Q7

Edexcel D1 2002 June Q1

Edexcel D1 2002 June Q2

Edexcel D1 2002 June Q3

Edexcel D1 2002 June Q5

Edexcel D1 2002 June Q6

Edexcel D1 2002 June Q7

Edexcel D1 2002 June Q8

Edexcel D1 2003 June Q1

Edexcel D1 2003 June Q2

Edexcel D1 2003 June Q3