Questions - Edexcel D1 - A-Level Maths

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.
(3)
The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

Edexcel D1 2013 June Q3

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-

The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

Use Prim's algorithm, starting at A , to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them.
Draw your minimum connector using the vertices given in Diagram 1 in the answer book.
Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table.
Use Kruskal's algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector.
State the minimum time needed, in days, to reconnect the six towns.

Edexcel D1 2013 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-5_780_1717_276_175} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T .

Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length. On a particular day, Liz must include F in her route.
Find the shortest path from S to T that includes F , and state its length.

Edexcel D1 2013 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-6_829_1547_257_259} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} \section*{[The total weight of the network is 344 miles]} Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway. Sophie needs to travel along each section to check that it is in good condition.
She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

Use the route inspection algorithm to 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. Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.
Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.

Edexcel D1 2013 June Q6

6. Harry wants to rent out boats at his local park. He can use linear programming to determine the number of each type of boat he should buy. Let $x$ be the number of 2 -seater boats and $y$ be the number of 4 -seater boats.
One of the constraints is $$x + y \geqslant 90$$

Explain what this constraint means in the context of the question. Another constraint is $$2 x \leqslant 3 y$$
Explain what this constraint means in the context of the question. A third constraint is $$y \leqslant x + 30$$
Represent these three constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R . Each 2 -seater boat costs $\pounds 100$ and each 4 -seater boat costs $\pounds 300$ to buy. Harry wishes to minimise the total cost of buying the boats.
Write down the objective function, C , in terms of $x$ and $y$.
Determine the number of each type of boat that Harry should buy. You must make your method clear and state the minimum cost.

Edexcel D1 2013 June Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-8_724_1730_241_167} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} \section*{[The sum of the duration of all activities is 172 days]} 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 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.
Calculate the total float for activity M. You must make the numbers you use in your calculation clear.
For each of the situations below, explain the effect that the delay would have on the project completion date.
1. A 2 day delay on the early start of activity P.
2. A 2 day delay on the early start of activity Q .
Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. Diagram 2 in the answer book shows a partly completed cascade chart for this project.
Complete the cascade chart.
Use your cascade chart to determine a second lower bound on the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities.
State which of the two lower bounds found in (d) and (f) is better. Give a reason for your answer.
(Total 17 marks)

Edexcel D1 2014 June Q1

1. $$\begin{array} { l l l l l l l l l } 31 & 10 & 38 & 45 & 19 & 47 & 35 & 28 & 12 \end{array}$$

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60
Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60
Determine whether the number of bins used in (c) is optimal. Give a reason for your answer.

Edexcel D1 2014 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-3_437_399_251_511} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-3_437_401_251_1151} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 1 shows the possible allocations of five employees, Ali (A), Campbell (C), Hugo (H), Janelle (J) and Polly (P), to five tasks 1, 2, 3, 4 and 5.

Explain why it is not possible to find a complete matching. It is decided that one of the employees should be trained so that a complete matching becomes possible. There are only enough funds for one employee to be trained. Two employees volunteer to undergo training. Janelle can be trained to do task 1 or Hugo can be trained to do task 5.
Decide which employee, Janelle or Hugo, should undergo training. Give a reason for your answer. You may now assume that the employee you identified in (b) has successfully undergone training. Figure 2 shows an initial matching.
Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state the complete matching.

Edexcel D1 2014 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-4_605_1378_248_370} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to traverse each road.

Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time taken.
(6) It is now necessary to include E in the route.
Determine the effect that this will have on the time taken for the journey. You must state your new quickest route and the time it takes.
(3)

Edexcel D1 2014 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-5_846_798_205_639} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 359 cm]}

\end{figure} Figure 4 represents the network of sensor wires used in a medical scanner. The number on each arc represents the length, in cm, of that section of wire. After production, each scanner is tested.
A machine will be programmed to inspect each section of wire.
It will travel along each arc of the network at least once, starting and finishing at A. Its route must be of minimum length.

Use the route inspection algorithm to find the length of a shortest inspection route. You must make your method and working clear. The machine will inspect 15 cm of wire per second.
Calculate the total time taken, in seconds, to test 120 scanners. It is now possible for the machine to start at one vertex and finish at a different vertex. An inspection route of minimum length is still required.
Explain why the machine should be programmed to start at a vertex with odd degree. Due to constraints at the factory, only B or D can be chosen as the starting point and there will also be a 2 second pause between tests.
Determine the new minimum total time now taken to test 120 scanners. You must state which vertex you are starting from and make your calculations clear.
(4)

Edexcel D1 2014 June Q5

