Questions - Edexcel D1 - A-Level Maths

Explain what is meant by the term 'path'.
(2) Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
(6) On a particular day, Tomek needs to travel from G to J via A.
Find the shortest route from G to J via A , and find its length.
(3) The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
Use an appropriate 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.
(5)
Write down a possible shortest inspection route.
(1)

Edexcel D1 2016 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-07_773_1353_226_372} \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 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.
State the critical activities.
Calculate the maximum number of days by which activity E could be delayed without lengthening the completion time of the project. You must make the numbers used 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.
Draw a cascade (Gantt) chart for this project on the grid provided in the answer book.

Edexcel D1 2016 June Q7

7. A theatre company is planning to sell two types of ticket, standard and premier. The theatre company has completed some market research and has used this to form the following constraints.

They will sell at most 450 tickets.
They will sell at least three times as many standard tickets as premier tickets.
At most $85 \%$ of all the tickets sold will be standard.

The theatre wants to maximise its profit. The profit on each standard ticket sold is $\pounds 5$ and the profit on each premier ticket sold is $\pounds 8$
Let $x$ represent the number of standard tickets sold and $y$ represent the number of premier tickets sold. 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 2017 June Q1

1. $$\begin{array} { l l l l l l l l l l l } 2.5 & 0.9 & 3.1 & 1.4 & 1.5 & 2.0 & 1.9 & 1.2 & 0.3 & 0.4 & 3.9 \end{array}$$ The numbers in the list are the lengths, in metres, of eleven pieces of wood. They are to be cut from planks of wood of length 5 metres. You should ignore wastage due to cutting.

Calculate a lower bound for the number of planks needed. You must make your method clear.
Use the first-fit bin packing algorithm to determine how these pieces could be cut from 5 metre planks.
Carry out a quick sort to produce a list of the lengths 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 these pieces could be cut from 5 metre planks.

Edexcel D1 2017 June Q2

	S	A	B	C	D	E	F	G
S	-	150	225	275	135	200	280	255
A	150	-	265	300	185	170	385	315
B	225	265	-	245	190	155	215	300
C	275	300	245	-	250	310	280	275
D	135	185	190	250	-	145	205	270
E	200	170	155	310	145	-	220	380
F	280	385	215	280	205	220	-	250
G	255	315	300	275	270	380	250	-

The table shows the costs, in pounds, of connecting seven computer terminals, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G, to a server, S.

Use Prim's algorithm, starting at S , to find the minimum spanning tree for this table of costs. 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 minimum cost, in pounds, of connecting the seven computer terminals to the server.
Explain why it is not necessary to check for cycles when using Prim's algorithm.

Edexcel D1 2017 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_604_506_239_406} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_608_511_242_1146} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.

Write down the technical name given to the type of graph shown in Figure 1.
(1) Figure 2 shows an initial matching.
Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
State a different complete matching from the one found in (b).
By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.

Edexcel D1 2017 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-05_739_1490_239_276} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} A project is modelled by the activity network shown in Figure 3. 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.
Determine the critical activities and the length of the critical path.
Calculate the total float for activity D. You must make the numbers you use in your calculation clear.
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 times and activities.

Edexcel D1 2017 June Q5

5. A school awards two types of prize, junior and senior. The school decides that it will award at least 25 junior prizes and at most 60 senior prizes.
Let $x$ be the number of junior prizes that the school awards and let $y$ be the number of senior prizes that the school awards.

Write down two inequalities to model these constraints.
(2) Two further constraints are $$\begin{aligned} & 2 x + 5 y \geqslant 250
& 5 x - 3 y \leqslant 150 \end{aligned}$$
Add lines and shading to Diagram 1 in the answer book to represent all four of these constraints. Hence determine the feasible region and label it $R$. The cost of a senior prize is three times the cost of a junior prize. The school wishes to minimise the cost of the prizes.
State the objective function, giving your answer in terms of $x$ and $y$.
Determine the exact coordinates of the vertices of the feasible region. Hence use the vertex method to find the number of junior prizes and the number of senior prizes that the school should award. You should make your working clear.

Edexcel D1 2017 June Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-08_1031_1502_242_333} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} \section*{[The total weight of the network is 223]} Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.

Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length. On a particular day, Pamela must include C in her route.
Find the shortest route from A to B that includes C , and state its length.
(2) Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
Write down a possible route, and calculate its length. You must make your calculation clear. Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).

