Questions D1 - A-Level Maths

Edexcel D1 2009 June Q17

Easy -1.2

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.
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.
1. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
2. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
3. 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)
  4. Miri
  Jessie
  Edward
  Katie
  Hegg
  Beth
  Louis
  Philip
  Natsuko
  Dylan
4. Use the quick sort algorithm to sort the above list into alphabetical order.
  (5)
5. Use the binary search algorithm to locate the name Louis.
  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.
6. 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.
7. 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)
  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.
8. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
  (6)
9. State the shortest distance from A to G .
  (1)
  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.
10. 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}$$
11. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
12. 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.
13. Write down the objective function.
14. Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.
  8. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-8_809_1541_283_262} \captionsetup{labelformat=empty} \caption{Figure 5}
  \end{figure} A construction 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.
15. Complete Diagram 2 in the answer book, showing the early and late event times.
16. State the critical activities.
17. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
18. On the grid provided, draw a cascade (Gantt) chart for this project. An inspector visits the project at 1 pm on days 16 and 31 to check the progress of the work.
19. Given that the project is on schedule, which activities must be happening on each of these days?

Edexcel D1 2011 June Q1

9 marks Moderate -0.5

1.

Jenny

Edexcel D1 2011 June Q10

Easy -1.8

10. & Freya
A binary search is to be performed on the names in the list above to locate the name Kim.

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, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-3_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure}
1. Define the terms
  1. tree,
  2. minimum spanning tree.
    (3)
  3. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 1. 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 spanning tree.
    (3)
  4. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
2. State whether your minimum spanning tree is unique. Justify your answer.
  (1)
  3. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-4_1492_1298_210_379} \captionsetup{labelformat=empty} \caption{Figure 2}
  \end{figure} Figure 2 shows the constraints of a linear programming problem in $x$ and $y$, where $R$ is the feasible region.
3. Write down the inequalities that form region $R$. The objective is to maximise $3 x + y$.
4. Find the optimal values of $x$ and $y$. You must make your method clear.
5. Obtain the optimal value of the objective function. Given that integer values of $x$ and $y$ are now required,
6. write down the optimal values of $x$ and $y$.
  4. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
  \end{figure} \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_620_582_287_1098} \captionsetup{labelformat=empty} \caption{Figure 4}
  \end{figure} Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching.
  There are three possible alternating paths that start at A .
  One of them is $$A - 3 = R - 4 = C - 5$$
7. Find the other two alternating paths that start at A .
8. List the improved matching generated by using the alternating path $\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5$.
9. Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.
  5. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-6_835_913_219_575} \captionsetup{labelformat=empty} \caption{Figure 5
  [0pt] [The total weight of the network is 98 km ]}
  \end{figure} Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.
10. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
11. Write down a possible shortest inspection route, giving its length. It is now decided to start the inspection route at D . The route must still traverse each pipe at least once but may finish at any node.
12. 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.
  6. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-7_823_1374_226_347} \captionsetup{labelformat=empty} \caption{Figure 6}
  \end{figure} Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
13. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
14. Explain how you determined your shortest route from your labelled diagram. The track between E and F is now closed for resurfacing and cannot be used.
15. Find the shortest route from A to H and state its length.
  (2)
  7. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-8_798_1497_258_283} \captionsetup{labelformat=empty} \caption{Figure 7}
  \end{figure} A project is modelled by the activity network shown in Figure 7. 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 the precedence table in the answer book.
  (3)
17. Complete Diagram 1 in the answer book, to show the early event times and late event times.
18. State the critical activities.
19. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
20. By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
  8. A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:
  Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is $\pounds 15$.
  The profit on each type B radio is $\pounds 12$.
  The firm wishes to maximise its weekly profit.
  Formulate this situation as a linear programming problem, defining your variables.
  (Total 7 marks)

Edexcel D1 Specimen Q1

4 marks Easy -1.8

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

1.

Bhavika

Edexcel D1 Specimen Q10

Easy -1.8

10. & Verity
2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-03_549_526_194_413} \captionsetup{labelformat=empty} \caption{Figure 1}

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

\includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-03_547_524_196_1110} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

