Oxford Cambridge and RSA
GCSE
Further Mathematics A
Y544/01: Discrete Mathematics
*1920756440*
A Level
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 75.
• 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 2025 [Y/508/5513] DC (PQ/FC) 359474/3
OCR is an exempt Charity
Turn over
1 A coach operator offers sightseeing tours of a city. The sightseeing tour starts and
ends at stop A, and there are tourist attractions at B, C, D, E, F and G. The table
below shows the distances in metres that the coach must travel between each of the
seven stops.
A B C D E F G
, 2
A – 120 100 230 260 150 200
B 120 – 180 210 200 250 280
C 100 180 – 235 190 170 270
D 230 210 235 – 170 185 210
E 260 200 190 170 – 210 270
F 150 250 170 185 210 – 195
27 27
G 200 280 210 195 –
0 0
The coach operator wants to find a route which starts and ends at A, visiting every
tourist attraction once.
(a) State the standard network problem that they must solve. [1]
(b) Use the nearest neighbour method to find an upper bound for the length of
the coach
operator’s route starting at A.
(c) Beginning by removing stop A to reduce the network, use an algorithm to
determine a lower
bound for the length of the coach operator’s route.
(d) By referring to your lower bound, comment on the length of the route found
by the nearest
neighbour method.
2 (a) Graph G is shown below
A B
C
F
E D
(i) Show that graph G is not bipartite. [2]
(ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3]
(iii) Determine whether
J graph
K G isLsimply connected.
M N O [1]
J 0 1 1 0 1 0
(b) The adjacency matrix for a digraph H is shown below
K 2 0 1 1 0 0
L 1 1 0 To1 1 1
From
M 0 0 1 1 0 1
N 1 0 1 0 0 1
© OCR 2025
O 0 1 0
Y544/01 Jun25
1 1 0
, 3
(i) Write down the indegree and outdegree of node L. [2]
(ii) Determine whether digraph H is simply connected. [1]
3 Hiro uses a sorting algorithm to sort the heights in cm of 8 people into ascending
order.
At the end of the first pass through the algorithm, Hiro ends up with the list below:
142 165 152 135 171 154 172 182
(a) If Hiro used the shuttle sort algorithm, write down the possibilities for the
original list. [1]
Hiro actually used the bubble sort algorithm starting at the left-hand side.
(b) Complete the second and third passes using the bubble sort algorithm.
You should show the list that results at the end of each pass.
In total, Hiro needed 5 passes to complete the bubble sort algorithm.
In total, the shuttle sort algorithm would take 12 comparisons to sort the original list
into ascending order.
(c) Using the total number of comparisons for each algorithm, compare the
efficiency of bubble sort and shuttle sort for sorting the heights of the 8
people. [3]
(d) It takes a computer 2 4. #10-3 seconds to sort a list of 300 numbers into
ascending order using the bubble sort algorithm.
Find the approximate length of a list the computer could sort in 1 minute. Give your
answer
to 1 significant figure.
4 The table shows the activities involved in a project, together with the immediate
predecessors and the duration of each activity in hours.
Immediate Duration
Activity
Predecessors (hours)
A – 5
B – 4
C A 3
D B 3
E D 2
F B 5
© OCR 2025 Y544/01 Jun25 Turn over
, 4
G C, E 2
H D 5
I G 3
J C, E, H 1
K D, F 2
(a) (i) By constructing an activity network for the project, determine the
minimum time in
which the project can be completed.
(ii) State the critical activities. [1]
(b) Calculate the interfering float for each non-critical activity. [3]
Each activity requires one worker. When an activity is started it must be completed
without interruption.
(c) Use the diagram in the Printed Answer Booklet to determine the minimum
number of workers needed to complete the project in the minimum
completion time.
Each column in the diagram represents 1 hour. For each worker, write the
letter of the activity they are doing in each box, or leave the box blank if the
worker is resting for that hour. You
may not need to use all the rows or columns in the table.
(d) Activity C takes an additional t hours, but all other timings are unchanged.
Determine the range of values of t that result in an increase in the minimum project
completion time.
5 The table below shows the pay-off for Player A in a two-person zero-sum game
between Player A and Player B. Each player has three options; P, Q and R represent
the options for Player A and X, Y and Z represent the options for player B.
X Y Z
P 1 2 -1
Q 3 0 2
R -1 4 -2
(a) Write down the maximum possible pay-off to Player B if Player A plays
option P. [1]
(b) Determine whether or not the game is stable. [4]
(c) Show that there are no Nash Equilibrium points for the game. [2]
© OCR 2025 Y544/01 Jun25
GCSE
Further Mathematics A
Y544/01: Discrete Mathematics
*1920756440*
A Level
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 75.
• 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 2025 [Y/508/5513] DC (PQ/FC) 359474/3
OCR is an exempt Charity
Turn over
1 A coach operator offers sightseeing tours of a city. The sightseeing tour starts and
ends at stop A, and there are tourist attractions at B, C, D, E, F and G. The table
below shows the distances in metres that the coach must travel between each of the
seven stops.
A B C D E F G
, 2
A – 120 100 230 260 150 200
B 120 – 180 210 200 250 280
C 100 180 – 235 190 170 270
D 230 210 235 – 170 185 210
E 260 200 190 170 – 210 270
F 150 250 170 185 210 – 195
27 27
G 200 280 210 195 –
0 0
The coach operator wants to find a route which starts and ends at A, visiting every
tourist attraction once.
(a) State the standard network problem that they must solve. [1]
(b) Use the nearest neighbour method to find an upper bound for the length of
the coach
operator’s route starting at A.
(c) Beginning by removing stop A to reduce the network, use an algorithm to
determine a lower
bound for the length of the coach operator’s route.
(d) By referring to your lower bound, comment on the length of the route found
by the nearest
neighbour method.
2 (a) Graph G is shown below
A B
C
F
E D
(i) Show that graph G is not bipartite. [2]
(ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3]
(iii) Determine whether
J graph
K G isLsimply connected.
M N O [1]
J 0 1 1 0 1 0
(b) The adjacency matrix for a digraph H is shown below
K 2 0 1 1 0 0
L 1 1 0 To1 1 1
From
M 0 0 1 1 0 1
N 1 0 1 0 0 1
© OCR 2025
O 0 1 0
Y544/01 Jun25
1 1 0
, 3
(i) Write down the indegree and outdegree of node L. [2]
(ii) Determine whether digraph H is simply connected. [1]
3 Hiro uses a sorting algorithm to sort the heights in cm of 8 people into ascending
order.
At the end of the first pass through the algorithm, Hiro ends up with the list below:
142 165 152 135 171 154 172 182
(a) If Hiro used the shuttle sort algorithm, write down the possibilities for the
original list. [1]
Hiro actually used the bubble sort algorithm starting at the left-hand side.
(b) Complete the second and third passes using the bubble sort algorithm.
You should show the list that results at the end of each pass.
In total, Hiro needed 5 passes to complete the bubble sort algorithm.
In total, the shuttle sort algorithm would take 12 comparisons to sort the original list
into ascending order.
(c) Using the total number of comparisons for each algorithm, compare the
efficiency of bubble sort and shuttle sort for sorting the heights of the 8
people. [3]
(d) It takes a computer 2 4. #10-3 seconds to sort a list of 300 numbers into
ascending order using the bubble sort algorithm.
Find the approximate length of a list the computer could sort in 1 minute. Give your
answer
to 1 significant figure.
4 The table shows the activities involved in a project, together with the immediate
predecessors and the duration of each activity in hours.
Immediate Duration
Activity
Predecessors (hours)
A – 5
B – 4
C A 3
D B 3
E D 2
F B 5
© OCR 2025 Y544/01 Jun25 Turn over
, 4
G C, E 2
H D 5
I G 3
J C, E, H 1
K D, F 2
(a) (i) By constructing an activity network for the project, determine the
minimum time in
which the project can be completed.
(ii) State the critical activities. [1]
(b) Calculate the interfering float for each non-critical activity. [3]
Each activity requires one worker. When an activity is started it must be completed
without interruption.
(c) Use the diagram in the Printed Answer Booklet to determine the minimum
number of workers needed to complete the project in the minimum
completion time.
Each column in the diagram represents 1 hour. For each worker, write the
letter of the activity they are doing in each box, or leave the box blank if the
worker is resting for that hour. You
may not need to use all the rows or columns in the table.
(d) Activity C takes an additional t hours, but all other timings are unchanged.
Determine the range of values of t that result in an increase in the minimum project
completion time.
5 The table below shows the pay-off for Player A in a two-person zero-sum game
between Player A and Player B. Each player has three options; P, Q and R represent
the options for Player A and X, Y and Z represent the options for player B.
X Y Z
P 1 2 -1
Q 3 0 2
R -1 4 -2
(a) Write down the maximum possible pay-off to Player B if Player A plays
option P. [1]
(b) Determine whether or not the game is stable. [4]
(c) Show that there are no Nash Equilibrium points for the game. [2]
© OCR 2025 Y544/01 Jun25