5. A linear programming problem in $x$ and $y$ is described as follows. Maximise $\quad P = 2 x + 3 y$
subject to $$\begin{aligned} x & \geqslant 25
y & \geqslant 25
7 x + 8 y & \leqslant 840
4 y & \leqslant 5 x
5 y & \geqslant 3 x
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 the objective line method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
Calculate the exact coordinates of vertex V. Given that an integer solution is required,
determine the optimal solution with integer coordinates. You must make your method clear.

Edexcel D1 2014 June Q6

6. (i) Draw the activity network described in the precedence table below, using activity on arc and the minimum number of dummies.

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

(ii) Explain why each of your dummies is necessary.

Edexcel D1 2014 June Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-8_620_1221_251_427} \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 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.
Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. The project is to be completed in the minimum time using as few workers as possible.
Schedule the activities using Grid 1 in the answer book.

Edexcel D1 2014 June Q8

8. A manufacturer of frozen yoghurt is going to exhibit at a trade fair. He will take two types of frozen yoghurt, Banana Blast and Strawberry Scream. He will take a total of at least 1000 litres of yoghurt.
He wants at least $25 \%$ of the yoghurt to be Banana Blast. He also wants there to be at most half as much Banana Blast as Strawberry Scream. Each litre of Banana Blast costs $\pounds 3$ to produce and each litre of Strawberry Scream costs $\pounds 2$ to produce. The manufacturer wants to minimise his costs. Let $x$ represent the number of litres of Banana Blast and $y$ represent the number of litres of Strawberry Scream. 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 2014 June Q1

	Art	Biology	Chemistry	Drama	English	French	Graphics
Art (A)	-	61	93	73	50	48	42
Biology (B)	61	-	114	82	83	63	58
Chemistry (C)	93	114	-	59	94	77	88
Drama (D)	73	82	59	-	89	104	41
English (E)	50	83	94	89	-	91	75
French (F)	48	63	77	104	91	-	68
Graphics (G)	42	58	88	41	75	68	-

The table shows the travelling times, in seconds, to walk between seven departments in a college.

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

Edexcel D1 2014 June Q2

2. (a) Draw the activity network described in the precedence table below, using activity on arc and exactly two dummies.

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

(b) Explain why each of the two dummies is necessary.

Edexcel D1 2014 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{818ba207-5839-4698-aacb-75dab88b218f-04_821_1374_210_374} \captionsetup{labelformat=empty} \caption{Figure 1
[0pt] [The total weight of the network is 451]}

\end{figure} Figure 1 models a network of tracks in a forest that need to be inspected by a park ranger. The number on each arc is the length, in km, of that section of the forest track. Each track must be traversed at least once and the length of the inspection route must be minimised. The inspection route taken by the ranger must start and end at vertex A.

Use the route inspection algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
State the number of times that vertex J would appear in the inspection route. The landowner decides to build two huts, one hut at vertex K and the other hut at a different vertex. In future, the ranger will be able to start his inspection route at one hut and finish at the other. The inspection route must still traverse each track at least once.
Determine where the other hut should be built so that the length of the route is minimised. You must give reasons for your answer and state a possible route and its length.

Edexcel D1 2014 June Q4

4. Six pupils, Ashley (A), Fran (F), Jas (J), Ned (N), Peter (P) and Richard (R), each wish to learn a musical instrument. The school they attend has six spare instruments; a clarinet (C), a trumpet (T), a violin (V), a keyboard (K), a set of drums (D) and a guitar (G). The pupils are asked which instruments they would prefer and their preferences are given in the table above. It is decided that each pupil must learn a different instrument and each pupil needs to be allocated to exactly one of their preferred instruments.

Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of pupils to instruments. Initially Ashley, Fran, Jas and Richard are each allocated to their first preference.
Show this initial matching on Diagram 2 in the answer book.
Starting with the initial matching from (b), apply the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and give your improved matching.
Explain why a complete matching is not possible. Fran decides that as a third preference she would like to learn to play the guitar. Peter decides that as a second preference he would like to learn to play the drums.
Starting with the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.

Edexcel D1 2014 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{818ba207-5839-4698-aacb-75dab88b218f-06_851_1490_191_317} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Sharon is planning a road trip from Preston to York. Figure 2 shows the network of roads that she could take on her trip. The number on each arc is the length of the corresponding road in miles.

Use Dijkstra's algorithm to find the shortest route from Preston (P) to York (Y). State the shortest route and its length.
(6) Sharon has a friend, John, who lives in Manchester (M). Sharon decides to travel from Preston to York via Manchester so she can visit John. She wishes to minimise the length of her route.
State the new shortest route. Hence calculate the additional distance she must travel to visit John on this trip. You must make clear the numbers you use in your calculation.
(3)

Edexcel D1 2014 June Q6