Find an alternating path linking George with 5. List the resulting improved matching this gives.
Explain why it is not possible to find a complete matching. George now has task 2 added to his possible allocation.
Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching.
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-04_586_1417_205_317} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} The network in Figure 3 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.
1. Find a minimum spanning tree for the network in Figure 3, showing clearly the order in which you selected the arcs for your tree, using
  1. Kruskal's algorithm,
  2. Prim's algorithm, starting from $A$. Given that footpaths are already in place along $A B$ and $F I$ and so should be included in the spanning tree,
  3. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.)
    4. $\quad \begin{array} { l l l l l l l l l l } 650 & 431 & 245 & 643 & 455 & 134 & 710 & 234 & 162 & 452 \end{array}$
  4. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
  5. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.)
  6. Determine whether your solution to part (b) is optimal. Give a reason for your answer.
    5. (a) Explain why a network cannot have an odd number of vertices of odd degree. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-06_615_1143_338_461} \captionsetup{labelformat=empty} \caption{Figure 4}
    \end{figure} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at $A$. He wishes to minimise the total distance he walks.
  7. Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
  8. Find the length of Hamish's route.
    [0pt] [The total weight of the network in Figure 4 is 4180 m .]
    (1)
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-07_627_1408_223_331} \captionsetup{labelformat=empty} \caption{Figure 5}
    \end{figure} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km .
  9. Use Dijkstra's algorithm to find the shortest route from $A$ to $J$. State your shortest route and its length.
  10. Explain how you determined the shortest route from your labelled diagram. The road from $C$ to $F$ will be closed next week for repairs.
  11. Find a shortest route from $A$ to $J$ that does not include $C F$ and state its length.
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-08_1501_1650_201_210} \captionsetup{labelformat=empty} \caption{Figure 6}
    \end{figure} The captain of the Malde Mare takes passengers on trips across the lake in her boat.
    The number of children is represented by $x$ and the number of adults by $y$. Two of the constraints limiting the number of people she can take on each trip are $$x < 10$$ and $$2 \leqslant y \leqslant 10$$ These are shown on the graph in Figure 6, where the rejected regions are shaded out.
  12. Explain why the line $x = 10$ is shown as a dotted line.
  13. Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip.
    (3) For each trip she charges $\pounds 2$ per child and $\pounds 3$ per adult. She must take at least $\pounds 24$ per trip to cover costs. The number of children must not exceed twice the number of adults.
  14. Use this information to write down two inequalities.
    (2)
2. Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R .
  (4)
3. Use your graph to determine how many children and adults would be on the trip if the captain takes:
  1. the minimum number of passengers,
  2. the maximum number of passengers.
    8. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-10_622_1441_194_312} \captionsetup{labelformat=empty} \caption{Figure 7}
    \end{figure} An engineering project is modelled by the activity network shown in Figure 7. 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 time.
  3. Calculate the early time and late time for each event. Write these in the boxes in Diagram 1 in the answer book.
  4. State the critical activities.
  5. Find the total float on activities $D$ and $F$. You must show your working.
  6. On the grid in the answer book, draw a cascade (Gantt) chart for this project. The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,
  7. which activities must be happening on each of these two days?

AQA D1 Q3

Easy -1.8

3

1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
2. State the number of edges in a minimum spanning tree of a network with $n$ vertices.
The following network has 10 vertices: $A , B , \ldots , J$. The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-004_1294_1118_785_445}
1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
2. State the length of your spanning tree.
3. Draw your spanning tree.

AQA D1 Q4

Moderate -0.3

4 The diagram shows the feasible region of a linear programming problem. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-005_1349_1395_408_294}

On the feasible region, find:
1. the maximum value of $2 x + 3 y$;
2. the maximum value of $3 x + 2 y$;
3. the minimum value of $- 2 x + y$.
Find the 5 inequalities that define the feasible region.

AQA D1 Q5

Moderate -0.8

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}

Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.
(6 marks)
State the corresponding route.
(1 mark)

AQA D1 Q7

Moderate -0.8

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-007_1539_1162_495_424} Stella leaves the bus station at $A$. She decides to walk along all of the roads at least once before returning to $A$.

Explain why it is not possible to start from $A$, travel along each road only once and return to $A$.
Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at $A$.
At each of the 9 places $B , C , \ldots , J$, there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

AQA D1 2006 January Q1

7 marks Moderate -0.8

1

Draw a bipartite graph representing the following adjacency matrix.
(2 marks)

	$\boldsymbol { U }$	$V$	$\boldsymbol { W }$	$\boldsymbol { X }$	$\boldsymbol { Y }$	$\boldsymbol { Z }$