Edexcel D1 2017 June Q7

7. Draw the activity network described in this precedence table, using activity on arc and dummies only where necessary.

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

Edexcel D1 2018 June Q1

1. $$\begin{aligned} & \text { Kerry (K) }
& \text { Nikki (N) }
& \text { Violet (V) }
& \text { Dev (D) }
& \text { Henri (H) }
& \text { Leslie (L) }
& \text { Enlai (E) }
& \text { Sylvester (S) }
& \text { Joan (J) } \end{aligned}$$ A binary search is to be performed on the names in the list above to locate the name Leslie.

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. You should state the name of the algorithm you use and show the list after each complete iteration.
Use the binary search algorithm to locate the name Leslie in the altered list you obtained in (b). You must make your method clear. The binary search algorithm is to be used to search for a name in an alphabetical list of 727 names.
Find the maximum number of iterations needed. You should justify your answer.

Edexcel D1 2018 June Q2

2. (a) Define the terms

alternating path,
complete matching.
(4) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098} \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.
(b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.
(3)
(c) Explain why it is not possible to find a complete matching.
(1) Worker C has task 1 added to his possible allocations.
(d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.

Edexcel D1 2018 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_595_1269_207_397} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} Figure 3 shows a graph G that contains $17 \operatorname { arcs }$ and 8 vertices.

State how many arcs there are in a spanning tree for G .
(1)
Explain why a path on G cannot contain 10 vertices.
(2)
Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.
(1) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 shows a weighted graph.
Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.
(3)
State the weight of the minimum spanning tree.
(1)

Edexcel D1 2018 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-05_876_1353_230_354} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} [The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.

Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. On Monday, Mandeep must travel from D to H via A.
Find the shortest time needed to travel from D to H via A . State the quickest route. On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
Write down a possible route, giving its duration. On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.

Edexcel D1 2018 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-06_630_1237_189_412} \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 hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

Complete the precedence table in the answer book.
Complete Diagram 1 in the answer book to show the early event times and late event times.
State the minimum project completion time and list the critical activities.
Calculate the maximum number of hours by which activity E could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used 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.
(3) Before the project begins it becomes apparent that activity E will require an additional 6 hours to complete. The project is still to be completed in the shortest possible time and the time to complete all other activities is unchanged.
State the new minimum project completion time and list the new critical activities.

Edexcel D1 2019 June Q1

	A	B	C	D	E	F
A	-	73	56	27	38	48
B	73	-	58	59	43	34
C	56	58	-	46	38	42
D	27	59	46	-	25	32
E	38	43	38	25	-	21
F	48	34	42	32	21	-

The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.

Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.

Edexcel D1 2019 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-03_892_871_203_596} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents a network of roads between ten villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }$ and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length. During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
Use Prim's algorithm, starting at A , to find a minimum connector for the five villages $\mathrm { A } , \mathrm { B }$, C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
Use Kruskal's algorithm to find a minimum connector for the five villages $\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }$ and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

Edexcel D1 2019 June Q3

3. Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below. $$\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$$

Calculate a lower bound for the number of tour groups required. You must make your method clear.
Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups. The above list of numbers is 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.
Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-04_712_1141_1363_463} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} [The total weight of the network is 227.2]
Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum's entrance at A .
Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.
Write down a possible shortest route, giving its length. Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.
State the finishing vertex of Sally's new route and calculate the difference in length between this new route and the route found in (f).

Edexcel D1 2019 June Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-06_677_1774_246_148} \captionsetup{labelformat=empty} \caption{Figure 3}

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

Explain the significance of the dummy activity
1. from event 2 to event 3
2. from event 6 to event 7
Complete Diagram 1 in the answer book to show the early event times and the late event times.
State the minimum project completion time and list the critical activities. The duration of activity H changes to $x$ hours.
Find, in terms of $x$ where necessary,
1. the possible new early event time for event 7
2. the possible new late event time for event 7 Given that the duration of activity H is such that the minimum project completion time is four hours greater than the time found in (c),
determine the value of $x$.

Edexcel D1 2019 June Q5

