Questions - Edexcel D1 - A-Level Maths

Use Dijkstra's algorithm to find the shortest time needed to travel from A to K . State the quickest route.
(6) On a particular day Oliver must travel from B to K via A.
Find a route of minimal time from B to K that includes A , and state its length.
(2) Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear.

Edexcel D1 2016 January Q5

5. A linear programming problem in $x$ and $y$ is described as follows. $$\begin{array} { l l } \text { Maximise } & \mathrm { P } = 5 x + 3 y
\text { subject to: } & x \geqslant 3
& x + y \leqslant 9
& 15 x + 22 y \leqslant 165
& 26 x - 50 y \leqslant 325 \end{array}$$

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 the objective line method to find the optimal vertex, V, of the feasible region. You must draw and label your objective line and label vertex V clearly.
Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V . The objective is now to minimise $5 x + 3 y$, where $x$ and $y$ are integers.
Write down the minimum value of $5 x + 3 y$ and the corresponding value of $x$ and corresponding value of $y$.

Edexcel D1 2016 January Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-7_664_1520_239_276} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} A project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.

Explain the significance of the dummy activity
1. from event 5 to event 6
2. from event 7 to event 9
Complete Diagram 1 in the answer book to show the early event times and the late event times.
State the minimum project completion time.
Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time. You must show your working.
On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project.
On Grid 2 in your answer book, construct a scheduling diagram to show that this project can be completed with three workers in just one more hour than the minimum project completion time.
(3)

Edexcel D1 2017 January Q1

Use the binary search algorithm to try to locate the name Hilbert in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage.

Edexcel D1 2017 January Q2

	A	B	C	D	E	F	G	H
A	-	27	51	32	29	23	47	40
B	27	-	24	35	20	42	33	28
C	51	24	-	37	43	31	26	34
D	32	35	37	-	39	45	44	30
E	29	20	43	39	-	38	45	55
F	23	42	31	45	38	-	53	45
G	47	33	26	44	45	53	-	39
H	40	28	34	30	55	45	39	-

The table represents a network that shows the average journey time, in minutes, between eight towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H .

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
State the weight of the minimum spanning tree.

Edexcel D1 2017 January Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_608_511_242_358} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_611_510_242_1201} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 1 shows the possible allocations of six workers, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , to six tasks, $1,2,3$, 4, 5 and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.

Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
Explain why it is not possible to find a complete matching. After training, task 1 is added to worker A's possible allocations.
Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.
(3)

Edexcel D1 2017 January Q4

4. $\begin{array} { l l l l l l l l l } 23 & 18 & 27 & 9 & 25 & 10 & 12 & 30 & 24 \end{array}$ The numbers in the list represent the weights, in kilograms, of nine suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 45 kilograms.

Calculate a lower bound for the number of containers that will be needed to transport the suitcases.
Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each complete pass.
Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers.
Explain why it is not possible to transport the suitcases using fewer containers than the number used in (d).

Edexcel D1 2017 January Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-06_897_1499_239_283} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} [The total weight of the network is 106.7]
Figure 3 models a network of cycle tracks that have to be inspected. The number on each arc represents the length, in km , of the corresponding track. Angela needs to travel along each cycle track at least once and wishes to minimise the length of her inspection route. She must start and finish at A.

Use an appropriate algorithm to find the tracks that will need to be traversed twice. You should make your method and working clear.
Find a route of minimum length, starting and finishing at A . State the length of your route. A new cycle track, AC, is under construction. It will be 15 km long. Angela will have to include this new track in her inspection route.
State the effect this new track will have on the total length of her route. Justify your answer.

Edexcel D1 2017 January Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-07_1052_1447_212_310} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} Figure 4 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Stieg wishes to minimise the time spent driving from his home at A , to his office at H . The amount of traffic on two of the roads leading into H varies each day, and so the length of time taken to drive along these roads is expressed in terms of $x$, where $x > 7$

Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H . State the length of each route, leaving your answer in terms of $x$ where necessary.
(7) On a particular day, the quickest route from A to H via G is 2 minutes quicker than the quickest route from A to H via E .
Calculate the value of $x$. You must make your method and working clear.

Edexcel D1 2017 January Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-08_1024_1495_226_276} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} A project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires exactly 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.
Explain what is meant by a critical path.
List the critical path for this network.
For each of the situations below, state the effect that the delay would have on the project completion date.
1. A 4-day delay during activity J.
2. A 4-day delay during activity M . The delays mentioned in (d) do not occur.
Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.

Edexcel D1 2017 January Q8

8. A shop sells three types of pen. These are ballpoint pens, rollerball pens and fountain pens. The shop manager knows that each week she should order

at least 50 pens in total
at least twice as many rollerball pens as fountain pens

In addition,

at most $60 \%$ of the pens she orders must be ballpoint pens
at least a third of the pens she orders must be rollerball pens