$\boldsymbol { A }$	1	0	1	0	1	0
$\boldsymbol { B }$	0	1	0	1	0	0
$\boldsymbol { C }$	0	1	0	0	0	1
$\boldsymbol { D }$	0	0	0	1	0	0
$\boldsymbol { E }$	0	0	1	0	1	1
$\boldsymbol { F }$	0	0	0	1	1	0

Given that initially $A$ is matched to $W , B$ is matched to $X , C$ is matched to $V$, and $E$ is matched to $Y$, use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

AQA D1 2006 January Q2

5 marks Easy -1.2

2 Use the quicksort algorithm to rearrange the following numbers into ascending order. Indicate clearly the pivots that you use. $$\begin{array} { l l l l l l l l } 18 & 23 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$

AQA D1 2006 January Q3

15 marks Easy -2.0

3

1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
2. State the number of edges in a minimum spanning tree of a network with $n$ vertices.
The following network has 10 vertices: $A , B , \ldots , J$. The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
2. State the length of your spanning tree.
3. Draw your spanning tree.

AQA D1 2006 January Q4

8 marks Moderate -0.8

4 The diagram shows the feasible region of a linear programming problem. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-04_1349_1395_408_294}

On the feasible region, find:
1. the maximum value of $2 x + 3 y$;
2. the maximum value of $3 x + 2 y$;
3. the minimum value of $- 2 x + y$.
Find the 5 inequalities that define the feasible region.

AQA D1 2006 January Q5

7 marks Moderate -0.8

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_412_1561_568_233}

Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.
(6 marks)
State the corresponding route.
(1 mark)

AQA D1 2006 January Q6

7 marks Easy -1.8

6 Two algorithms are shown. \section*{Algorithm 1}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $I = ( P * R * T ) / 100$
Line 50	Let $A = P + I$
Line 60	Let $M = A / ( 12 * T )$
Line 70	Print $M$
Line 80	Stop

\section*{Algorithm 2}

Line 10	Input $P$
Line 20	Input $R$
Line 30	Input $T$
Line 40	Let $A = P$
Line 50	$K = 0$
Line 60	Let $K = K + 1$
Line 70	Let $I = ( A * R ) / 100$
Line 80	Let $A = A + I$
Line 90	If $K < T$ then goto Line 60
Line 100	Let $M = A / ( 12 * T )$
Line 110	Print $M$
Line 120	Stop

In the case where the input values are $P = 400 , R = 5$ and $T = 3$ :

trace Algorithm 1;
trace Algorithm 2.

AQA D1 2006 January Q7

13 marks Moderate -0.5

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_1539_1162_495_424} Stella leaves the bus station at $A$. She decides to walk along all of the roads at least once before returning to $A$.

Explain why it is not possible to start from $A$, travel along each road only once and return to $A$.
Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at $A$.
At each of the 9 places $B , C , \ldots , J$, there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

AQA D1 2006 January Q8

11 marks Moderate -0.8

8 Salvadore is visiting six famous places in Barcelona: La Pedrera $( L )$, Nou Camp $( N )$, Olympic Village $( O )$, Park Guell $( P )$, Ramblas $( R )$ and Sagrada Familia $( S )$. Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel. The table shows the times, in minutes, that it will take to travel between the six places.

\backslashbox{From}{To}	La Pedrera ( $L$ )	Nou Camp (N)	Olympic Village ( $O$ )	Park Guell (P)	Ramblas (R)	Sagrada Familia ( $S$ )
La Pedrera $( L )$	-	35	30	30	37	35
Nou Camp $( N )$	25	-	20	21	25	40
Olympic Village ( $O$ )	15	40	-	25	30	29
Park Guell ( $P$ )	30	35	25	-	35	20
Ramblas ( $R$ )	20	30	17	25	-	25
Sagrada Familia ( $S$ )	25	35	29	20	30	-

Find the total travelling time for:
1. the route $L N O L$;
2. the route $L O N L$.
Give an example of a Hamiltonian cycle in the context of the above situation.
Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
1. Show that, using the nearest neighbour algorithm starting from Sagrada Familia $( S )$, the total travelling time for Salvadore is 145 minutes.
2. Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
3. Salvadore starts from Sagrada Familia ( $S$ ) and then visits Ramblas ( $R$ ). Given that he visits Nou Camp $( N )$ before Park Guell $( P )$, find an improved upper bound for the total travelling time for Salvadore.

