Questions D1 - A-Level Maths

OCR MEI D1 2006 January Q6

16 marks Easy -1.2

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

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

Edexcel D1 2014 January Q1

8 marks Easy -1.3

1. 11
17
10
14
8
13
6
4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.

Edexcel D1 2014 January Q2

10 marks Moderate -0.5

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
State the new minimum cost of connecting the nine buildings.

Edexcel D1 2014 January Q4

8 marks Moderate -0.8

4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
  2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
4. State the new minimum cost of connecting the nine buildings.
  3. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
  \end{figure} \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
  \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
5. Define the term 'matching'.
  (2)
6. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
  (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
7. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
  (3)
  4. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
  [0pt] [The total weight of the network is 367 metres]}
  \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
  The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
8. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
9. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
10. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.

Edexcel D1 2014 January Q11

Moderate -0.5

11
17
10
14
8

Edexcel D1 2014 January Q14

Moderate -0.5

14
8
13
6
4

Edexcel D1 2014 January Q17

Easy -1.8

17
10
14
8
13
6
4
15
7

Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
  2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
4. State the new minimum cost of connecting the nine buildings.
  3. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
  \end{figure} \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
  \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
5. Define the term 'matching'.
  (2)
6. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
  (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
7. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
  (3)
  4. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
  [0pt] [The total weight of the network is 367 metres]}
  \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
  The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
8. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
9. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
10. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
  5. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
  \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
11. Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
12. Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
  (3)
  6. A linear programming problem in $x$ and $y$ is described as follows. Minimise $\quad C = 2 x + 5 y$ subject to $$\begin{aligned} x + y & \geqslant 500 \\ 5 x + 4 y & \geqslant 4000 \\ y & \leqslant 2 x \\ y & \geqslant x - 250 \\ x , y & \geqslant 0 \end{aligned}$$
13. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
14. Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to $x + y \geqslant k$ for some value of $k$.
15. Determine the greatest value of $k$ for which P is still the optimal point.
  7. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \captionsetup{labelformat=empty} \caption{Figure 6}
  \end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
16. Complete Diagram 1 in the answer book to show the early event times and late event times.
17. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
18. Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
19. Schedule the activities, using Grid 2 in the answer book.
  8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
  Pack B contains 30 posters and 50 flyers.
  The charity must send out at least 15000 flyers.
  The charity wants between $40 \%$ and $60 \%$ of the total packs produced to be Pack As.
  Posters cost 15p each and flyers cost 3p each.
  The charity wishes to minimise its costs.
  Let $x$ represent the number of Pack As produced, and $y$ represent the number of Pack Bs produced.
  Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
  You should not attempt to solve the problem.
  (Total 6 marks)

Edexcel D1 Q4

Moderate -0.5

4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed $( A )$ - Monday and Wednesday;
Miss Brown ( $B$ ) - Monday, Wednesday and Friday;
Ms. Clough ( $C$ ) - Monday;
Mr. Dingle ( $D$ ) - Tuesday, Wednesday and Thursday;
Mrs. Evans $( E )$ - Wednesday and Thursday.
The manager initially suggests that $A$ might work on Monday, $B$ on Wednesday and $D$ on Thursday.

Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
(2 marks)
Obtain an alternating path, starting at $C$, and use this to improve the initial matching.
(3 marks)
Find another alternating path and hence obtain a complete matching.
(3 marks)

Edexcel D1 Q5

Standard +0.3

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

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_352_904_450_287} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.

Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
Hence determine the critical activities and the length of the critical path. Each activity requires one worker. The project is to be completed in the minimum time.
Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities.
(5 marks)

Edexcel D1 Q6

Moderate -0.3

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

\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_469_844_422_1731} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

State the maximum flow along
1. SAET,
2. SBDT,
3. SCFT.
  (3 marks)
Show these maximum flows on Diagram 1 on the answer sheet.
(1 mark)
Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
(6 marks)
Indicate a maximum flow on Diagram 3.
(2 marks)
Prove that your flow is maximal.
(2 marks)

Edexcel D1 Q7

Moderate -0.8

