0% found this document useful (0 votes)
17 views28 pages

6689 01 Que 20160617

Uploaded by

nleyaeugene5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
17 views28 pages

6689 01 Que 20160617

Uploaded by

nleyaeugene5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

Pearson Edexcel GCE

Decision Mathematics D1
Advanced/Advanced Subsidiary

Friday 17 June 2016 – Afternoon Paper Reference

Time: 1 hour 30 minutes 6689/01


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.
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.
• centre
Fill in the boxes on the top of the answer book with your name,
number and candidate number.
• clearly
Answer all questions and ensure that your answers to parts of questions are
labelled.
• – there may
Answer the questions in the D1 answer book provided
be more space than you need.
• without
You should show sufficient working to make your methods clear. Answers
working may not gain full credit.
• degree of accuracy.is used, the answer should be given to an appropriate
When a calculator

• Do not return the question paper with the answer book.


Information
•• The
The total mark for this paper is 75.
marks for each question are shown in brackets
– use this as a guide as to how much time to spend on each question.
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.
Turn over
P46678A
©2016 Pearson Education Ltd.

1/1/1/1/e2
*P46678A*
Write your answers in the D1 answer book for this paper.

1.

L A L A

M B M B

N C N C

P D P D

T E T E

Figure 1 Figure 2

(a) Define the term ‘bipartite graph’.


(2)

Figure 1 shows the possible allocations of five people, Larry (L), Monisha (M), Nina (N), Phil (P)
and Theo (T), to five activities, A, B, C, D and E.

Figure 2 shows an initial matching.

(b) Starting from this initial matching, use the maximum matching algorithm to find a complete
matching. You should list the alternating path you use and state your complete matching.
(3)

(Total 5 marks)

P46678A 2
2. Draw the activity network described in the precedence table below, using activity on arc and exactly
three dummies.

Activity Immediately preceding activities


A –
B –
C A
D A
E B
F B
G A, E, F
H F
I C
J D, G
K D, G

(Total 5 marks)

P46678A 3 Turn over


3. 59 45 18 55 47 11 63 17 15 42

(a) The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain
the sorted list. You should show the result of each pass and identify your pivots clearly.
(4)

The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper
wire is sold in one metre lengths.