6.
$\begin{array} { l l l l l l l l l } 24 & 14 & 8 & x & 19 & 25 & 6 & 17 & 9 \end{array}$ The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase is weighed inaccurately and the only information known about the unknown weight, $x \mathrm {~kg}$, of this suitcase is that $19 < x \leqslant 23$. The suitcases are to be transported in containers that can hold a maximum of 50 kilograms.

Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to containers.
Using the list provided, carry out a quick sort to produce a list of the weights in descending order. Show the result of each pass and identify your pivots clearly.
Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2 possible allocations of suitcases to containers. After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of the containers is full.
Calculate the possible integer values of $x$. You must show your working.

Edexcel D1 2014 June Q7

7. (a) In the context of critical path analysis, define the term 'total float'. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{818ba207-5839-4698-aacb-75dab88b218f-08_1310_1563_340_251} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 is the activity network for a building project. 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 exactly one worker. The project is to be completed in the shortest possible time.
(b) Complete Diagram 1 in the answer book to show the early event times and the late event times.
(c) State the critical activities.
(d) Calculate the maximum number of days by which activity G could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used in your calculation clear.
(e) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. The project is to be completed in the minimum time using as few workers as possible.
(f) Schedule the activities using Grid 1 in the answer book.

Edexcel D1 2014 June Q8

8. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{818ba207-5839-4698-aacb-75dab88b218f-10_1753_1362_260_315} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} The graph in Figure 4 is being used to solve a linear programming problem. The four constraints have been drawn on the graph and the rejected regions have been shaded out. The four vertices of the feasible region $R$ are labelled $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D .

Write down the constraints represented on the graph.
(2) The objective function, P , is given by $$\mathrm { P } = x + k y$$ where $k$ is a positive constant. The minimum value of the function P is given by the coordinates of vertex A and the maximum value of the function P is given by the coordinates of vertex D .
Find the range of possible values for $k$. You must make your method clear.
(Total 8 marks)

Edexcel D1 2015 June Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_476_319_434} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_474_319_1146} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} A delivery firm has six vans, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , available for six deliveries, $1,2,3,4,5$ and 6 . Each van must be assigned to just one delivery. The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching. A complete matching is required, starting from the given initial matching.

Explain why it is necessary to use the maximum matching algorithm twice. There are three possible alternating paths that start at either D or B . One of these is $$D - 2 = A - 3 = F - 6 = E - 5$$
Find the other two alternating paths.
List the improved matching generated by using the alternating path $$D - 2 = A - 3 = F - 6 = E - 5$$
Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching.

Edexcel D1 2015 June Q2

2. $$\begin{array} { l l l l l l l l l l } 18 & 29 & 48 & 9 & 42 & 31 & 37 & 24 & 27 & 41 \end{array}$$ The numbers above are Alan's batting scores for the first 10 cricket matches of the season.

Use a quick sort to sort this list of numbers into ascending order. You must make your pivots clear. Alan's batting scores for the final 10 cricket matches of the same season were
$\begin{array} { l l l l l l l l l l } 72 & 53 & 89 & 91 & 68 & 67 & 90 & 77 & 83 & 75 \end{array}$
Carry out a bubble sort on this second list of numbers to produce a list of these scores in ascending order. You need only give the state of the list after each pass. Alan's combined batting scores for the entire season were $$\begin{array} { l l l l l l l l l l l l l l l l l l l l } 9 & 18 & 24 & 27 & 29 & 31 & 37 & 41 & 42 & 48 & 53 & 67 & 68 & 72 & 75 & 77 & 83 & 89 & 90 & 91 \end{array}$$
Use the binary search algorithm to locate 68 in the combined list of 20 scores. You must make your method clear.

Edexcel D1 2015 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-4_901_894_228_612} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 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 J. State the shortest route and its length.
Explain how you determined the shortest route from your labelled diagram.
Find the shortest route from A to J via E and state its length.

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

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-

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

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-

Questions — Edexcel D1 (480 questions)

Browse by module

Browse by board

Edexcel D1 2013 June Q2

Edexcel D1 2013 June Q3

Edexcel D1 2013 June Q4

Edexcel D1 2013 June Q5

Edexcel D1 2013 June Q6

Edexcel D1 2013 June Q7

Edexcel D1 2014 June Q1

Edexcel D1 2014 June Q2

Edexcel D1 2014 June Q3

Edexcel D1 2014 June Q4

Edexcel D1 2014 June Q5

Edexcel D1 2014 June Q6

Edexcel D1 2014 June Q7

Edexcel D1 2014 June Q8

Edexcel D1 2014 June Q1

Edexcel D1 2014 June Q2

Edexcel D1 2014 June Q3

Edexcel D1 2014 June Q4

Edexcel D1 2014 June Q5

Edexcel D1 2014 June Q6

Edexcel D1 2014 June Q7

Edexcel D1 2014 June Q8

Edexcel D1 2015 June Q1

Edexcel D1 2015 June Q2

Edexcel D1 2015 June Q3

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-