Questions — Edexcel D1 (480 questions)

6. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
      (3 marks)
2. Show these maximum flows on Diagram 1 on the answer sheet.
   (1 mark)
3. 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)
4. Indicate a maximum flow on Diagram 3.
   (2 marks)
5. Prove that your flow is maximal.
   (2 marks)

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\).

1. 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.
2. Set up an initial Simplex tableau for this problem.
   (3 marks)
3. 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}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. 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 Paper Reference(s)
   6689 \section*{Decision Mathematics D1 (New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Monday 25 June 2001 - Morning} Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G. In the boxes on the answer book, write the name of the examining body (Edexcel), your centre number, candidate number, the unit title (Decision Mathematics D1), the paper reference (6689), your surname, other name and signature. Full marks may be obtained for answers to ALL questions. This paper has seven questions. You must ensure that your answers to parts of questions are clearly labelled. You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit. \section*{END}
   1. The precedence table for activities involved in a small project is shown below
6. Explain
   1. the purpose of the variables \(r , s\) and \(t\),
   2. the final row of the tableau.
7. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
8. Interpret your solution. \section*{Materials required for examination
   Graph Paper (ASG2)} Items included with question papers
   Answer booklet \section*{Decision Mathematics D1 (New Syllabus)
   \textbackslash section*\{Advanced/Advanced Subsidiary\}} \section*{Friday 18 January 2002 - Afternoon} Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature. Full marks may be obtained for answers to ALL questions.
   This paper has seven questions. You must ensure that your answers to parts of questions are clearly labelled. You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.
   1. Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs \(1,2,3,4\) or 5 . The table shows each member's preferences for the jobs.

   Ann	1 or 2
   Bryn	3 or 1
   Daljit	2 or 4
   Gareth	5 or 3
   Nickos	1 or 2

   Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
9. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
10. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
11. Find a second alternating path from the initial allocation.
    2. (i) Use the binary search algorithm to try to locate the name SABINE in the following alphabetical list. Explain each step of the algorithm.
    1. ABLE
    2. BROWN
    3. COOKE
    4. DANIEL
    5. DOUBLE
    6. \(F E W\)
    7. OSBORNE
    8. PAUL
    9. SWIFT
    10. TURNER
        (ii) Find the maximum number of iterations of the binary search algorithm needed to locate a name in a list of 1000 names.

    	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
    \(A\)	-	10	12	13	20	9
    \(B\)	10	-	7	15	11	7
    \(C\)	12	7	-	11	18	3
    \(D\)	13	15	11	-	27	8
    \(E\)	20	11	18	27	-	18
    \(F\)	9	7	3	8	18	-

    The table shows the distances, in metres, between six nodes \(A , B , C , D , E\), and \(F\) of a network.
12. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. Explain your method and indicate the order in which you selected the edges.
13. Draw your minimum spanning tree and find its total length.
14. State whether your minimum spanning tree is unique. Justify your answer.
    (ii) A connected network \(N\) has seven vertices.
15. State the number of edges in a minimum spanning tree for \(N\). A minimum spanning tree for a connected network has \(n\) edges.
16. State the number of vertices in the network. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-010_474_737_379_367}
    \end{figure} Figure 1 shows a network of roads. Erica wishes to travel from \(A\) to \(L\) as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
17. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling.
18. Show that there is another route which also takes the minimum time
    5. Two fertilizers are available, a liquid \(X\) and a powder \(Y\). A bottle of \(X\) contains 5 units of chemical \(A , 2\) units of chemical \(B\) and \(\frac { 1 } { 2 }\) unit of chemical \(C\). A packet of \(Y\) contains 1 unit of \(A , 2\) units of \(B\) and 2 units of \(C\). A professional gardener makes her own fertilizer. She requires at least 10 units of \(A\), at least 12 units of \(B\) and at least 6 units of \(C\). She buys \(x\) bottles of \(X\) and \(y\) packets of \(Y\).
19. Write down the inequalities which model this situation.
20. On the grid provided construct and label the feasible region. A bottle of \(X\) costs \(\pounds 2\) and a packet of \(Y\) costs \(\pounds 3\).
21. Write down an expression, in terms of \(x\) and \(y\), for the total cost \(\pounds T\).
22. Using your graph, obtain the values of \(x\) and \(y\) that give the minimum value of \(T\). Make your method clear and calculate the minimum value of \(T\).
23. Suggest how the situation might be changed so that it could no longer be represented graphically. Figure 2 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{6.} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_403_789_372_324}
    \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.
24. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
25. State the maximum flow along
    1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
    2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
26. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flow-augmenting route you use, together with its flow.
27. From your final flow pattern, determine the number of van loads passing through \(B\) each day. The company has the opportunity to increase the number of vans loads from one of the warehouses \(W _ { 1 } , W _ { 2 } , W _ { 3 }\), to \(A , B\) or \(C\).
28. Determine how the company should use this opportunity so that it achieves a maximal flow.
    , 啨 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_307_990_404_1690}
    \end{figure} A project is modelled by the activity network shown in Fig 3. The activities are represented by the edges. The number in brackets on each edge gives the time, in days, taken to complete the activity.
29. Calculate the early time and the late time for each event. Write these in the boxes on the answer sheet.
30. Hence determine the critical activities and the length of the critical path.
31. Obtain the total float for each of the non-critical activities.
32. On the first grid on the answer sheet, draw a cascade (Gantt) chart showing the information obtained in parts (b) and (c). Each activity requires one worker. Only two workers are available.
33. On the second grid on the answer sheet, draw up a schedule and find the minimum time in which the 2 workers can complete the project. \section*{(New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Thursday 23 May 2002 - Afternoon} Nil Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy. Full marks may be obtained for answers to ALL questions.
    This paper has eight questions. You must ensure that your answers to parts of questions are clearly labelled.
    You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.
    1.

    Ashford	6
    Colnbrook	1
    Datchet	18
    Feltham	12
    Halliford	9
    Laleham	0
    Poyle	5
    Staines	13
    Wraysbury	14

    The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.
    2. While solving a maximizing linear programming problem, the following tableau was obtained.

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	0	0	\(1 \frac { 2 } { 3 }\)	1	0	\(- \frac { 1 } { 6 }\)	\(\frac { 2 } { 3 }\)
    \(y\)	0	1	\(3 \frac { 1 } { 3 }\)	0	1	\(- \frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)
    \(x\)	1	0	- 3	0	- 1	\(\frac { 1 } { 2 }\)	1
    \(P\)	0	0	1	0	1	1	11

34. Explain why this is an optimal tableau.
35. Write down the optimal solution of this problem, stating the value of every variable.
36. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
    3. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_291_307_395_383}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_287_311_397_781}
    \end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$
37. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
38. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_380_965_374_1690}
    \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.
39. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length. The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
40. 1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
    2. Find a route of minimum length.
    3. Find the total length of this shortest route.
       5. An algorithm is described by the flow chart below.
       \includegraphics[max width=\textwidth, alt={}, center]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_1040_825_372_411}
41. Given that \(a = 645\) and \(b = 255\), complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
42. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
43. State what the algorithm achieves. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_711_1049_411_1640}
    \end{figure} A building project is modelled by the activity network shown in Fig. 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. The left box entry at each vertex is the earliest event time and the right box entry is the latest event time.
44. Determine the critical activities and state the length of the critical path.
45. State the total float for each non-critical activity.
46. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
47. draw up a schedule to determine the minimum number of workers required to complete the project in the critical time. State the minimum number of workers.
    7. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-015_472_766_520_342}
    \end{figure}
48. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
49. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
50. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.

8. A chemical company produces two products \(X\) and \(Y\). Based on potential demand, the total production each week must be at least 380 gallons. A major customer's weekly order for 125 gallons of \(Y\) must be satisfied. Product \(X\) requires 2 hours of processing time for each gallon and product \(Y\) requires 4 hours of processing time for each gallon. There are 1200 hours of processing time available each week. Let \(x\) be the number of gallons of \(X\) produced and \(y\) be the number of gallons of \(Y\) produced each week.

1. Write down the inequalities that \(x\) and \(y\) must satisfy. It costs \(\pounds 3\) to produce 1 gallon of \(X\) and \(\pounds 2\) to produce 1 gallon of \(Y\). Given that the total cost of production is \(\pounds C\),
2. express \(C\) in terms of \(x\) and \(y\). The company wishes to minimise the total cost.
3. Using the graphical method, solve the resulting Linear Programming problem. Find the optimal values of \(x\) and \(y\) and the resulting total cost.
4. Find the maximum cost of production for all possible choices of \(x\) and \(y\) which satisfy the inequalities you wrote down in part (a). \section*{(New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Tuesday 5 November 2002 - Morning} \section*{Materials required for examination
   Graph Paper (ASG2)} Items included with question papers
   Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G. In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
   When a calculator is used, the answer should be given to an appropriate degree of accuracy. Full marks may be obtained for answers to ALL questions.
   This paper has eight questions. Page 8 is blank. You must ensure that your answers to parts of questions are clearly labelled.
   You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.
   1. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-016_312_446_360_1873}
   \end{figure} A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).
5. Complete this Hamiltonian cycle.
6. Hence use the planarity algorithm to determine if the graph is planar.
   2. The precedence table for activities involved in manufacturing a toy is shown below. A bipartite graph showing this information is drawn in the answer booklet.
   Initially, \(A , B , D\) and \(E\) are allocated to tasks 2, 1, 3 and 5 respectively.
   Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly.
   2. (a) Explain why it is impossible to draw a network with exactly three odd vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_460_700_1160_388}
   \end{figure} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100 .
7. Determine the value of \(x\), showing your working clearly.
   3. (a) Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_415_800_383_1720}
   \end{figure}
8. Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
      4. The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper ( \(R\) ), Palmer ( \(P\) ), Boase ( \(B\) ), Young ( \(Y\) ), Thomas ( \(T\) ), Kenney ( \(K\) ), Morris ( \(M\) ), Halliwell ( \(H\) ), Wicker ( \(W\) ), Garesalingam ( \(G\) ).
9. Use the quick sort algorithm to sort the names above into alphabetical order.
10. Use the binary search algorithm to locate the name Kenney.
    5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-025_330_1059_315_214}
    \end{figure} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.
11. Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet.
12. Hence determine the critical activities.
13. Calculate the total float time for \(D\). Each activity requires only one person.
14. Find a lower bound for the number of workers needed to complete the process in the minimum time. Given that there are only three workers available, and that workers may not share an activity,
15. schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time.
    6. A company produces two types of self-assembly wooden bedroom suites, the 'Oxford' and the 'York'. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite.
16. On the diagram in the answer book draw straight lines to show which components need to be connected.
17. Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
    (4)
    3. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-028_997_458_285_468}
    \end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6 . An initial matching is obtained by matching the following pairs
    A to 3,
    B to 4,
    \(C\) to 1,
    \(F\) to 5 .
18. Show this matching in a distinctive way on the diagram in the answer book.
19. Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
    4. (a) Draw an activity network described in this precedence table, using as few dummies as possible. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.
20. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
21. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use.
22. Explain why it is not possible to find a complete matching. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-037_385_1072_283_1658}
    \end{figure} Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from \(S\) to \(T\) as quickly as possible.
23. Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\).
24. Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution. On a particular day Avinash must include \(C\) in his route.
25. Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time.
    3. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-038_430_497_251_452}
    \end{figure}
26. Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm.
27. Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
28. State whether your answer to part (b) is unique. Give a reason for your answer.
29. Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. Given that it is permitted to start and finish the inspection at two distinct vertices,
30. find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer.
    4.
    1. Glasgow
    2. Newcastle
    3. Manchester
    4. York
    5. Leicester
    6. Birmingham
    7. Cardiff
    8. Exeter
    9. Southampton
    10. Plymouth
    A binary search is to be performed on the names in the list above to locate the name Newcastle.
31. Explain why a binary search cannot be performed with the list in its present form.
32. Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use.
33. Use the binary search algorithm on your new list to locate the name Newcastle.

2. (a) Use the binary search algorithm to locate the name HUSSAIN in the following alphabetical list. Explain each step of the algorithm.

