OCR AS Level Further Mathematics B (MEI)
Modelling with Algorithms questions and
answers.
1 (a) . . (i) State .the .number .of .arcs .in .the .complete .graph .with .6 .nodes. [1]
(ii) State .the .minimum .number .of .arcs .in .a .simply .connected .graph .with .6 .nodes. [1]
(b) . (i) Using .the .nodes .in .the .Printed .Answer .Booklet, .draw .the .graph .described .by .the
.incidence .matrix .below. [1]
A .B . C . D . E
A . J0 . 1 0.
.1 0N
K
.
B . K1 . 0 O
. 2 0
C . K1 . 2 . 1O
. 2 0
K . 3O
D . 0 .0
O
.0 0 1.
K 0O
E . 0L 1
. 3
1 P
(ii) State .the .order .of .node .C. [1]
© .OCR Y413/01 Turn .over
. .Jun22
,2 A .process .for .finding .a .square .root .of .the .positive .real .number .N .is .described .by .the .flow
.chart .below.
START
Input .the .values
.of .N .and .A
.where .A .> .0
N .+ .A
Let . B .= . A
.
2
Is No
–10 .< .B .– .A .< .10–6
–6 Let . A .= .B
?
Yes
Output .B
STOP
(a) Explain .why .the .process .described .by .the .flow .chart .is .an .example .of .an .algorithm. [1]
(b) Work .through .the .algorithm .using .the .inputs .N .= .73 .and .A .= .8. .Record .the .values .of .A
.and .B, .to .at .least .9 .decimal .places .where .necessary, .every .time .they .change.
Give .the .final .output .correct .to .7 .decimal .places. [3]
(c) The .inputs .remain .as .N .= .73 .and .A .= .8. .The .box .in .the .algorithm .where .B .is .defined
.needs .adapting .to .ensure .that .the .negative .square .root .of .73 .is .the .output.
Explain .how .to .adapt .the .box. [1]
A .student .claims .that .if .the .statement . A .2 .0 .is .removed .from .the .algorithm, .so .that .there .is
.no .longer .a .restriction .on .the .value .of .A, .the .algorithm .can .still .be .used .to .find .a .square
.root .of .N.
(d) Explain .whether .the .student’s .claim .is .correct. [1]
, 3 In .Fig. .3 .the .weights .of .the .arcs .represent .distances.
A 10 H
20 9 50
B G
85
31
23 7 42
5
37
C 14 D
F
29
6
E
Fig. .3
Dijkstra’s .algorithm .is .to .be .used .once .to .find .both .the .shortest .path .from .A .to .C .and .the .shortest
.path .from .C .to .G.
(a) State .which .vertex .should .be .chosen .as .the .start .vertex. [1]
(b) (i) On .the .copy .of .the .network .in .the .Printed .Answer .Booklet, .apply .Dijkstra’s .algorithm
.(with .the .starting .vertex .stated .in .part .(a)) .to .find .both .the .shortest .path .from .A .to .C
.and .the .shortest .path .from .C .to .G. [5]
(ii) State .the .weight .of .the .shortest .route .from .A .to .F .via .C. [1]
(c) Apply .Prim’s .algorithm, .starting .at .A, .to .find .the .minimum .spanning .tree .for .the .network .in
Fig. .3.
• State .the .order .in .which .the .arcs .were .included .in .the .tree.
• Draw .the .minimum .spanning .tree. [3]
© .OCR Y413/01 Turn .over
. .Jun22
Modelling with Algorithms questions and
answers.
1 (a) . . (i) State .the .number .of .arcs .in .the .complete .graph .with .6 .nodes. [1]
(ii) State .the .minimum .number .of .arcs .in .a .simply .connected .graph .with .6 .nodes. [1]
(b) . (i) Using .the .nodes .in .the .Printed .Answer .Booklet, .draw .the .graph .described .by .the
.incidence .matrix .below. [1]
A .B . C . D . E
A . J0 . 1 0.
.1 0N
K
.
B . K1 . 0 O
. 2 0
C . K1 . 2 . 1O
. 2 0
K . 3O
D . 0 .0
O
.0 0 1.
K 0O
E . 0L 1
. 3
1 P
(ii) State .the .order .of .node .C. [1]
© .OCR Y413/01 Turn .over
. .Jun22
,2 A .process .for .finding .a .square .root .of .the .positive .real .number .N .is .described .by .the .flow
.chart .below.
START
Input .the .values
.of .N .and .A
.where .A .> .0
N .+ .A
Let . B .= . A
.
2
Is No
–10 .< .B .– .A .< .10–6
–6 Let . A .= .B
?
Yes
Output .B
STOP
(a) Explain .why .the .process .described .by .the .flow .chart .is .an .example .of .an .algorithm. [1]
(b) Work .through .the .algorithm .using .the .inputs .N .= .73 .and .A .= .8. .Record .the .values .of .A
.and .B, .to .at .least .9 .decimal .places .where .necessary, .every .time .they .change.
Give .the .final .output .correct .to .7 .decimal .places. [3]
(c) The .inputs .remain .as .N .= .73 .and .A .= .8. .The .box .in .the .algorithm .where .B .is .defined
.needs .adapting .to .ensure .that .the .negative .square .root .of .73 .is .the .output.
Explain .how .to .adapt .the .box. [1]
A .student .claims .that .if .the .statement . A .2 .0 .is .removed .from .the .algorithm, .so .that .there .is
.no .longer .a .restriction .on .the .value .of .A, .the .algorithm .can .still .be .used .to .find .a .square
.root .of .N.
(d) Explain .whether .the .student’s .claim .is .correct. [1]
, 3 In .Fig. .3 .the .weights .of .the .arcs .represent .distances.
A 10 H
20 9 50
B G
85
31
23 7 42
5
37
C 14 D
F
29
6
E
Fig. .3
Dijkstra’s .algorithm .is .to .be .used .once .to .find .both .the .shortest .path .from .A .to .C .and .the .shortest
.path .from .C .to .G.
(a) State .which .vertex .should .be .chosen .as .the .start .vertex. [1]
(b) (i) On .the .copy .of .the .network .in .the .Printed .Answer .Booklet, .apply .Dijkstra’s .algorithm
.(with .the .starting .vertex .stated .in .part .(a)) .to .find .both .the .shortest .path .from .A .to .C
.and .the .shortest .path .from .C .to .G. [5]
(ii) State .the .weight .of .the .shortest .route .from .A .to .F .via .C. [1]
(c) Apply .Prim’s .algorithm, .starting .at .A, .to .find .the .minimum .spanning .tree .for .the .network .in
Fig. .3.
• State .the .order .in .which .the .arcs .were .included .in .the .tree.
• Draw .the .minimum .spanning .tree. [3]
© .OCR Y413/01 Turn .over
. .Jun22
