Question paper - Edexcel

Paper Reference(s)
6689/01
Edexcel GCE
Decision Mathematics D1
Advanced/Advanced Subsidiary
Wednesday 24 May 2006 ( Afternoon
Time: 1 hour 30 minutes
Materials required for examination Items included with question
papers
Nil D1 Answer book
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. Instructions to Candidates
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. Information for Candidates
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
question paper is 75. Advice to Candidates
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.
Write your answers in the D1 answer booklet for this paper.
1. 52 48 50 45 64 47 53 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 completed pass.
(4)
2. (a) Define the term 'alternating path'.
(2) Figure 1 Adam A ( ( B (Dames
Blondes)
Daniela D ( ( C (Catman)
Henry H ( ( F (Scar Flaws)
Min-Seong M ( ( K (Sword of the
Kings)
Robert R ( ( P (Ha!
Repotter)
Sam S ( ( Y (Spy Derman) The bipartite graph in Figure 1 shows the films that six customers wish to
hire this Saturday evening. The shop has only one copy of each film. The
bold lines indicate an initial matching. (b) Starting from this initial matching use the maximum matching
algorithm twice to obtain a complete matching. You should clearly state
the alternating paths you use.
(5) 3. Figure 2
Figure 2 shows the network of pipes represented by arcs. The length
of each pipe, in kilometres, is shown by the number on each arc. The
network is to be inspected for leakages, using the shortest route and
starting and finishing at A. (a) Use the route inspection algorithm to fins which arcs, if any,
need to be traversed twice.
(4)
(b) State the length of the minimum route. [The total weight of the
network is 394 km.]
(1) It is now permitted to start and finish the inspection at two
distinct vertices. (c) State, with a reason, which two vertices should be chosen to
minimise the length of the new route.
(2) 4. (a) Explain what is meant by the term 'path'. Figure 3 Figure 3 shows a network of cycle tracks. The number on each edge
represents the length, in miles, of that track. Mary wishes to cycle from A
to I as part of a cycling holiday. She wishes to minimise the distance she
travels. (b) Use Dijkstra's algorithm to find the shortest path from A to I.
Show all necessary working in the boxes in Diagram 1 in the answer book.
State your shortest path and its length.
(6)
(c) Explain how you determined the shortest path from your
labelling.
(2) Mary wants to visit a theme park at E. (d) Find a path of minimal length that goes from A to I via E and
state its length.
(2) 5. Figure 4 An engineering project is modelled by the activity network shown in Figure
4. The activities are represented by the arcs. The number in brackets on
each arc gives the time, in days, to complete the activity. Each activity
requires one worker. The project is to be completed in the shortest time. (a) Calculate the early time and late time for each event. Write these in
boxes in Diagram 1 in the answer book.
(4)
(b) State the critical activities.
(1)
(c) Find the total float on activities D and F. You must show your
working.
(3)
(d) On the grid in the answer book, draw a cascade (Gantt) chart for this
project.
(4) The chief engineer visits the project on day 15 and day 25 to check the
progress of the work. Given that the project is on schedule, (e) which activities must be happening on each of these two days?
(3) 6. The tableau below is the initial tableau for a maximising linear
programming problem. |Basic | x | y | z |r |s |t |Value |
|variable | | | | | | | |
|r |7 |10 |10 |1 |0 |0 |3600 |
|s |6 |9 |12 |0 |1 |0 |3000 |
|t |2 |3 |4 |0 |0 |1 |2400 |
|P |-35 |-55 |-60 |0 |0 |0 |0 | (a) Write down the four equations represented in the initial
tableau above.
(4)
(b) Taking the most negative number in the profit row to indicate
the pivot column at each stage, solve this linear programming problem.
State the row operations that you use.
(9)
(c) State the values of the objective function and each variable.
(3)
7. Figure 5
Figure 5 shows a capacitated, directed network. The capacity of each
arc is shown on each arc. The numbers in circles represent an initial flow
from S to T. Two cuts C1 and C2 are shown on Figure 5. (a) Write down the capacity of each of the two cuts and the value
of the initial flow.
(3)
(b) Complete the initialisation of the labelling procedure on
Diagram 1 by entering values along arcs AC, CD, DE and DT.
(2)
(c) Hence use the labelling procedure to find a maximal flow
through the network. You must list each flow-augmenting path you use,
together with its flow.
(5)
(d) Show your maximal flow pattern on Diagram 2.
(2)
(e) Prove that your flow is maximal.
(2) TOTAL FOR PAPER: 75 MARKS
END
-----------------------
30 24 21 39
20 H(12) 56 33 44 83 B A C D 44 C2 C1 I(16) K(21) E L(6) B(14) A(10) D(5) E(15) G(8) 5 2 4 F G H I 15 25 17 15 31 33 19 21 25 44 19 3 C2 6 9 20 29 25 40 75 31 A S C1 T C 20 6 18 25 49 0 18 6 45 31 27 27 18 24 7 8 1 20 27 21 27 11 28 37 42
B D E N(12) M(9) F(20) J(10) C(11) 18 27 82 25 21 55