1. ALLEN
2. BALL
3. COOPER
4. EVANS
5. HUSSAIN
6. JONES
7. MICHAEL
8. PATEL
9. RICHARDS
10. TINDALL
11. WU
    (b) State the maximum number of comparisons that need to be made to locate a name in an alphabetical list of 11 names.
    (1 mark)

\begin{figure}[h] \end{figure} (a) Using an appropriate algorithm, obtain a suitable route starting and finishing at \(A\).
(b) Calculate the total length of this route.
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.
(a) 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)
(b) Obtain an alternating path, starting at \(C\), and use this to improve the initial matching.
(c) Find another alternating path and hence obtain a complete matching.
(3 marks)
5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \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.
(a) Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
(6 marks)
(b) 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.
(c) 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)
6. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
(a) State the maximum flow along
(i) SAET,
(ii) SBDT,
(iii) SCFT.
(3 marks)
(b) Show these maximum flows on Diagram 1 on the answer sheet.
(c) 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.
(d) Indicate a maximum flow on Diagram 3.
(e) Prove that your flow is maximal.
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\).
(a) 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.
(b) Set up an initial Simplex tableau for this problem.
(c) Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h] \end{figure} (d) Obtain the coordinates of the points A, \(C\) and \(D\).
(e) 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\)

• Monday (M)
  \(B\) ◯
• Tuesday (Tu)
  \(C \odot\)
• Wednesday (W)
  \(D\) ◯
• Thursday (Th)
  \(E\) -
• Friday (F)
  (b)
  (c)

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] \end{figure} (c) \begin{figure}[h] \end{figure} Flow augmenting routes
(d) \begin{figure}[h] \end{figure} (e) \(\_\_\_\_\)
\section*{Decision Mathematics D1
(New Syllabus)
Advanced/Advanced Subsidiary } Monday 25 June 2001 - Morning
Time: 1 hour 30 minutes Materials required for examination
Answer Book (AB12)
Graph Paper (ASG2) Items included with question papers
Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G. In the boxes on the answer book, write the name of the examining body (Edexcel), your centre number, candidate number, the unit title (Decision Mathematics D1), the paper reference (6689), your surname, other name and signature. Full marks may be obtained for answers to ALL questions.
This paper has seven questions. You must ensure that your answers to parts of questions are clearly labelled.
You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.

1. The precedence table for activities involved in a small project is shown below

Draw an activity network, using activity on edge and without using dummies, to model this project.
(5)
2. \begin{figure}[h] \end{figure} Figure 1 shows 7 locations \(A , B , C , D , E , F\) and \(G\) which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.
(a) Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
(4)
(b) Draw your minimum spanning tree and find the least cost of the pipelines.
(3)

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.

1. 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)
2. Obtain an alternating path, starting at \(C\), and use this to improve the initial matching.
3. Find another alternating path and hence obtain a complete matching.
   (3 marks)

5. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \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.

1. Calculate the early time and the late time for each event. Write your answers in the boxes on the answer sheet.
   (6 marks)
2. 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.
3. 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)

6. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
      (3 marks)
2. Show these maximum flows on Diagram 1 on the answer sheet.
3. 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.
4. Indicate a maximum flow on Diagram 3.
5. Prove that your flow is maximal.

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\).

1. 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.
2. Set up an initial Simplex tableau for this problem.
3. 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}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. 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
6. Minimum total length of cable
   Question 4 to be answered on this page
7. \(A\)
   • Monday (M)
     \(B\) ◯
   • Tuesday (Tu)
     \(C \odot\)
   • Wednesday (W)
     \(D\) ◯
   • Thursday (Th)
     \(E\) -
   • Friday (F)
   Question 5 to be answered on this page
   Key
8. 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)
9. Critical activities
   Length of critical path \(\_\_\_\_\)
10. 
    \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
11. 1. SAET \(\_\_\_\_\)
    2. SBDT \(\_\_\_\_\)
    3. SCFT \(\_\_\_\_\)
12. \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}
13. \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
14. \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}
15. \(\_\_\_\_\)
    \section*{Decision Mathematics D1
    (New Syllabus)
    Advanced/Advanced Subsidiary } Monday 25 June 2001 - Morning
    Time: 1 hour 30 minutes Materials required for examination
    Answer Book (AB12)
    Graph Paper (ASG2) Items included with question papers
    Answer booklet Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G. In the boxes on the answer book, write the name of the examining body (Edexcel), your centre number, candidate number, the unit title (Decision Mathematics D1), the paper reference (6689), your surname, other name and signature. Full marks may be obtained for answers to ALL questions.
    This paper has seven questions. You must ensure that your answers to parts of questions are clearly labelled.
    You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.
    1. The precedence table for activities involved in a small project is shown below
16. Explain
    1. the purpose of the variables \(r , s\) and \(t\),
    2. the final row of the tableau.
17. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
18. Interpret your solution. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
19. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
20. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
21. Find a second alternating path from the initial allocation.
    2. (i) Use the binary search algorithm to try to locate the name SABINE in the following alphabetical list. Explain each step of the algorithm.
    1. ABLE
    2. BROWN
    3. COOKE
    4. DANIEL
    5. DOUBLE
    6. FEW
    7. OSBORNE
    8. PAUL
    9. SWIFT
    10. TURNER
        (ii) Find the maximum number of iterations of the binary search algorithm needed to locate a name in a list of 1000 names.
    The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.
    2. While solving a maximizing linear programming problem, the following tableau was obtained.

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	0	0	\(1 \frac { 2 } { 3 }\)	1	0	\(- \frac { 1 } { 6 }\)	\(\frac { 2 } { 3 }\)
    \(y\)	0	1	\(3 \frac { 1 } { 3 }\)	0	1	\(- \frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)
    \(x\)	1	0	-3	0	-1	\(\frac { 1 } { 2 }\)	1
    \(P\)	0	0	1	0	1	1	11

22. Explain why this is an optimal tableau.
23. Write down the optimal solution of this problem, stating the value of every variable.
24. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
    3. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-045_438_475_403_494}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-045_442_476_403_1108}
    \end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$
25. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
26. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-046_577_1476_367_333}
    \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.
27. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.
    (5) The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
