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.
(2 marks)
4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed \(( A )\) - Monday and Wednesday;
Miss Brown ( \(B\) ) - Monday, Wednesday and Friday;
Ms. Clough ( \(C\) ) - Monday;
Mr. Dingle ( \(D\) ) - Tuesday, Wednesday and Thursday;
Mrs. Evans \(( E )\) - Wednesday and Thursday.
The manager initially suggests that \(A\) might work on Monday, \(B\) on Wednesday and \(D\) on Thursday.
(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.
(3 marks)
(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.
(b) Hence determine the critical activities and the length of the critical path. Each activity requires one worker. The project is to be completed in the minimum time.
(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.
(1 mark)
(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.
(6 marks)
(d) Indicate a maximum flow on Diagram 3.
(2 marks)
(e) 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\).
(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}$$ (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.
(b) Set up an initial Simplex tableau for this problem.
(3 marks)
(c) 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] \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.
(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

Draw an activity network, using activity on edge and without using dummies, to model this project.
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.
(b) Draw your minimum spanning tree and find the least cost of the pipelines.