5. A clothing shop sells a particular brand of shirt, which comes in three different sizes, small, medium and large. Each month the manager of the shop orders $x$ small shirts, $y$ medium shirts and $z$ large shirts.
The manager forms constraints on the number of each size of shirts he will have to order.
One constraint is that for every 3 medium shirts he will order at least 5 large shirts.

Write down an inequality, with integer coefficients, to model this constraint. Two further constraints are $$x + y + z \geqslant 250 \text { and } x \leqslant 0.2 ( x + y + z )$$
Use these two constraints to write down statements, in context, that describe the number of different sizes of shirt the manager will order. The cost of each small shirt is $\pounds 6$, the cost of each medium shirt is $\pounds 10$ and the cost of each large shirt is $\pounds 15$ The manager must minimise the total cost of all the shirts he will order.
Write down the objective function. Initially, the manager decides to order exactly 150 large shirts.
1. Rewrite the constraints, as simplified inequalities with integer coefficients, in terms of $x$ and $y$ only.
2. 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 $V$.
Write down the number of each size of shirt the manager should order. Calculate the total cost of this order. Later, the manager decides to order exactly 50 small shirts and exactly 75 medium shirts instead of 150 large shirts.
Find the minimum number of large shirts the manager should order and show that this leads to a lower cost than the cost found in (f).

Edexcel D1 2019 June Q6

	$\mathbf { A }$	$\mathbf { B }$	$\mathbf { C }$	$\mathbf { D }$	$\mathbf { E }$	$\mathbf { F }$
$\mathbf { A }$	-	73	56	27	38	48
$\mathbf { B }$	73	-	58	59	43	34
$\mathbf { C }$	56	58	-	46	38	42
$\mathbf { D }$	27	59	46	-	25	32
$\mathbf { E }$	38	43	38	25	-	21
$\mathbf { F }$	48	34	42	32	21	-

\includegraphics[max width=\textwidth, alt={}]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-12_1374_1529_267_210}

\begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Key:} \includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-12_266_579_1720_1146}

\end{figure} Shortest route: $\_\_\_\_$ Length of shortest route: $\_\_\_\_$ \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-13_899_881_319_534} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} 3. $\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$ $\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$
\begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-18_711_1143_299_404} \captionsetup{labelformat=empty} \caption{Figure 2
[0pt] [The total weight of the network is 227.2]}

\end{figure} 4. \includegraphics[max width=\textwidth, alt={}, center]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_572_1454_1021_248} \section*{Key:}

\includegraphics[max width=\textwidth, alt={}]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_357_167_1610_1375}

\section*{Diagram 1} 5.

VIIIV SIHI NI III IM ION OC

VIIV SIHI NI JIHM ION OC

VEYV SIHI NI JIIIM ION OO

\includegraphics[max width=\textwidth, alt={}]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-23_840_1590_309_181}

\section*{Diagram 1} 6.

\includegraphics[max width=\textwidth, alt={}]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-28_2632_1830_121_121}

VIIIV SIHI NI JIHM 10 N OC

VIIV SIHI NI JIHM I ON OC

VI4V SIHI NI JIIYM ION OO

Edexcel D1 2020 June Q1

The table below shows the distances, in metres, between six vertices, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , in a network.

	A	B	C	D	E	F
A	-	18	23	17	28	19
B	18	-	20	11	-	24
C	23	20	-	-	25	13
D	17	11	-	-	-	22
E	28	-	25	-	-	-
F	19	24	13	22	-	-

Draw the weighted network using the vertices given in Diagram 1 in the answer book.
Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
Draw the minimum spanning tree on Diagram 2 in the answer book and state its total weight.

Edexcel D1 2020 June Q2