28. 1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
    2. Find a route of minimum length.
    3. Find the total length of this shortest route.
       (5)
       5. An algorithm is described by the flow chart below.
       \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-047_1590_1264_363_539}
29. Given that \(a = 645\) and \(b = 255\), complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
30. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
31. State what the algorithm achieves.
    6. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-048_1083_1608_421_259}
    \end{figure} A building project is modelled by the activity network shown in Fig. 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. The left box entry at each vertex is the earliest event time and the right box entry is the latest event time.
32. Determine the critical activities and state the length of the critical path.
33. State the total float for each non-critical activity.
34. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
35. draw up a schedule to determine the minimum number of workers required to complete the project in the critical time. State the minimum number of workers.
    (3)
    7. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-049_719_1170_590_438}
    \end{figure}
36. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
37. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
38. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.

8. A chemical company produces two products \(X\) and \(Y\). Based on potential demand, the total production each week must be at least 380 gallons. A major customer's weekly order for 125 gallons of \(Y\) must be satisfied. Product \(X\) requires 2 hours of processing time for each gallon and product \(Y\) requires 4 hours of processing time for each gallon. There are 1200 hours of processing time available each week. Let \(x\) be the number of gallons of \(X\) produced and \(y\) be the number of gallons of \(Y\) produced each week.

1. Write down the inequalities that \(x\) and \(y\) must satisfy.
   (3) It costs \(\pounds 3\) to produce 1 gallon of \(X\) and \(\pounds 2\) to produce 1 gallon of \(Y\). Given that the total cost of production is \(\pounds C\),
2. express \(C\) in terms of \(x\) and \(y\).
   (1) The company wishes to minimise the total cost.
3. Using the graphical method, solve the resulting Linear Programming problem. Find the optimal values of \(x\) and \(y\) and the resulting total cost.
4. Find the maximum cost of production for all possible choices of \(x\) and \(y\) which satisfy the inequalities you wrote down in part (a). 6689 \section*{Edexcel GCE
   Decision Mathematics D1
   Advanced/Advanced Subsidiary } May 2002 Answer Booklet
   1. \(\_\_\_\_\)
      
   2. \(\_\_\_\_\)
      
   4. (a) Shortest route \(\_\_\_\_\) \section*{Length of shortest route}
5. 1. \(\_\_\_\_\)
   2. \(\_\_\_\_\)
   3. \(\_\_\_\_\)
      5. (a)
6. Draw an activity network, using activity on arc, and exactly one dummy, to model the manufacturing process.
7. Explain briefly why it is necessary to use a dummy in this case.
   3. At a water sports centre there are five new instructors. Ali (A), George ( \(G\) ), Jo ( \(J\) ), Lydia ( \(L\) ) and Nadia \(( N )\). They are to be matched to five sports, canoeing \(( C )\), scuba diving \(( D )\), surfing \(( F )\), sailing ( \(S\) ) and water skiing ( \(W\) ). The table indicates the sports each new instructor is qualified to teach.

   Instructor	Sport
   \(A\)	\(C , F , W\)
   \(G\)	\(F\)
   \(J\)	\(D , C , S\)
   \(L\)	\(S , W\)
   \(N\)	\(D , F\)

   Initially, \(A , G , J\) and \(L\) are each matched to the first sport in their individual list.
8. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
9. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used. Given that on a particular day \(J\) must be matched to \(D\),
10. explain why it is no longer possible to find a complete matching.
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-064_720_1305_391_236} Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes \(A\), \(B , C , D , E , F , G\) and \(H\) represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe. Each pipe must be traversed at least once and the length of the inspection route must be minimised.
11. Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node \(C\). The inspection must still traverse each pipe at least once but may finish at any node.
12. Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
    (3)
    5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-065_763_1490_348_242}
    \end{figure}
13. Use Dijkstra's algorithm to find the shortest route from \(S\) to \(T\) in Fig. 3. Show all necessary working in the boxes in the answer booklet. State your shortest route and its length.
14. Explain how you determined the shortest route from your labelling.
15. It is now necessary to go from \(S\) to \(T\) via \(H\). Obtain the shortest route and its length.
    6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)
16. The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
17. Determine the least number of bins needed.
18. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .
    7. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-066_526_1404_345_345}
    \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
19. Write down the source vertices. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-066_525_1406_1233_343}
    \end{figure} Figure 5 shows a feasible flow through the same network.
20. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
21. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
    (6)
22. Show the maximal flow on Diagram 2 and state its value.
23. Prove that your flow is maximal.
    8. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

    \cline { 2 - 5 } \multicolumn{1}{c|}{}	Processing	Blending	Packing	Profit ( \(\pounds 100\) )
    Morning blend	3	1	2	4
    Afternoon blend	2	3	4	5
    Evening blend	4	2	3	3

    The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.
24. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
    (4) An initial Simplex tableau for the above situation is

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	3	2	4	1	0	0	35
    \(s\)	1	3	2	0	1	0	20
    \(t\)	2	4	3	0	0	1	24
    \(P\)	- 4	- 5	- 3	0	0	0	0

25. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
26. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
    (2)
    Paper Reference(s)
    6689/01
    Edexcel GCE
    Decision Mathematics D1
    Advanced/Advanced Subsidiary November 2002
    Answer Booklet
    1. (a) \(A , X , D , F\),
    3. (a)
27. \(A \bullet\)
    • \(C\)
      A
    • \(C\)
      \(G \bullet\)
    • \(D\)
      \(G \bullet\)
    • \(D\)
      \(J \bullet\)
    • \(F\)
      \(J \bullet\)
    • \(F\)
      \(L \bullet\)
    • \(S\)
      \(L \bullet\)
    • \(S\)
      \(N \bullet\)
    • \(W\)
      \(N \bullet\)
    • \(W\)
    • \(\_\_\_\_\)
    • \(\_\_\_\_\)
      
    1. (a) \(\_\_\_\_\)
    2. \(\_\_\_\_\)
       
    Length of route: \(\_\_\_\_\)
    5. (a)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-072_937_2097_277_522} Route:
    Length:
28. \(\_\_\_\_\)
    Turn over
    (Total 10 marks)
