Edexcel D1 (Decision Mathematics 1)

1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.

\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}

1. The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.

$$\begin{array} { l l l l l l l l l l l l } 6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8 \end{array}$$

1. Considering only the total amount, what is the least number of rolls that are needed?
2. Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.
3. Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).
4. Comment on this result.

3. This question should be answered on the sheet provided. A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office. The table summarises the trainees’ preferences.

1. Draw a bipartite graph to model this situation.
2. Explain why no complete matching is possible. Trainee \(T\) is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
3. Draw a second bipartite graph to model the changed situation. In an initial matching, trainee \(P\) is placed in the Dundee office, trainee \(R\) in the Glasgow office, and trainee \(S\) in the Edinburgh office.
4. Draw this initial matching.
5. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.
   (7 marks) Turn over

4. The following matrix gives the capacities of the pipes in a system.

1. Represent this information as a digraph.
2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
4. Explain how you know that this flow is maximal.

5. This question should be answered on the sheet provided. An algorithm is described by the flow chart shown in Figure 1 below. \begin{figure}[h] \end{figure}

1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output.
2. Explain what the algorithm achieves.
3. Attempt to apply the algorithm again, with the initial value of \(a\), as specified in Box 2, changed to 5 . Explain what happens.
   (2 mark)
4. Find the set of positive initial values of \(a\) for which the algorithm will work.
   (2 marks)

6. The manager of a new leisure complex needs to maximise the Revenue \(( \pounds R )\) from providing the following two weekend programmes. The following restrictions apply to each weekend.
No more than 90 participants can be accommodated.
There must be at most 40 adults.
A maximum of 600 person-hours of windsurfing can be offered.
A maximum of 300 person-hours of sailing can be offered.

1. Formulate the above information as a linear programming problem, listing the constraints as inequalities and stating the objective function \(R\).
2. On graph paper, illustrate the constraints, indicating clearly the feasible region.
3. Solve the problem graphically, stating how many adults and how many children should be accepted each weekend and what the revenue will be. The manager is considering buying more windsurfing equipment at a cost of \(\pounds 2000\). This would increase windsurfing provision by \(10 \%\).
4. State, with a reason, whether such a purchase would be cost effective.

7. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows an activity network modelling the tasks involved in widening a bridge over the B451. The arcs represent the tasks and the numbers in brackets gives the time, in days, to complete each task.

1. Find the early and late times for each event.
2. Determine those activities which lie on the critical path and list them in order.
3. State the minimum length of time needed to widen the bridge. Each task needs a single worker.
4. Show that two men would not be sufficient to widen the bridge in the shortest time.
   (2 marks)
5. Draw up a schedule showing how 3 men could complete the project in the shortest time. \section*{Please hand this sheet in for marking}
6. Complete matching:

   \(P\)	\(\bullet\)	\(\bullet\)	\(D\)
   \(Q\)	\(\bullet\)	\(\bullet\)	\(G\)
   \(R\)	\(\bullet\)	\(\bullet\)	\(E\)
   \(S\)	\(\bullet\)	\(\bullet\)	\(L ( H )\)
   \(T\)	\(\bullet\)	\(\bullet\)	\(L\)

   \section*{Please hand this sheet in for marking}

7. \(x\)	\(a\)	\(b\)	\(( a - b ) < 0.01\) ?
   100	50	26	No
   -	26	14.923	No

   Final output
8. \(\_\_\_\_\)

9. \(x\)	\(a\)	\(b\)	\(( a - b ) < 0.01 ?\)
   100

10. \(\_\_\_\_\)
    \section*{Please hand this sheet in for marking}
11. 
    \includegraphics[max width=\textwidth, alt={}, center]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-11_768_1689_427_221}
12. \(\_\_\_\_\)
13. \(\_\_\_\_\)

14. 0	5	10	15	20	25	30	35	40	45	50	55	60
    Worker 1
    Worker 2

15. 0	5	10	15	20	25	30	35	40	45	50	55	60
    Worker 1
    Worker 2
    Worker 3