AQA D1 2006 January Q9

8 marks Standard +0.3

9 A factory makes three different types of widget: plain, bland and ordinary. Each widget is made using three different machines: $A , B$ and $C$. Each plain widget needs 5 minutes on machine $A , 12$ minutes on machine $B$ and 24 minutes on machine $C$. Each bland widget needs 4 minutes on machine $A , 8$ minutes on machine $B$ and 12 minutes on machine $C$. Each ordinary widget needs 3 minutes on machine $A$, 10 minutes on machine $B$ and 18 minutes on machine $C$. Machine $A$ is available for 3 hours a day, machine $B$ for 4 hours a day and machine $C$ for 9 hours a day. The factory must make:
more plain widgets than bland widgets;
more bland widgets than ordinary widgets.
At least $40 \%$ of the total production must be plain widgets.
Each day, the factory makes $x$ plain, $y$ bland and $z$ ordinary widgets.
Formulate the above situation as 6 inequalities, in addition to $x \geqslant 0 , y \geqslant 0$ and $z \geqslant 0$, writing your answers with simplified integer coefficients.
(8 marks)

AQA D1 2007 January Q1

10 marks Standard +0.3

1 The following network shows the lengths, in miles, of roads connecting nine villages. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}

Use Prim's algorithm, starting from $A$, to find a minimum spanning tree for the network.
Find the length of your minimum spanning tree.
Draw your minimum spanning tree.
State the number of other spanning trees that are of the same length as your answer in part (a).

AQA D1 2007 January Q2

6 marks Moderate -0.8

2 Five people $A , B , C , D$ and $E$ are to be matched to five tasks $R , S , T , U$ and $V$.
The table shows the tasks that each person is able to undertake.

Person	Tasks
$A$	$R , V$
$B$	$R , T$
$C$	$T , V$
$D$	$U , V$
$E$	$S , U$

Show this information on a bipartite graph.
Initially, $A$ is matched to task $V , B$ to task $R , C$ to task $T$, and $E$ to task $U$. Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

AQA D1 2007 January Q3

8 marks Easy -1.3

3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: $A , B , C$ and $D$. Mark decides to start from $A$, drive to the other three places and then return to $A$. Mark wants to keep his driving time to a minimum.

\backslashbox{From}{To}	$\boldsymbol { A }$	$\boldsymbol { B }$	$\boldsymbol { C }$	$\boldsymbol { D }$
A	-	8	6	11
B	14	-	13	25
C	14	9	-	17
$\boldsymbol { D }$	26	10	18	-

Find the length of the tour $A B C D A$.
Find the length of the tour $A D C B A$.
Find the length of the tour using the nearest neighbour algorithm starting from $A$.
Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.

AQA D1 2007 January Q4

8 marks Moderate -0.8

4

A student is using a bubble sort to rearrange seven numbers into ascending order.
Her correct solution is as follows:
Initial list 18 17 13 26 10 14 24
After 1st pass 17 13 18 10 14 24 26
After 2nd pass 13 17 10 14 18 24 26
After 3rd pass 13 10 14 17 18 24 26
After 4th pass 10 13 14 17 18 24 26
After 5th pass 10 13 14 17 18 24 26
Write down the number of comparisons and swaps on each of the five passes.
Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.

AQA D1 2007 January Q5

8 marks Easy -1.2

5 A student is using the following algorithm with different values of $A$ and $B$.

Line 10	Input $A , B$
Line 20	Let $C = 0$ and let $D = 0$
Line 30	Let $C = C + A$
Line 40	Let $D = D + B$
Line 50	If $C = D$ then go to Line 110
Line 60	If $C > D$ then go to Line 90
Line 70	Let $C = C + A$
Line 80	Go to Line 50
Line 90	Let $D = D + B$
Line 100	Go to Line 50
Line 110	Print $C$
Line 120	End

1. Trace the algorithm in the case where $A = 2$ and $B = 3$.
2. Trace the algorithm in the case where $A = 6$ and $B = 8$.
State the purpose of the algorithm.
Write down the final value of $C$ in the case where $A = 200$ and $B = 300$.

AQA D1 2007 January Q6

13 marks Moderate -0.8