29. \(\_\_\_\_\)
    leave
    blank
    leave
    6.
30. \(\_\_\_\_\)
31. \(\_\_\_\_\)
32. \(\_\_\_\_\)

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 .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_755_627_283_285} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_748_618_287_1153} \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.
4. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
5. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
6. 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
7. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
8. Use the binary search algorithm to locate the name Louis.
   5. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-417_938_1408_264_324} \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.
9. 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.
10. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-418_903_1493_260_278} \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.
11. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
    (6)
12. 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.
13. 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}$$
14. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
15. 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.
16. Write down the objective function.
17. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-420_812_1541_278_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.
18. Complete Diagram 2 in the answer book, showing the early and late event times.
19. State the critical activities.
20. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
21. 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.
22. Given that the project is on schedule, which activities must be happening on each of these days?
23. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-422_632_896_1742_523} \captionsetup{labelformat=empty} \caption{Diagram 1}
    \end{figure}
24. Total weight of tree \(\_\_\_\_\)
    2. \(\_\_\_\_\)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-423_108_61_2627_1884}
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_746_601_255_242} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_739_599_260_1103} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} (Question 3 continued)
    C
    • 1
    E • • 2 H • • 3 M • • 4 R • • 5 S • • 6
    4. \(\_\_\_\_\)
    (Question 4 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-427_133_40_2622_1877}
    5. \(\_\_\_\_\)
    (Question 5 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-430_2633_1831_118_118}
    7. \(\_\_\_\_\)
    \section*{(Question 7 continued)} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-432_1616_1637_278_148}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-433_2296_1347_435_182}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-434_2382_1559_127_194}
    (Total 15 marks) \section*{Decision Mathematics D1
    Advanced/Advanced Subsidiary } Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Complete your answers in blue or black ink or pencil.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 7 questions in this question paper. The total mark for this paper is 75.
    There are 8 pages in this question paper. The answer book has 16 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit. \section*{Write your answers in the D1 answer book for this paper.} 1. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-436_611_636_356_719} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.
25. Show this initial matching on Diagram 1 in the answer book.
    (1)
26. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
    (5)
    2. Prim's algorithm finds a minimum spanning tree for a connected graph.
27. Explain the terms
    1. connected graph,
    2. tree,
    3. spanning tree.
28. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]
29. \(\_\_\_\_\)
30. \(\_\_\_\_\)
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-453_614_1315_255_374} \captionsetup{labelformat=empty} \caption{Figure 5}
    \end{figure}
31. \(\_\_\_\_\)
    \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{(b)}

    Event	Immediately preceding activity
    A	-
    B	-
    C
    D
    E
    F
    G
    H

    \end{table} Question 6 continues on the next page \section*{(Question 6 continued)} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(c)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-454_2222_1161_356_330}
    \end{figure} 7. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(Question 7 continued)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-457_927_1315_365_315}
    \end{figure} \section*{6689/01 Edexcel GCE} \section*{Decision Mathematics D1 Advanced/Advanced Subsidiary} \section*{Thursday 27 May 2010 - Morning} Materials required for examination
    Nil Items included with question papers
    D1 Answer Book Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    Check that you have the correct question paper.
    Answer ALL the questions.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 8 questions in this question paper. The total mark for this paper is 75 .
    There are 12 pages in this question paper. The answer book has 20 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit.
    1. \section*{-} \section*{Q} LO
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-471_753_1216_223_361} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
33. Paper Reference(s)
    6689/01
    Edexcel GCE
    Decision Mathematics D1
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-493_130_311_471_1641} \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\) \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-498_993_1262_262_331} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure}
35. \(\_\_\_\_\)
36. 
    D \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{B} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-499_204_435_1567_961}
    \end{figure} \begin{verbatim} G \end{verbatim} A • \section*{Diagram 1} Weight of minimum spanning tree: \(\_\_\_\_\)
37. \(\_\_\_\_\)
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_742_604_296_223} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_734_590_301_1096} \captionsetup{labelformat=empty} \caption{Figure 4}
    \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_744_604_294_221}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_739_592_296_1094}
    5. 6.
    \includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-504_1226_1591_278_178}
    \section*{Graph 1}
    1. (a)
    A binary search is to be performed on the names in the list above to locate the name Kim.
38. Explain why a binary search cannot be performed with the list in its present form.
39. 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.
40. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-510_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
41. Define the terms
    1. tree,
    2. minimum spanning tree.
       (3)
42. 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)
43. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
44. State whether your minimum spanning tree is unique. Justify your answer.
    (1)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-511_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.
45. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
46. Find the optimal values of \(x\) and \(y\). You must make your method clear.
47. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
48. write down the optimal values of \(x\) and \(y\).
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_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$$
49. Find the other two alternating paths that start at A .
50. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
51. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-513_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.
52. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
53. 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.
54. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-514_825_1379_226_342} \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.
55. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
56. 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.
57. Find the shortest route from A to H and state its length.
    (2)
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-515_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.
58. Complete the precedence table in the answer book.
    (3)
59. Complete Diagram 1 in the answer book, to show the early event times and late event times.
60. State the critical activities.
61. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
62. 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:
    • At least 50 type A radios should be produced.
    • The number of type A radios should be between \(20 \%\) and \(40 \%\) of the total number of radios produced.
    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)

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 .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_755_627_283_285} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_748_618_287_1153} \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.
4. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
5. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
6. 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
7. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
8. Use the binary search algorithm to locate the name Louis.
   5. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-417_938_1408_264_324} \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.
9. 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.
10. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-418_903_1493_260_278} \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.
11. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
    (6)
12. 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.
13. 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}$$
14. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
15. 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.
16. Write down the objective function.
17. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-420_812_1541_278_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.
18. Complete Diagram 2 in the answer book, showing the early and late event times.
19. State the critical activities.
20. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
21. 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.
22. Given that the project is on schedule, which activities must be happening on each of these days?
23. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-422_632_896_1742_523} \captionsetup{labelformat=empty} \caption{Diagram 1}
    \end{figure}