7. A tailor makes two types of garment, $A$ and $B$. He has available $70 \mathrm {~m} ^ { 2 }$ of cotton fabric and $90 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $A$ requires $1 \mathrm {~m} ^ { 2 }$ of cotton fabric and $3 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $B$ requires $2 \mathrm {~m} ^ { 2 }$ of each fabric. The tailor makes $x$ garments of type $A$ and $y$ garments of type $B$.

Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
The tailor sells type $A$ for $\pounds 30$ and type $B$ for $\pounds 40$. All garments made are sold. The tailor wishes to maximise his total income.
Set up an initial Simplex tableau for this problem.
(3 marks)
Solve the problem using the Simplex algorithm.
(8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure}
Obtain the coordinates of the points A, $C$ and $D$.
Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
(3 marks) Answer Book (AB12)
Graph Paper (ASG2) Items included with question papers Answer booklet

Edexcel D1 Q4

Moderate -0.5

4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; } \\ & \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; } \\ & \text { Ms. Clough } ( C ) \text { - Monday; } \\ & \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; } \\ & \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ The manager initially suggests that $A$ might work on Monday, $B$ on Wednesday and $D$ on Thursday.

Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
(2 marks)
Obtain an alternating path, starting at $C$, and use this to improve the initial matching.
Find another alternating path and hence obtain a complete matching.
(3 marks)

Edexcel D1 Q5

Standard +0.3

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

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-006_542_1389_483_352} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows the activity network used to model a small building project. The activities are represented by the edges and the number in brackets on each edge represents the time, in hours, taken to complete that activity.

Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
(6 marks)
Hence determine the critical activities and the length of the critical path.
(2 marks)
Each activity requires one worker. The project is to be completed in the minimum time.
Schedule the activities for the minimum number of workers using the time line on the answer sheet. Ensure that you make clear the order in which each worker undertakes his activities.
(5 marks)

Edexcel D1 Q6

Standard +0.3

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

\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-007_732_1308_433_388} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

State the maximum flow along
1. SAET,
2. SBDT,
3. SCFT.
  (3 marks)
Show these maximum flows on Diagram 1 on the answer sheet.
Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
Indicate a maximum flow on Diagram 3.
Prove that your flow is maximal.

Edexcel D1 Q7

Moderate -0.5

7. A tailor makes two types of garment, $A$ and $B$. He has available $70 \mathrm {~m} ^ { 2 }$ of cotton fabric and $90 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $A$ requires $1 \mathrm {~m} ^ { 2 }$ of cotton fabric and $3 \mathrm {~m} ^ { 2 }$ of woollen fabric. Garment $B$ requires $2 \mathrm {~m} ^ { 2 }$ of each fabric. The tailor makes $x$ garments of type $A$ and $y$ garments of type $B$.

Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ The tailor sells type $A$ for $\pounds 30$ and type $B$ for $\pounds 40$. All garments made are sold. The tailor wishes to maximise his total income.
Set up an initial Simplex tableau for this problem.
Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure}
Obtain the coordinates of the points A, $C$ and $D$.
Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
Final tree
(b) Minimum total length of cable
Question 4 to be answered on this page
(a) $A$
Question 5 to be answered on this page
Key
(a) Early
Time
Late
Time \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201} $F ( 3 )$ \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
H(4) K(6)
(b) Critical activities
Length of critical path $\_\_\_\_$ (c) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
(a) (i) SAET $\_\_\_\_$ (ii) SBDT $\_\_\_\_$ (iii) SCFT $\_\_\_\_$ (b) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}
\end{figure} (c) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}
\end{figure} Flow augmenting routes
(d) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}
\end{figure} (e) $\_\_\_\_$

Edexcel D1 Q10

Easy -1.2

10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

Calculate a lower bound for the number of rolls needed.
(2)
Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
Use full bins to find an optimal solution that uses the minimum number of rolls.

Edexcel D1 Q12

Easy -1.2

12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

Calculate a lower bound for the number of rolls needed.
(2)
Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
Use full bins to find an optimal solution that uses the minimum number of rolls.