6 [Figure 1, printed on the insert, is provided for use in this question.]
Dino is to have a rectangular swimming pool at his villa.
He wants its width to be at least 2 metres and its length to be at least 5 metres.
He wants its length to be at least twice its width.
He wants its length to be no more than three times its width.
Each metre of the width of the pool costs $\pounds 1000$ and each metre of the length of the pool costs $\pounds 500$. He has $\pounds 9000$ available. Let the width of the pool be $x$ metres and the length of the pool be $y$ metres.

Show that one of the constraints leads to the inequality $$2 x + y \leqslant 18$$
Find four further inequalities.
On Figure 1, draw a suitable diagram to show the feasible region.
Use your diagram to find the maximum width of the pool. State the corresponding length of the pool.

AQA D1 2007 January Q7

14 marks Standard +0.3

7 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351} The total of all the times in the diagram is 2280 seconds.

1. Craig is staying at the Circus ( $C$ ) and has to visit the Oriental ( $O$ ). Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from $C$ to $O$.
2. Write down the corresponding route.
1. Find, by inspection, the shortest time to walk from $A$ to $M$.
2. Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.

	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
\(\boldsymbol { A }\)	1	0	1	0	1	0
\(\boldsymbol { B }\)	0	1	0	1	0	0
\(\boldsymbol { C }\)	0	1	0	0	0	1
\(\boldsymbol { D }\)	0	0	0	1	0	0
\(\boldsymbol { E }\)	0	0	1	0	1	1
\(\boldsymbol { F }\)	0	0	0	1	1	0

Person	Tasks
\(A\)	\(R , V\)
\(B\)	\(R , T\)
\(C\)	\(T , V\)
\(D\)	\(U , V\)
\(E\)	\(S , U\)

Questions D1 (932 questions)

Browse by module

Browse by board

Edexcel D1 2009 June Q17

Edexcel D1 2011 June Q1

Edexcel D1 2011 June Q10

Edexcel D1 Specimen Q1

Edexcel D1 Specimen Q10

AQA D1 Q3

AQA D1 Q4

AQA D1 Q5

AQA D1 Q7

AQA D1 2006 January Q1

AQA D1 2006 January Q2

AQA D1 2006 January Q3

AQA D1 2006 January Q4

AQA D1 2006 January Q5

AQA D1 2006 January Q6

AQA D1 2006 January Q7

AQA D1 2006 January Q8

AQA D1 2006 January Q9

AQA D1 2007 January Q1

AQA D1 2007 January Q2

AQA D1 2007 January Q3

AQA D1 2007 January Q4

AQA D1 2007 January Q5

AQA D1 2007 January Q6

AQA D1 2007 January Q7

Line 10	Input \(P\)
Line 20	Input \(R\)
Line 30	Input \(T\)
Line 40	Let \(I = ( P * R * T ) / 100\)
Line 50	Let \(A = P + I\)
Line 60	Let \(M = A / ( 12 * T )\)
Line 70	Print \(M\)
Line 80	Stop

\backslashbox{From}{To}	La Pedrera ( \(L\) )	Nou Camp (N)	Olympic Village ( \(O\) )	Park Guell (P)	Ramblas (R)	Sagrada Familia ( \(S\) )
La Pedrera \(( L )\)	-	35	30	30	37	35
Nou Camp \(( N )\)	25	-	20	21	25	40
Olympic Village ( \(O\) )	15	40	-	25	30	29
Park Guell ( \(P\) )	30	35	25	-	35	20
Ramblas ( \(R\) )	20	30	17	25	-	25
Sagrada Familia ( \(S\) )	25	35	29	20	30	-

Initial list	18	17	13	26	10	14	24
After 1st pass	17	13	18	10	14	24	26
After 2nd pass	13	17	10	14	18	24	26
After 3rd pass	13	10	14	17	18	24	26
After 4th pass	10	13	14	17	18	24	26
After 5th pass	10	13	14	17	18	24	26

Line 10	Input \(A , B\)
Line 20	Let \(C = 0\) and let \(D = 0\)
Line 30	Let \(C = C + A\)
Line 40	Let \(D = D + B\)
Line 50	If \(C = D\) then go to Line 110
Line 60	If \(C > D\) then go to Line 90
Line 70	Let \(C = C + A\)
Line 80	Go to Line 50
Line 90	Let \(D = D + B\)
Line 100	Go to Line 50
Line 110	Print \(C\)
Line 120	End