24. Total weight of tree \(\_\_\_\_\)
    2. \(\_\_\_\_\)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-423_108_61_2627_1884}
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_746_601_255_242} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_739_599_260_1103} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} (Question 3 continued)
    C
    • 1
    E • • 2 H • • 3 M • • 4 R • • 5 S • • 6
    4. \(\_\_\_\_\)
    (Question 4 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-427_133_40_2622_1877}
    5. \(\_\_\_\_\)
    (Question 5 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-430_2633_1831_118_118}
    7. \(\_\_\_\_\)
    \section*{(Question 7 continued)} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-432_1616_1637_278_148}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-433_2296_1347_435_182}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-434_2382_1559_127_194}
    (Total 15 marks) \section*{Decision Mathematics D1
    Advanced/Advanced Subsidiary } Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Complete your answers in blue or black ink or pencil.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 7 questions in this question paper. The total mark for this paper is 75.
    There are 8 pages in this question paper. The answer book has 16 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit. \section*{Write your answers in the D1 answer book for this paper.} 1. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-436_611_636_356_719} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.
25. Show this initial matching on Diagram 1 in the answer book.
    (1)
26. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
    (5)
    2. Prim's algorithm finds a minimum spanning tree for a connected graph.
27. Explain the terms
    1. connected graph,
    2. tree,
    3. spanning tree.
28. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]
29. \(\_\_\_\_\)
30. \(\_\_\_\_\)
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-453_614_1315_255_374} \captionsetup{labelformat=empty} \caption{Figure 5}
    \end{figure}
31. \(\_\_\_\_\)
    \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{(b)}

    Event	Immediately preceding activity
    A	-
    B	-
    C
    D
    E
    F
    G
    H

    \end{table} Question 6 continues on the next page \section*{(Question 6 continued)} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(c)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-454_2222_1161_356_330}
    \end{figure} 7. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(Question 7 continued)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-457_927_1315_365_315}
    \end{figure} \section*{6689/01 Edexcel GCE} \section*{Decision Mathematics D1 Advanced/Advanced Subsidiary} \section*{Thursday 27 May 2010 - Morning} Materials required for examination
    Nil Items included with question papers
    D1 Answer Book Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    Check that you have the correct question paper.
    Answer ALL the questions.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 8 questions in this question paper. The total mark for this paper is 75 .
    There are 12 pages in this question paper. The answer book has 20 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit.
    1. \section*{-} \section*{Q} LO
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-471_753_1216_223_361} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
33. Paper Reference(s)
    6689/01
    Edexcel GCE
    Decision Mathematics D1
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-493_130_311_471_1641} \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\) \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-498_993_1262_262_331} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure}
35. \(\_\_\_\_\)
36. 
    D \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{B} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-499_204_435_1567_961}
    \end{figure} \begin{verbatim} G \end{verbatim} A • \section*{Diagram 1} Weight of minimum spanning tree: \(\_\_\_\_\)
37. \(\_\_\_\_\)
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_742_604_296_223} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_734_590_301_1096} \captionsetup{labelformat=empty} \caption{Figure 4}
    \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_744_604_294_221}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_739_592_296_1094}
    5. 6.
    \includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-504_1226_1591_278_178}
    \section*{Graph 1}
    1. (a)
    A binary search is to be performed on the names in the list above to locate the name Kim.
38. Explain why a binary search cannot be performed with the list in its present form.
39. 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.
40. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-510_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
41. Define the terms
    1. tree,
    2. minimum spanning tree.
       (3)
42. 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)
43. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
44. State whether your minimum spanning tree is unique. Justify your answer.
    (1)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-511_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.
45. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
46. Find the optimal values of \(x\) and \(y\). You must make your method clear.
47. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
48. write down the optimal values of \(x\) and \(y\).
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_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$$
49. Find the other two alternating paths that start at A .
50. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
51. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-513_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.
52. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
53. 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.
54. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-514_825_1379_226_342} \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.
55. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
56. 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.
57. Find the shortest route from A to H and state its length.
    (2)
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-515_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.
58. Complete the precedence table in the answer book.
    (3)
59. Complete Diagram 1 in the answer book, to show the early event times and late event times.
60. State the critical activities.
61. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
62. 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:
    • At least 50 type A radios should be produced.
    • The number of type A radios should be between \(20 \%\) and \(40 \%\) of the total number of radios produced.
    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)

13
16
5
8
2
15
12
10 6. \section*{Diagram 1}

1. (a) (i) \(\_\_\_\_\)
   (ii) \(\_\_\_\_\)
   (b)
   \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-562_1214_1239_753_349}
   (c) \(\_\_\_\_\)
   