2. (a) (i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of $n$ numbers into ascending order.
(ii) Write down the circumstances under which a bubble sort stops. A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads
0.9
0.5
0.7
1.2
1.5
1.4
1.1
1.7
2.2
3.2
(b) Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.
(c) Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.
(d) Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4

Edexcel D1 2020 June Q3

3. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.

Edexcel D1 2020 June Q4

4. (a) Draw the activity network described by the precedence table below, using activity on arc. Use dummies only where necessary.
(5)

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

Given that K is a critical activity,
(b) state which other activities must also be critical.
(1) Given instead that all activities shown in the precedence table have the same duration and K is not necessarily critical,
(c) state the critical path for the network.
(1)

	S	A	B	C	D	E	F	G
S	-	150	225	275	135	200	280	255
A	150	-	265	300	185	170	385	315
B	225	265	-	245	190	155	215	300
C	275	300	245	-	250	310	280	275
D	135	185	190	250	-	145	205	270
E	200	170	155	310	145	-	220	380
F	280	385	215	280	205	220	-	250
G	255	315	300	275	270	380	250	-

	A	B	C	D	E	F
A	-	73	56	27	38	48
B	73	-	58	59	43	34
C	56	58	-	46	38	42
D	27	59	46	-	25	32
E	38	43	38	25	-	21
F	48	34	42	32	21	-

	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)
\(\mathbf { A }\)	-	73	56	27	38	48
\(\mathbf { B }\)	73	-	58	59	43	34
\(\mathbf { C }\)	56	58	-	46	38	42
\(\mathbf { D }\)	27	59	46	-	25	32
\(\mathbf { E }\)	38	43	38	25	-	21
\(\mathbf { F }\)	48	34	42	32	21	-

	A	B	C	D	E	F
A	-	18	23	17	28	19
B	18	-	20	11	-	24
C	23	20	-	-	25	13
D	17	11	-	-	-	22
E	28	-	25	-	-	-
F	19	24	13	22	-	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

	S	A	B	C	D	E	F	G
S	-	150	225	275	135	200	280	255
A	150	-	265	300	185	170	385	315
B	225	265	-	245	190	155	215	300
C	275	300	245	-	250	310	280	275
D	135	185	190	250	-	145	205	270
E	200	170	155	310	145	-	220	380
F	280	385	215	280	205	220	-	250
G	255	315	300	275	270	380	250	-

	A	B	C	D	E	F
A	-	73	56	27	38	48
B	73	-	58	59	43	34
C	56	58	-	46	38	42
D	27	59	46	-	25	32
E	38	43	38	25	-	21
F	48	34	42	32	21	-

	A	B	C	D	E	F
A	-	18	23	17	28	19
B	18	-	20	11	-	24
C	23	20	-	-	25	13
D	17	11	-	-	-	22
E	28	-	25	-	-	-
F	19	24	13	22	-	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

Questions — Edexcel D1 (480 questions)

Browse by module

Browse by board

Edexcel D1 2016 June Q5

Edexcel D1 2016 June Q6

Edexcel D1 2016 June Q7

Edexcel D1 2017 June Q1

Edexcel D1 2017 June Q2

Edexcel D1 2017 June Q3

Edexcel D1 2017 June Q4

Edexcel D1 2017 June Q5

Edexcel D1 2017 June Q6

Edexcel D1 2017 June Q7

Edexcel D1 2018 June Q1

Edexcel D1 2018 June Q2

Edexcel D1 2018 June Q3

Edexcel D1 2018 June Q4

Edexcel D1 2018 June Q5

Edexcel D1 2019 June Q1

Edexcel D1 2019 June Q2

Edexcel D1 2019 June Q3

Edexcel D1 2019 June Q4

Edexcel D1 2019 June Q5

Edexcel D1 2019 June Q6

Edexcel D1 2020 June Q1

Edexcel D1 2020 June Q2

Edexcel D1 2020 June Q3

Edexcel D1 2020 June Q4

	S	A	B	C	D	E	F	G
S	-	150	225	275	135	200	280	255
A	150	-	265	300	185	170	385	315
B	225	265	-	245	190	155	215	300
C	275	300	245	-	250	310	280	275
D	135	185	190	250	-	145	205	270
E	200	170	155	310	145	-	220	380
F	280	385	215	280	205	220	-	250
G	255	315	300	275	270	380	250	-

	A	B	C	D	E	F
A	-	73	56	27	38	48
B	73	-	58	59	43	34
C	56	58	-	46	38	42
D	27	59	46	-	25	32
E	38	43	38	25	-	21
F	48	34	42	32	21	-

	A	B	C	D	E	F
A	-	18	23	17	28	19
B	18	-	20	11	-	24
C	23	20	-	-	25	13
D	17	11	-	-	-	22
E	28	-	25	-	-	-
F	19	24	13	22	-	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-