Each ballpoint pen costs $\pounds 2$, each rollerball pen costs $\pounds 3$ and each fountain pen costs $\pounds 5$
The shop manager wants to minimise her costs.
Let $x$ represent the number of ballpoint pens ordered, let $y$ represent the number of rollerball pens ordered and let $z$ represent the number of fountain pens ordered.

Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. The shop manager decides to order exactly 10 fountain pens. This reduces the problem to the following $$\begin{array} { l r } \text { Minimise } & P = 2 x + 3 y
\text { subject to } & x + y \geqslant 40
& 2 x - 3 y \leqslant 30
- x + 2 y \geqslant 10
& y \geqslant 20
& x \geqslant 0 \end{array}$$
Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R .
Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V.
Write down the number of each type of pen that the shop manager should order. Calculate the cost of this order.
(Total $\mathbf { 1 6 }$ marks)

Edexcel D1 2018 January Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-02_611_515_333_397} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-02_611_515_333_1146} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure}

Define the term 'bipartite graph'. Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, $1,2,3$, 4, 5 and 6 Figure 2 shows an initial matching.
Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.

Edexcel D1 2018 January Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-03_1031_1571_226_246} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} The network in Figure 3 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. Each activity requires exactly one worker. The early event times and late event times are shown at each vertex. Given that the total float on activity B is 2 days and the total float on activity F is also 2 days,

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

Edexcel D1 2018 January Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-04_1059_1424_228_317} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.

Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
Find a route of minimal length that goes from D to H via A and state its length.
Use Prim's algorithm, starting at E , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
Find the length, in kilometres, of your minimum spanning tree.

Edexcel D1 2018 January Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-05_1198_908_226_584} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} Figure 5 shows the constraints of a linear programming problem in $x$ and $y$, where $R$ is the feasible region.

Determine the inequalities that define the feasible region.
Find the exact coordinates of the vertices of the feasible region. The objective is to maximise $P = 2 x + 3 y$.
Use point testing at each vertex to find the optimal vertex, $V$, of the feasible region and state the corresponding value of $P$ at $V$.
(3) The objective is changed to maximise $Q = 2 x + k y$, where $k$ is a constant.
Find the range of values of $k$ for which the vertex identified in (c) is still optimal.
(2)

Edexcel D1 2018 January Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-06_725_1718_242_169} \captionsetup{labelformat=empty} \caption{Figure 6
[0pt] [The total weight of the network is 601]}

\end{figure} Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in metres, of the corresponding footpath. An inspection route of minimum length that traverses each footpath at least once needs to be found.

Write down the nodes at which the route will start and finish.
(1) It is now decided to start the inspection route at B and finish the inspection route at D . A route of minimum length that traverses each footpath at least once needs to be found.
By considering the pairings of all relevant nodes find the arcs that will need to be traversed twice. You must make your method and working clear.
Write down a possible shortest inspection route, giving its length.

Edexcel D1 2018 January Q6

6. $$\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}$$ The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.

Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting. The list of numbers above is to be sorted into ascending order.
Starting at the left-hand end of the list, after three passes of the bubble sort, the list is $$\begin{array} { l l l l l l l l l l } 11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60 \end{array}$$
1. Write down the list that results at the end of the fourth pass.
2. Write down the number of comparisons and swaps performed during the fourth pass. The original list of numbers is now to be sorted into descending order.
Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.

Edexcel D1 2018 January Q7

7. Emily is planning to sell three types of milkshake, strawberry, vanilla and chocolate. Emily has completed some market research and has used this to form the following constraints on the number of milkshakes that she will sell each week.

She will sell fewer than 200 non-vanilla milkshakes in total.
She will sell at most 2.5 times as many strawberry milkshakes as vanilla milkshakes.
At most, $75 \%$ of the milkshakes that she will sell will be vanilla.

The profit on each strawberry milkshake sold is $\pounds 0.75$, the profit on each vanilla milkshake sold is $\pounds 1.20$ and the profit on each chocolate milkshake sold is $\pounds 1.45$ Emily wants to maximise her profit.
Let $x$ represent the number of strawberry milkshakes sold, let $y$ represent the number of vanilla milkshakes sold and let $z$ represent the number of chocolate milkshakes sold.

Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. In week 1, Emily sells 100 strawberry milkshakes and 25 chocolate milkshakes.
Calculate the maximum possible profit and minimum possible profit, in pounds, for the sale of all milkshakes in week 1. You must show your working.

Edexcel D1 2018 January Q8

\includegraphics[max width=\textwidth, alt={}]{e0c89aba-9d2e-469b-8635-d513df0b65a4-19_2261_50_315_33}

\begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-19_862_1422_196_258} \captionsetup{labelformat=empty} \caption{Figure 4}

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

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-20_1196_899_251_529} \captionsetup{labelformat=empty} \caption{Figure 5}

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

\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-24_871_1536_210_205} \captionsetup{labelformat=empty} \caption{Figure 6
[0pt] [The total weight of the network is 601]}

\end{figure} 6.
$\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}$ 7.