(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut
from one metre lengths. (You should ignore wastage due to cutting.)
(3)

(c) Determine whether your solution to (b) is optimal. Give a reason for your answer.
(2)

(Total 9 marks)

P46678A 4
4.
A
5
B
17 13
E
C
21
15 D
13 31
10
F 4 H 7
2 G
9
14 23 17

J 15
K

Figure 3

Figure 3 represents a network of tram tracks. The number on each edge represents the length,
in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to
minimise the distance she travels.

(a) Use Dijkstra’s algorithm to find the shortest path from A to F. State your path and its length.
(6)

On another day, Sarah wishes to travel from A to F via J.

(b) Find a route of minimal length that goes from A to F via J and state its length.
(2)

(c) Use Prim’s algorithm, starting at G, to find the minimum spanning tree for the network.
You must clearly state the order in which you select the edges of your tree.
(3)

(d) State the length, in miles, of the minimum spanning tree.


(1)

(Total 12 marks)

P46678A 5 Turn over


5.

Start

Input x and y

t=0

x=x–1
Yes
Is x odd? y=y
x t=t+y
x=
2
y = 2y
No
t=t

No Yes
Is x = 0? Output t Stop

Figure 4

An algorithm is described by the flow chart shown in Figure 4.

Given that x = 27 and y = 5,

(a) complete the table in the answer book to show the results obtained at each step when the
algorithm is applied. Give the final output.
(4)
1
The numbers 122 and are to be used as inputs for the algorithm described by the flow chart.
2
(b) (i) State, giving a reason, which number should be input as x.

(ii) State the output.


(3)

(Total 7 marks)

P46678A 6
6.
B 15 C 24 K 22 L

17 42 31 11
40
9
A E 17
23 D 5 F

12 68 18

G 18 H 12 J

Figure 5

[The total weight of the network is 384]

Figure 5 models a network of corridors in an office complex that need to be inspected by a security
guard. The number on each arc is the length, in metres, of the corresponding section of corridor.

Each corridor must be traversed at least once and the length of the inspection route must be
minimised. The guard must start and finish at vertex A.

(a) Use the route inspection algorithm to find the length of the shortest inspection route. State the
arcs that should be repeated. You should make your method and working clear.
(5)

It is now possible for the guard to start at one vertex and finish at a different vertex. An inspection
route that traverses each corridor at least once is still required.

(b) Explain why the inspection route should start at a vertex with odd degree.
(2)

The guard decides to start the inspection route at F and the length of the inspection route must still
be minimised.

(c) Determine where the guard should finish. You must give reasons for your answer.
(2)

(d) State a possible route and its length.


(2)

(Total 11 marks)

P46678A 7 Turn over


7.

5 D(w) 17 K(13) 30

5 17 30
A(5) E(4) G(7) L(5)

M(6) 30
0 B(7) 9 H(8) 17
30
0 9 y

F (5) I(12)
C(3) N(8)

3 x

z J(10) 22

Figure 6

The network in Figure 6 shows the activities that need to be undertaken by a company to complete
a project. Each activity is represented by an arc and the duration, in days, is shown in brackets.
Each activity requires exactly one worker. The early event times and late event times are shown at
each vertex.

Given that the total float on activity D is 1 day,

(a) find the values of w, x, y and z.


(3)

(b) On Diagram 1 in the answer book, draw a cascade (Gantt) chart for the project.
(4)

(c) Use your cascade chart to determine a lower bound for the minimum number of workers
needed to complete the project in the shortest possible time. You must make specific reference
to times and activities.
(2)

It is decided that the company may use up to 36 days to complete the project.

(d) On Diagram 2 in the answer book, construct a scheduling diagram to show how the project can
be completed within 36 days using as few workers as possible.
(3)

(Total 12 marks)

P46678A 8
8. Charlie needs to buy storage containers.

There are two different types of storage container available, standard and deluxe.

Standard containers cost £20 and deluxe containers cost £65. Let x be the number of standard
containers and y be the number of deluxe containers.

The maximum budget available is £520

(a) Write down an inequality, in terms of x and y, to model this constraint.


(1)

Three further constraints are:


x.2
–x + 24y . 24
7x + 8y - 112

(b) Add lines and shading to Diagram 1 in the answer book to represent all four constraints.
Hence determine the feasible region and label it R.
(4)

The capacity of a deluxe container is 50% greater than the capacity of a standard container.
Charlie wishes to maximise the total capacity.

(c) State an objective function, in terms of x and y.


(1)

(d) Use the objective line method to find the optimal vertex, V, of the feasible region. You must
make your objective line clear and label the optimal vertex V.
(3)

(e) Calculate the exact coordinates of vertex V.


(2)

(f) Determine the number of each type of container that Charlie should buy. You must make your
method clear and calculate the cost of purchasing the storage containers.
(3)

(Total 14 marks)
TOTAL FOR PAPER: 75 MARKS

END

P46678A 9
BLANK PAGE

P46678A 10
BLANK PAGE

P46678A 11
BLANK PAGE

P46678A 12
Write your name here
Surname Other names

Centre Number Candidate Number


Pearson
Edexcel GCE
Decision Mathematics D1
Advanced/Advanced Subsidiary

Friday 17 June 2016 – Afternoon Paper Reference

Time: 1 hour 30 minutes 6689/01


Answer Book Total Marks
Do not return the question paper with the answer book.

Turn over

P46678A
©2016 Pearson Education Ltd.
*P46678A0116*
1/1/1/1/e2
Leave
blank
1.
L A L A

DO NOT WRITE IN THIS AREA


M B M B

N C N C

P D P D

T E T E

Figure 1 Figure 2

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q1

(Total 5 marks)

2
*P46678A0216*
DO NOT WRITE IN THIS AREA DO NOT WRITE IN THIS AREA DO NOT WRITE IN THIS AREA

2.

*P46678A0316*
(Total 5 marks)
Q2

3
blank
Leave

Turn over
Leave
blank
3. 59 45 18 55 47 11 63 17 15 42
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

4
*P46678A0416*
Leave
blank
Question 3 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q3

(Total 9 marks)

5
*P46678A0516* Turn over
Leave
blank
4.
A

DO NOT WRITE IN THIS AREA


5
B
13
17 E

C 21
15
D 7
31
13
10
F H
2 4
G

9
14 17

DO NOT WRITE IN THIS AREA


23
J
15
K

Key:

Order of Final
Vertex
labelling value

Working values

Shortest path: . .............................................................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


DO NOT WRITE IN THIS AREA

Length of shortest path: ........................................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
*P46678A0616*
Leave
blank
Question 4 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q4

(Total 12 marks)

7
*P46678A0716* Turn over
Leave
blank
5. (a) You may not need to use all the rows in this table.
It may not be necessary to complete all boxes in each row.

DO NOT WRITE IN THIS AREA


x y t Is x odd? Is x = 0?

27 5 0 Yes

DO NOT WRITE IN THIS AREA


DO NOT WRITE IN THIS AREA

8
*P46678A0816*
Leave
blank
Question 5 continued
DO NOT WRITE IN THIS AREA
DO NOT WRITE IN THIS AREA

Final output _____________________________________________________________

(b)
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q5

(Total 7 marks)

9
*P46678A0916* Turn over
Leave
blank
6.
B 15 C 24 K 22 L

DO NOT WRITE IN THIS AREA


17 42 31 11
40
9
A E 17
23 D 5 F

12 68 18

G 18 H 12 J

Figure 5
[The total weight of the network is 384]
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

10
*P46678A01016*
Leave
blank
Question 6 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q6

(Total 11 marks)

11
*P46678A01116* Turn over
Leave
blank
7. (a) ___________________________________________________________________
___________________________________________________________________

DO NOT WRITE IN THIS AREA


___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(b)
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32

DO NOT WRITE IN THIS AREA


DO NOT WRITE IN THIS AREA

Diagram 1

12
*P46678A01216*
Leave
blank
Question 7 continued
(c) ___________________________________________________________________
DO NOT WRITE IN THIS AREA

___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________

(d)

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38
DO NOT WRITE IN THIS AREA
DO NOT WRITE IN THIS AREA

Diagram 2
Q7

(Total 12 marks)

13
*P46678A01316* Turn over
Leave
blank
8.
y
16 –

DO NOT WRITE IN THIS AREA


14 –

12 –

10 –

8–

DO NOT WRITE IN THIS AREA


6–

4–

2–

0– x

0 4 8 12 16 20 24 28 32

Diagram 1

_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

14
*P46678A01416*
Leave
blank
Question 8 continued
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

15
*P46678A01516* Turn over
Leave
blank
Question 8 continued
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

DO NOT WRITE IN THIS AREA


_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
DO NOT WRITE IN THIS AREA

_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________ Q8

(Total 14 marks)

TOTAL FOR PAPER: 75 MARKS

END

16
*P46678A01616*

You might also like