Oxford Cambridge and RSA Examinations GCE Further Mathematics AY534/01: Discrete Mathematics AS Level question paper and marking scheme (merged)

Oxford Cambridge and
RSA Examinations GCE
Further Mathematics
AY534/01: Discrete
Mathematics AS Level
question paper and
marking scheme
(merged)

, Oxford Cambridge and RSA

Friday 26 May 2023 – Afternoon
AS Level Further Mathematics A
Y534/01 Discrete Mathematics
Time allowed: 1 hour 15 minutes
* 9 9 7 5 4 2 9 7 0 3 *




You must have:
• the Printed Answer Booklet
• the Formulae Booklet for AS Level Further


QP
Mathematics A
• a scientific or graphical calculator




INSTRUCTIONS
• Use black ink. You can use an HB pencil, but only for graphs and diagrams.
• Write your answer to each question in the space provided in the Printed Answer
Booklet. If you need extra space use the lined pages at the end of the Printed Answer
Booklet. The question numbers must be clearly shown.
• Fill in the boxes on the front of the Printed Answer Booklet.
• Answer all the questions.
• Where appropriate, your answer should be supported with working. Marks might be
given for using a correct method, even if your answer is wrong.
• Give non-exact numerical answers correct to 3 significant figures unless a different
degree of accuracy is specified in the question.
• The acceleration due to gravity is denoted by g m s–2. When a numerical value is
needed use g = 9.8 unless a different value is specified in the question.
• Do not send this Question Paper for marking. Keep it in the centre or recycle it.

INFORMATION
• The total mark for this paper is 60.
• The marks for each question are shown in brackets [ ].
• This document has 8 pages.

ADVICE
• Read each question carefully before you start your answer.




© OCR 2023 [D/508/5500] OCR is an exempt Charity
DC (PQ/CT) 328708/2 Turn over

, 2
1 Jane wants to travel from home to the local town.

Jane can do this by train, by bus or by both train and bus.

(a) Give an example of a problem that Jane could be answering that would give a construction
problem. [1]


A website gives Jane all the possible buses and trains that she could use.
Jane finds 7 possible ways to make the journey.
• 2 of the 7 journeys involve travelling by train for at least part of the journey
• 6 of the 7 journeys involve travelling by bus for at least part of the journey
(b) Use the inclusion-exclusion principle to find how many of the 7 journeys involve travelling
by both train and bus. [2]


2 A network is shown below.

A

4 3
2 E
B
15

5 8 9


C 2 D

(a) Use an appropriate algorithm to find the least weight (shortest) path from A to D. [3]

(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. [3]




© OCR 2023 Y534/01 Jun23

, 3
3 The list of numbers below is to be sorted into increasing order.

23 10 18 7 62 54 31 82

(a) Sort the list using bubble sort.
You do not need to show intermediate working.

(i) Record the list that results at the end of each pass. [3]

(ii) Record the number of swaps used in each pass. [2]

(b) Now sort the original list using shuttle sort.
You do not need to show intermediate working.

(i) Record the list that results at the end of each pass. [3]

(ii) Record the number of swaps used in each pass. [2]

(c) Using the total number of comparisons plus the total number of swaps as a measure of
efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this
particular list. [1]


Bubble sort and shuttle sort are both O (n 2) .

(d) Explain what this means for the run-time of the algorithms when the length of the list being
sorted changes from 1000 to 3000. [1]




© OCR 2023 Y534/01 Jun23 Turn over