\includegraphics[max width=\textwidth, alt={}]{e0c89aba-9d2e-469b-8635-d513df0b65a4-32_2636_1825_119_122}

Edexcel D1 2019 January Q1

(a) Define the term 'bipartite graph'.

Six workers, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { 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,4
$B$	5
$C$	3,4
$D$	2
$E$	$4,5,6$
$F$	1,6

(b) Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocation of workers to tasks.
(1) Initially, workers $\mathrm { A } , \mathrm { C } , \mathrm { E }$ and F are allocated to tasks 2, 4, 5 and 6 respectively.
(c) Starting from the given initial matching, apply the maximum matching algorithm to obtain a complete matching. You must state the alternating paths that you use, and state your improved matching after each iteration.

Edexcel D1 2019 January Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-03_848_1435_244_315} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents a network of roads. The number on each arc is the length, in km , of the corresponding road.

Use Dijkstra's algorithm to find the shortest route from A to L. State the shortest route and its length.
Explain how you determined the shortest route from your labelled diagram.
Find the length of the shortest route from J to F via A , and state your route.

Edexcel D1 2019 January Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-04_848_1394_210_331} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding 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 the late event times.
State the critical activities.
Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

Edexcel D1 2019 January Q4

4. $$\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}$$ The numbers in the list above represent the weights, in kilograms, of 11 boxes. John must transport all the boxes using his van. You may assume the van has sufficient space for any combination of boxes. Each van load of boxes must weigh at most 475 kg .

Calculate a lower bound for the number of van loads needed to transport all 11 boxes.
Use the first-fit bin packing algorithm to show how the boxes could be put into van loads. State the number of van loads needed according to this solution.
Carry out a quick sort on the numbers in the list given above to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly.
Use the first-fit decreasing bin packing algorithm on your ordered list to show how the boxes could be put into van loads. State the number of van loads needed according to this solution. Due to volume restrictions, the van cannot transport more than three boxes at any one time.
Show how the boxes could now be put into the minimum number of van loads.

Edexcel D1 2019 January Q5

Activity	Immediately preceding activities
A	-
B	-
C	-
D	B
E	A, D
F	B
G	B, C
H	E, F, G
I	F, G
J	G
K	H, I

Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies.
(5) Given that D is a critical activity,
state which other activities must also be critical.
(1)

Edexcel D1 2019 January Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-07_608_1468_194_296} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} [The weight of the network is $20 x + 17$ ]

Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
During rush hour one day $x = 9$
1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
2. Calculate the weight of the minimum spanning tree. You are now given that $x > 3$ A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
Determine the value of $x$, showing your working clearly.

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

	A	B	C	D	E	F	G	H
A	-	27	51	32	29	23	47	40
B	27	-	24	35	20	42	33	28
C	51	24	-	37	43	31	26	34
D	32	35	37	-	39	45	44	30
E	29	20	43	39	-	38	45	55
F	23	42	31	45	38	-	53	45
G	47	33	26	44	45	53	-	39
H	40	28	34	30	55	45	39	-

	A	B	C	D	E	F	G	H
A	-	27	51	32	29	23	47	40
B	27	-	24	35	20	42	33	28
C	51	24	-	37	43	31	26	34
D	32	35	37	-	39	45	44	30
E	29	20	43	39	-	38	45	55
F	23	42	31	45	38	-	53	45
G	47	33	26	44	45	53	-	39
H	40	28	34	30	55	45	39	-

Questions — Edexcel D1 (480 questions)

Browse by module

Browse by board

Edexcel D1 2016 January Q4

Edexcel D1 2016 January Q5

Edexcel D1 2016 January Q6

Edexcel D1 2017 January Q1

Edexcel D1 2017 January Q2

Edexcel D1 2017 January Q3

Edexcel D1 2017 January Q4

Edexcel D1 2017 January Q5

Edexcel D1 2017 January Q6

Edexcel D1 2017 January Q7

Edexcel D1 2017 January Q8

Edexcel D1 2018 January Q1

Edexcel D1 2018 January Q2

Edexcel D1 2018 January Q3

Edexcel D1 2018 January Q4

Edexcel D1 2018 January Q5

Edexcel D1 2018 January Q6

Edexcel D1 2018 January Q7

Edexcel D1 2018 January Q8

Edexcel D1 2019 January Q1

Edexcel D1 2019 January Q2

Edexcel D1 2019 January Q3

Edexcel D1 2019 January Q4

Edexcel D1 2019 January Q5

Edexcel D1 2019 January Q6

	A	B	C	D	E	F	G	H
A	-	27	51	32	29	23	47	40
B	27	-	24	35	20	42	33	28
C	51	24	-	37	43	31	26	34
D	32	35	37	-	39	45	44	30
E	29	20	43	39	-	38	45	55
F	23	42	31	45	38	-	53	45
G	47	33	26	44	45	53	-	39
H	40	28	34	30	55	45	39	-