(d) \(\_\_\_\_\)
The table shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G.
(a) Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
(b) Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
(c) Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
(d) State the weight of the minimum spanning tree.
4. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 1436 m ]} (a) Explain the term valency. Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe. Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
(b) Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
(c) Find the length of the inspection route. Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
(d) Find the length of the minimum inspection route excluding HI. Justify your answer.
(e) Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
5. \begin{figure}[h] \end{figure} Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.
(a) Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.
(6)
(b) Explain how you determined your shortest route from your labelled diagram.
(2) Due to flooding, the roads in and out of D are closed.
(c) Find the shortest route from S to T avoiding D . State your shortest route and its length.
(2)
6. \begin{figure}[h] \end{figure} Figure 5 is the activity network relating to a development project. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
(a) Complete the precedence table in the answer book.
(2)
(b) Complete Diagram 1 in the answer book to show the early event times and late event times.
(4)
(c) Calculate the total float for activity E. You must make the numbers you use in your calculation clear.
(2)
(d) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
(2)
(e) Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
7. \begin{figure}[h] \end{figure} A company is going to hire out two types of car, standard and luxury. Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy. Figure 6 shows three constraints, other than \(x , y \geqslant 0\)
Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)
(a) Write, as an inequality, the third constraint shown in Figure 6. The company decides that at least \(\frac { 1 } { 6 }\) of the cars must be luxury cars.
(b) Express this information as an inequality and show that it simplifies to $$5 y \geqslant x$$ You must make the steps in your working clear. Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
(c) Express this information as an inequality.
(d) Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).
(e) Hence determine the feasible region and label it R . The company expects to make \(\pounds 80\) profit per week on each car.
It therefore wishes to maximise \(\mathrm { P } = 80 x + 80 y\), where P is the profit per week.
(f) Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
(g) Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit. (a)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-579_545_1422_890_258} \section*{Diagram 1} (b) (c) \begin{figure}[h] \end{figure} (d) Weight of minimum spanning tree
4. \begin{figure}[h] \end{figure} 5. Key: Paper Reference(s)
6689/01
Edexcel GCE
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-598_130_311_471_1641} \(\stackrel { A } { \bullet } \stackrel { \text { B } } { \bullet }\) F• $$\mathrm { C }$$ \(\stackrel { \mathrm { E } } { \ominus } \stackrel { \text { D } } { \bullet }\) \section*{Diagram 1} 3.
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-628_1302_1579_293_184} \section*{Diagram 1} Diagram 2
(Total 12 marks)
4. S J H A C K P L T L 5. \begin{figure}[h] \end{figure} 6. Leave blank
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-636_2368_1301_294_440}
8. \section*{Diagram 1} \section*{Decision Mathematics D1
Advanced/Advanced Subsidiary } \section*{Friday 17 May 2013 - Morning
Time: 1 hour 30 minutes} Materials required for examination
Nil Items included with question papers
D1 Answer Book Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation or symbolic differentiation/integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
Check that you have the correct question paper.
Answer ALL the questions.
When a calculator is used, the answer should be given to an appropriate degree of accuracy.
Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 7 questions in this question paper. The total mark for this paper is 75.
There are 12 pages in this question paper. The answer book has 16 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
You should show sufficient working to make your methods clear to the Examiner.
Answers without working may not gain full credit. \section*{Write your answers in the D1 answer book for this paper.} 1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, \(1,2,3,4,5\) and 6.
(a) Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
(b) Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.
(6)
2.
0.6
0.2
0.4
0.5
0.7
0.1
0.9
0.3
1.5
1.6
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.
(3)
(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
(c) Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
(d) Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.
3. Order of arcs:
(b)
A
D
C

• F
  B
  E

Diagram 1 (c)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-655_652_536_415_230} D

• F

\section*{Diagram 2} (d) \(\_\_\_\_\)
(e) Minimum time needed: \(\_\_\_\_\)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-656_2632_1829_121_118} (b)
Shortest path from S to T:
Length of shortest path from S to T:
Shortest path from S to T via \(\mathbf { F }\) :
Length of shortest path from S to T via \(\mathbf { F }\) :
5. \begin{figure}[h] \end{figure} [The total weight of the network is 344 miles] 6. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-662_1271_1549_223_201} \section*{Diagram 1} (b) \(\_\_\_\_\)
(c) \(\_\_\_\_\)
(d) \(\_\_\_\_\)
\section*{Pearson Edexcel International Advanced Level Decision Mathematics D1} Advanced/Advanced Subsidiary \section*{You must have:} D1 Answer Book Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. \section*{Instructions}

• Use black ink or ball-point pen.
• If pencil is used for diagrams/sketches/graphs it must be dark (HB or B). Coloured pencils and highlighter pens must not be used.
• Fill in the boxes on the top of the answer book with your name, centre number and candidate number.
• Answer all questions and ensure that your answers to parts of questions are clearly labelled.
• Answer the questions in the D1 answer book provided - there may be more space than you need.
• You should show sufficient working to make your methods clear. Answers without working may not gain full credit.
• When a calculator is used, the answer should be given to an appropriate degree of accuracy.
• Do not return the question paper with the answer book.

\section*{Information}

• The total mark for this paper is 75.
• The marks for each question are shown in brackets
• use this as a guide as to how much time to spend on each question.

\section*{Advice}

• Read each question carefully before you start to answer it.
• Try to answer every question.
• Check your answers if you have time at the end.

\section*{Write your answers in the D1 answer book for this paper.} 1. 11
17
10

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 .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_755_627_283_285} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_748_618_287_1153} \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.
4. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
5. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
6. 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
7. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
8. Use the binary search algorithm to locate the name Louis.
   5. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-417_938_1408_264_324} \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.
9. 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.
10. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-418_903_1493_260_278} \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.
11. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
    (6)
12. 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.
13. 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}$$
14. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
15. 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.
16. Write down the objective function.
17. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-420_812_1541_278_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.
18. Complete Diagram 2 in the answer book, showing the early and late event times.
19. State the critical activities.
20. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
21. 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.
22. Given that the project is on schedule, which activities must be happening on each of these days?
23. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-422_632_896_1742_523} \captionsetup{labelformat=empty} \caption{Diagram 1}
    \end{figure}
24. Total weight of tree \(\_\_\_\_\)
    2. \(\_\_\_\_\)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-423_108_61_2627_1884}
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_746_601_255_242} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_739_599_260_1103} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} (Question 3 continued)
    C
    • 1
    E • • 2 H • • 3 M • • 4 R • • 5 S • • 6
    4. \(\_\_\_\_\)
    (Question 4 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-427_133_40_2622_1877}
    5. \(\_\_\_\_\)
    (Question 5 continued)
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-430_2633_1831_118_118}
    7. \(\_\_\_\_\)
    \section*{(Question 7 continued)} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-432_1616_1637_278_148}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-433_2296_1347_435_182}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-434_2382_1559_127_194}
    (Total 15 marks) \section*{Decision Mathematics D1
    Advanced/Advanced Subsidiary } Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Complete your answers in blue or black ink or pencil.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 7 questions in this question paper. The total mark for this paper is 75.
    There are 8 pages in this question paper. The answer book has 16 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit. \section*{Write your answers in the D1 answer book for this paper.} 1. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-436_611_636_356_719} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.
25. Show this initial matching on Diagram 1 in the answer book.
    (1)
26. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
    (5)
    2. Prim's algorithm finds a minimum spanning tree for a connected graph.
27. Explain the terms
    1. connected graph,
    2. tree,
    3. spanning tree.
28. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]
29. \(\_\_\_\_\)
30. \(\_\_\_\_\)
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-453_614_1315_255_374} \captionsetup{labelformat=empty} \caption{Figure 5}
    \end{figure}