Edexcel D1 Q13

Moderate -1.0

13
16
5
8
2
15
12
10 6.

\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-558_2226_1632_322_157}

\section*{Diagram 1}

Edexcel D1 2009 June Q1

5 marks Easy -1.3

1.

	$\mathbf { A }$	$\mathbf { B }$	$\mathbf { C }$	$\mathbf { D }$	$\mathbf { E }$	$\mathbf { F }$
$\mathbf { A }$	-	135	180	70	95	225
$\mathbf { B }$	135	-	215	125	205	240
$\mathbf { C }$	180	215	-	150	165	155
$\mathbf { D }$	70	125	150	-	100	195
$\mathbf { E }$	95	205	165	100	-	215
$\mathbf { F }$	225	240	155	195	215	-

The table shows the lengths, in km, of potential rail routes between six towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F .

Use Prim's algorithm, starting from A , to find a minimum spanning tree for this table. You must list the arcs that form your tree in the order that they are selected.
Draw your tree using the vertices given in Diagram 1 in the answer book.
State the total weight of your tree.

Edexcel D1 2009 June Q2

9 marks Moderate -0.8

2.
32
45
17
23
38
28
16
9
12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

Calculate a lower bound for the number of rolls needed.
Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
Use full bins to find an optimal solution that uses the minimum number of rolls.

Edexcel D1 2009 June Q3

7 marks Moderate -0.8

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_755_624_283_283} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_750_620_285_1146} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
(3)

Edexcel D1 2009 June Q4

9 marks Easy -1.8

4. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

Use the quick sort algorithm to sort the above list into alphabetical order.
(5)
Use the binary search algorithm to locate the name Louis.

Edexcel D1 2009 June Q5

9 marks Standard +0.3

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-5_940_1419_262_322} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} [The total weight of the network is 625 m ]
Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.

Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
(6) The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.
Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
(3)

Edexcel D1 2009 June Q6

7 marks Moderate -0.8

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-6_899_1493_262_285} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road.

Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
(6)
State the shortest distance from A to G .
(1)

Edexcel D1 2009 June Q7

14 marks Easy -1.3

7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes $x$ large baskets and $y$ small baskets. Each large basket costs $\pounds 7$ to make and each small basket costs $\pounds 5$ to make. Rose has $\pounds 350$ she can spend on making the baskets.

Write down an inequality, in terms of $x$ and $y$, to model this constraint.
(2) Two further constraints are $$\begin{aligned} & y \leqslant 20 \text { and } \\ & y \leqslant 4 x \end{aligned}$$
Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
On the grid provided, show these three constraints and $x \geqslant 0 , y \geqslant 0$. Hence label the feasible region, R. Rose makes a profit of $\pounds 2$ on each large basket and $\pounds 3$ on each small basket. Rose wishes to maximise her profit, £P.
Write down the objective function.
Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.

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

Questions D1 (932 questions)

Browse by module

Browse by board

OCR MEI D1 2006 January Q6

Edexcel D1 2014 January Q1

Edexcel D1 2014 January Q2

Edexcel D1 2014 January Q4

Edexcel D1 2014 January Q11

Edexcel D1 2014 January Q14

Edexcel D1 2014 January Q17

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q4

Edexcel D1 Q5

Edexcel D1 Q6

Edexcel D1 Q7

Edexcel D1 Q10

Edexcel D1 Q12

Edexcel D1 Q13

Edexcel D1 2009 June Q1

Edexcel D1 2009 June Q2

Edexcel D1 2009 June Q3

Edexcel D1 2009 June Q4

Edexcel D1 2009 June Q5

Edexcel D1 2009 June Q6

Edexcel D1 2009 June Q7

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

	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)
\(\mathbf { A }\)	-	135	180	70	95	225
\(\mathbf { B }\)	135	-	215	125	205	240
\(\mathbf { C }\)	180	215	-	150	165	155
\(\mathbf { D }\)	70	125	150	-	100	195
\(\mathbf { E }\)	95	205	165	100	-	215
\(\mathbf { F }\)	225	240	155	195	215	-