31. \(\_\_\_\_\)
    \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{(b)}

    Event	Immediately preceding activity
    A	-
    B	-
    C
    D
    E
    F
    G
    H

    \end{table} Question 6 continues on the next page \section*{(Question 6 continued)} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(c)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-454_2222_1161_356_330}
    \end{figure} 7. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(Question 7 continued)} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-457_927_1315_365_315}
    \end{figure} \section*{6689/01 Edexcel GCE} \section*{Decision Mathematics D1 Advanced/Advanced Subsidiary} \section*{Thursday 27 May 2010 - Morning} Materials required for examination
    Nil Items included with question papers
    D1 Answer Book Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them. Write your answers for this paper in the D1 answer book provided.
    In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
    Check that you have the correct question paper.
    Answer ALL the questions.
    When a calculator is used, the answer should be given to an appropriate degree of accuracy.
    Do not return the question paper with the answer book. Full marks may be obtained for answers to ALL questions.
    The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 8 questions in this question paper. The total mark for this paper is 75 .
    There are 12 pages in this question paper. The answer book has 20 pages. Any blank pages are indicated. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit.
    1. \section*{-} \section*{Q} LO
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-471_753_1216_223_361} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
33. Paper Reference(s)
    6689/01
    Edexcel GCE
    Decision Mathematics D1
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-493_130_311_471_1641} \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\) \(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-498_993_1262_262_331} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure}
35. \(\_\_\_\_\)
36. 
    D \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{B} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-499_204_435_1567_961}
    \end{figure} \begin{verbatim} G \end{verbatim} A • \section*{Diagram 1} Weight of minimum spanning tree: \(\_\_\_\_\)
37. \(\_\_\_\_\)
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_742_604_296_223} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_734_590_301_1096} \captionsetup{labelformat=empty} \caption{Figure 4}
    \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_744_604_294_221}
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_739_592_296_1094}
    5. 6.
    \includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-504_1226_1591_278_178}
    \section*{Graph 1}
    1. (a)
    A binary search is to be performed on the names in the list above to locate the name Kim.
38. Explain why a binary search cannot be performed with the list in its present form.
39. 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.
40. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-510_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
41. Define the terms
    1. tree,
    2. minimum spanning tree.
       (3)
42. 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)
43. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
44. State whether your minimum spanning tree is unique. Justify your answer.
    (1)
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-511_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.
45. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
46. Find the optimal values of \(x\) and \(y\). You must make your method clear.
47. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
48. write down the optimal values of \(x\) and \(y\).
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_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$$
49. Find the other two alternating paths that start at A .
50. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
51. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-513_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.
52. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
53. 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.
54. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-514_825_1379_226_342} \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.
55. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
56. 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.
57. Find the shortest route from A to H and state its length.
    (2)
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-515_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.
58. Complete the precedence table in the answer book.
    (3)
59. Complete Diagram 1 in the answer book, to show the early event times and late event times.
60. State the critical activities.
61. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
62. 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:
    • At least 50 type A radios should be produced.
    • The number of type A radios should be between \(20 \%\) and \(40 \%\) of the total number of radios produced.
    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)

1. The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise.

Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
2. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use.
3. Explain why it is not possible to find a complete matching. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{f4258313-53d5-4a88-abf9-c0c7926770e4-3_572_1600_340_276}
   \end{figure} Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from \(S\) to \(T\) as quickly as possible.
4. Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\).
   (4)
5. Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution. On a particular day Avinash must include \(C\) in his route.
6. Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time.
   (2)
   \includegraphics[max width=\textwidth, alt={}, center]{f4258313-53d5-4a88-abf9-c0c7926770e4-4_641_735_294_593}
7. Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm.
8. Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
9. State whether your answer to part (b) is unique. Give a reason for your answer.
10. Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. Given that it is permitted to start and finish the inspection at two distinct vertices,
11. find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer.

4.

1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

A binary search is to be performed on the names in the list above to locate the name Newcastle.

1. Explain why a binary search cannot be performed with the list in its present form.
2. Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use.
3. Use the binary search algorithm on your new list to locate the name Newcastle.

5. Figure 3
\includegraphics[max width=\textwidth, alt={}, center]{f4258313-53d5-4a88-abf9-c0c7926770e4-6_584_992_287_589} Figure 3 shows a capacitated directed network. The number on each arc is its capacity. \begin{figure}[h] \end{figure} Figure 4 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\).
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal.
3. Use this initial flow and the labelling procedure on Diagram 1 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
4. Show your maximal flow pattern on Diagram 2.
5. Prove that your flow is maximal.

6. The Young Enterprise Company "Decide", is going to produce badges to sell to decision maths students. It will produce two types of badges. Badge 1 reads "I made the decision to do maths" and Badge 2 reads "Maths is the right decision".
"Decide" must produce at least 200 badges and has enough material for 500 badges.
Market research suggests that the number produced of Badge 1 should be between \(20 \%\) and \(40 \%\) of the total number of badges made. The company makes a profit of 30 p on each Badge 1 sold and 40 p on each Badge 2. It will sell all that it produced, and wishes to maximise its profit. Let \(x\) be the number produced of Badge 1 and \(y\) be the number of Badge 2 .

1. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers.
2. On the grid provided in the answer book, construct and clearly label the feasible region.
3. Using your graph, advise the company on the number of each badge it should produce. State the maximum profit "Decide" will make.
   (3)

7. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Fig. 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the activity. The numbers in circles give the event numbers. Each activity requires one worker.

1. Explain the purpose of the dotted line from event 4 to event 5.
   (1)
2. Calculate the early time and the late time for each event. Write these in the boxes in the answer book.
3. Determine the critical activities.
4. Obtain the total float for each of the non-critical activities.
5. On the grid in the answer book, draw a cascade (Gantt) chart, showing the answers to parts (c) and (d).
6. Determine the minimum number of workers needed to complete the project in the minimum time. Make your reasoning clear. END

1. 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 .

1. 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.
2. Draw your tree using the vertices given in Diagram 1 in the answer book.
3. State the total weight of your tree.

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 .

1. 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 .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \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

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

5. \begin{figure}[h] \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.

1. 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.
2. 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] \end{figure} Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road.

1. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
   (6)
2. 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.

1. 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}$$
2. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
3. 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.
4. Write down the objective function.
5. Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.