Cambridge International AS & A Level

* 2 5 7 9 4 4 0 8 6 9 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory May/June 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (LO) 213986
© UCLES 2021 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• Two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of –7.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

© UCLES 2021 9618/31/M/J/21

 3

(c) The given binary floating-point number is not normalised.

Normalise the floating-point number. Show your working.

Mantissa Exponent

0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(d) The denary number 513 cannot be stored accurately as a normalised floating-point number in
this computer system.

(i) Explain the reason for this.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

(ii) Describe an alteration to the way floating-point numbers are stored to enable this number
to be stored accurately using the same total number of bits.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2021 9618/31/M/J/21 [Turn over

 4

2 (a) Describe the purpose of a user-defined data type.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Define, using pseudocode, the following enumerated data types:

(i) SchoolDay to hold data about the days students are usually in school.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) WeekEnd to hold data about the days that are not school days.

...........................................................................................................................................

..................................................................................................................................... [1]

(c) Define, using pseudocode, the composite data type ClubMeet. This will hold data about club
members that includes:

• first name and last name

• the two days they attend:
○ one on a school day
○ one not on a school day.

Use the enumerated types you created in part (b).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/31/M/J/21

 5

3 (a) Draw one line to connect each Operating System (OS) term to the most appropriate
description about it.

OS term Description

Using secondary storage to simulate

additional main memory
Multi-tasking

Managing the processes running on

the CPU
Paging

Managing the execution of many programs

that appear to run at the same time

Interrupt handling

Locating non-contiguous blocks of data and

relocating them

Scheduling
Transferring control to another routine when
a service is required

Virtual memory
Reading/writing same-size blocks of data
from/to secondary storage when required

[5]

(b) Explain how an interpreter executes a program without producing a complete translated
version of it.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/31/M/J/21 [Turn over

 6

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of
expressions.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Identify, with reasons, a data structure that could be used to evaluate an expression
in RPN.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(b) Write the infix expression in RPN.

(a – b) * (a + c) / 7

...................................................................................................................................................

............................................................................................................................................. [1]

(c) Write the RPN expression as an infix expression.

a b / 4 * a b + -

...................................................................................................................................................

............................................................................................................................................. [1]

(d) Evaluate the RPN expression:

a b + c d / /

where a = 17, b = 3, c = 48 and d = 12.

Show your working.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/31/M/J/21

 7

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram
using Dijkstra’s algorithm.

Show your working and write your answers in the table provided.

Base
4
5

Town 1 2
1 Town 2
8

Town 3

7 3 Town 6
1

5
6
Town 4 Town 5

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answers

Town 1 Town 2 Town 3 Town 4 Town 5 Town 6

[5]

© UCLES 2021 9618/31/M/J/21 [Turn over

 8

(b) Explain the use of graphs to aid Artificial Intelligence (AI).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

6 Give two benefits and two drawbacks of packet switching.

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

Drawback 1 ......................................................................................................................................

..........................................................................................................................................................

Drawback 2 ......................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2021 9618/31/M/J/21

 9

7 The diagram shows a logic circuit.

A P
Y
B

C R

Z
Q

(a) Complete the truth table for the given logic circuit. Show your working.

Inputs Working space Outputs

A B C P Q R Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
[3]
(b) State the name of the logic circuit.

............................................................................................................................................. [1]

(c) Write the Boolean expressions for the two outputs Y and Z in the truth table as
sum-of-products and state the purpose of each output.

Y = ............................................................................................................................................

Purpose ....................................................................................................................................

Z = ............................................................................................................................................

Purpose ....................................................................................................................................
[4]

© UCLES 2021 9618/31/M/J/21 [Turn over

 10

8 (a) State two factors that may affect the performance of a sorting algorithm.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one-
dimensional array into descending order, and orders the corresponding students’ names
stored into a two-dimensional array in the same order as the scores. All the arrays are indexed
from 1.

The contents of both arrays after sorting are shown.

Name
Score
1 2
1 98 1 Smithfield Tom
2 97 2 Johnson Jane

… …

248 5 248 Peters Jade

249 3 249 Allen John

YearSize 249 ←
Flag ←
TRUE
WHILE Flag = TRUE
Flag FALSE←
FOR Student ←
1 TO YearSize - 1
IF Score[Student] < Score[Student + 1] THEN
Temp1 ←
Score[Student]
Temp2 ←
Name[Student,1]
Temp3 ←
Name[Student,2]
Score[Student] Score[Student + 1] ←
Name[Student,1] Name[Student + 1,1] ←
Name[Student,2] Name[Student + 1,2] ←
Score[Student + 1] Temp1 ←
Name[Student + 1,1] Temp2 ←
Name[Student + 1,2] Temp3 ←
Flag TRUE ←
ENDIF
NEXT Student
ENDWHILE

© UCLES 2021 9618/31/M/J/21

 11

Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [6]

© UCLES 2021 9618/31/M/J/21 [Turn over

 12

9 (a) Describe what is meant by an imperative (procedural) programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Describe what is meant by a declarative programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Identify the programming paradigm for each of these program code examples.

Program code example Programming paradigm

male(john).
female(ethel).
parent(john, ethel).
FOR Counter = 1 TO 20
X = X * Counter
NEXT Counter
Start: LDD Counter
INC ACC
STO Counter
public class Vehicle
{
private speed;
public Vehicle()
{
speed = 0;
}
}
[4]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/31/M/J/21

 Cambridge International AS & A Level
* 4 7 5 7 0 1 8 5 5 9 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory May/June 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (LK/CB) 205788/1
© UCLES 2021 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• Two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of –7.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

© UCLES 2021 9618/32/M/J/21

 3

(c) The given binary floating-point number is not normalised.

Normalise the floating-point number. Show your working.

Mantissa Exponent

0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(d) The denary number 513 cannot be stored accurately as a normalised floating-point number in
this computer system.

(i) Explain the reason for this.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

(ii) Describe an alteration to the way floating-point numbers are stored to enable this number
to be stored accurately using the same total number of bits.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2021 9618/32/M/J/21 [Turn over

 4

2 (a) Describe the purpose of a user-defined data type.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Define, using pseudocode, the following enumerated data types:

(i) SchoolDay to hold data about the days students are usually in school.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) WeekEnd to hold data about the days that are not school days.

...........................................................................................................................................

..................................................................................................................................... [1]

(c) Define, using pseudocode, the composite data type ClubMeet. This will hold data about club
members that includes:

• first name and last name

• the two days they attend:
○ one on a school day
○ one not on a school day.

Use the enumerated types you created in part (b).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/32/M/J/21

 5

3 (a) Draw one line to connect each Operating System (OS) term to the most appropriate
description about it.

OS term Description

Using secondary storage to simulate

additional main memory
Multi-tasking

Managing the processes running on

the CPU
Paging

Managing the execution of many programs

that appear to run at the same time

Interrupt handling

Locating non-contiguous blocks of data and

relocating them

Scheduling
Transferring control to another routine when
a service is required

Virtual memory
Reading/writing same-size blocks of data
from/to secondary storage when required

[5]

(b) Explain how an interpreter executes a program without producing a complete translated
version of it.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/32/M/J/21 [Turn over

 6

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of
expressions.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Identify, with reasons, a data structure that could be used to evaluate an expression
in RPN.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(b) Write the infix expression in RPN.

(a – b) * (a + c) / 7

...................................................................................................................................................

............................................................................................................................................. [1]

(c) Write the RPN expression as an infix expression.

a b / 4 * a b + -

...................................................................................................................................................

............................................................................................................................................. [1]

(d) Evaluate the RPN expression:

a b + c d / /

where a = 17, b = 3, c = 48 and d = 12.

Show your working.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/32/M/J/21

 7

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram
using Dijkstra’s algorithm.

Show your working and write your answers in the table provided.

Base
4
5

Town 1 2
1 Town 2
8

Town 3

7 3 Town 6
1

5
6
Town 4 Town 5

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answers

Town 1 Town 2 Town 3 Town 4 Town 5 Town 6

[5]

© UCLES 2021 9618/32/M/J/21 [Turn over

 8

(b) Explain the use of graphs to aid Artificial Intelligence (AI).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

6 Give two benefits and two drawbacks of packet switching.

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

Drawback 1 ......................................................................................................................................

..........................................................................................................................................................

Drawback 2 ......................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2021 9618/32/M/J/21

 9

7 The diagram shows a logic circuit.

A P
Y
B

C R

Z
Q

(a) Complete the truth table for the given logic circuit. Show your working.

Inputs Working space Outputs

A B C P Q R Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
[3]
(b) State the name of the logic circuit.

............................................................................................................................................. [1]

(c) Write the Boolean expressions for the two outputs Y and Z in the truth table as
sum-of-products and state the purpose of each output.

Y = ............................................................................................................................................

Purpose ....................................................................................................................................

Z = ............................................................................................................................................

Purpose ....................................................................................................................................
[4]

© UCLES 2021 9618/32/M/J/21 [Turn over

 10

8 (a) State two factors that may affect the performance of a sorting algorithm.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one-
dimensional array into descending order, and orders the corresponding students’ names
stored into a two-dimensional array in the same order as the scores. All the arrays are indexed
from 1.

The contents of both arrays after sorting are shown.

Name
Score
1 2
1 98 1 Smithfield Tom
2 97 2 Johnson Jane

… …

248 5 248 Peters Jade

249 3 249 Allen John

YearSize 249 ←
Flag ←
TRUE
WHILE Flag = TRUE
Flag FALSE←
FOR Student ←
1 TO YearSize - 1
IF Score[Student] < Score[Student + 1] THEN
Temp1 ←
Score[Student]
Temp2 ←
Name[Student,1]
Temp3 ←
Name[Student,2]
Score[Student] Score[Student + 1] ←
Name[Student,1] Name[Student + 1,1] ←
Name[Student,2] Name[Student + 1,2] ←
Score[Student + 1] Temp1 ←
Name[Student + 1,1] Temp2 ←
Name[Student + 1,2] Temp3 ←
Flag TRUE ←
ENDIF
NEXT Student
ENDWHILE

© UCLES 2021 9618/32/M/J/21

 11

Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [6]

© UCLES 2021 9618/32/M/J/21 [Turn over

 12

9 (a) Describe what is meant by an imperative (procedural) programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Describe what is meant by a declarative programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Identify the programming paradigm for each of these program code examples.

Program code example Programming paradigm

male(john).
female(ethel).
parent(john, ethel).
FOR Counter = 1 TO 20
X = X * Counter
NEXT Counter
Start: LDD Counter
INC ACC
STO Counter
public class Vehicle
{
private speed;
public Vehicle()
{
speed = 0;
}
}
[4]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/32/M/J/21

 Cambridge International AS & A Level
* 4 0 8 1 7 6 1 7 1 4 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory May/June 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (LO) 213987
© UCLES 2021 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• Two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of –7.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

© UCLES 2021 9618/33/M/J/21

 3

(c) The given binary floating-point number is not normalised.

Normalise the floating-point number. Show your working.

Mantissa Exponent

0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(d) The denary number 513 cannot be stored accurately as a normalised floating-point number in
this computer system.

(i) Explain the reason for this.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

(ii) Describe an alteration to the way floating-point numbers are stored to enable this number
to be stored accurately using the same total number of bits.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2021 9618/33/M/J/21 [Turn over

 4

2 (a) Describe the purpose of a user-defined data type.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Define, using pseudocode, the following enumerated data types:

(i) SchoolDay to hold data about the days students are usually in school.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) WeekEnd to hold data about the days that are not school days.

...........................................................................................................................................

..................................................................................................................................... [1]

(c) Define, using pseudocode, the composite data type ClubMeet. This will hold data about club
members that includes:

• first name and last name

• the two days they attend:
○ one on a school day
○ one not on a school day.

Use the enumerated types you created in part (b).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/33/M/J/21

 5

3 (a) Draw one line to connect each Operating System (OS) term to the most appropriate
description about it.

OS term Description

Using secondary storage to simulate

additional main memory
Multi-tasking

Managing the processes running on

the CPU
Paging

Managing the execution of many programs

that appear to run at the same time

Interrupt handling

Locating non-contiguous blocks of data and

relocating them

Scheduling
Transferring control to another routine when
a service is required

Virtual memory
Reading/writing same-size blocks of data
from/to secondary storage when required

[5]

(b) Explain how an interpreter executes a program without producing a complete translated
version of it.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/33/M/J/21 [Turn over

 6

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of
expressions.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Identify, with reasons, a data structure that could be used to evaluate an expression
in RPN.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(b) Write the infix expression in RPN.

(a – b) * (a + c) / 7

...................................................................................................................................................

............................................................................................................................................. [1]

(c) Write the RPN expression as an infix expression.

a b / 4 * a b + -

...................................................................................................................................................

............................................................................................................................................. [1]

(d) Evaluate the RPN expression:

a b + c d / /

where a = 17, b = 3, c = 48 and d = 12.

Show your working.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/33/M/J/21

 7

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram
using Dijkstra’s algorithm.

Show your working and write your answers in the table provided.

Base
4
5

Town 1 2
1 Town 2
8

Town 3

7 3 Town 6
1

5
6
Town 4 Town 5

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answers

Town 1 Town 2 Town 3 Town 4 Town 5 Town 6

[5]

© UCLES 2021 9618/33/M/J/21 [Turn over

 8

(b) Explain the use of graphs to aid Artificial Intelligence (AI).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

6 Give two benefits and two drawbacks of packet switching.

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

Drawback 1 ......................................................................................................................................

..........................................................................................................................................................

Drawback 2 ......................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2021 9618/33/M/J/21

 9

7 The diagram shows a logic circuit.

A P
Y
B

C R

Z
Q

(a) Complete the truth table for the given logic circuit. Show your working.

Inputs Working space Outputs

A B C P Q R Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
[3]
(b) State the name of the logic circuit.

............................................................................................................................................. [1]

(c) Write the Boolean expressions for the two outputs Y and Z in the truth table as
sum-of-products and state the purpose of each output.

Y = ............................................................................................................................................

Purpose ....................................................................................................................................

Z = ............................................................................................................................................

Purpose ....................................................................................................................................
[4]

© UCLES 2021 9618/33/M/J/21 [Turn over

 10

8 (a) State two factors that may affect the performance of a sorting algorithm.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one-
dimensional array into descending order, and orders the corresponding students’ names
stored into a two-dimensional array in the same order as the scores. All the arrays are indexed
from 1.

The contents of both arrays after sorting are shown.

Name
Score
1 2
1 98 1 Smithfield Tom
2 97 2 Johnson Jane

… …

248 5 248 Peters Jade

249 3 249 Allen John

YearSize 249 ←
Flag ←
TRUE
WHILE Flag = TRUE
Flag FALSE←
FOR Student ←
1 TO YearSize - 1
IF Score[Student] < Score[Student + 1] THEN
Temp1 ←
Score[Student]
Temp2 ←
Name[Student,1]
Temp3 ←
Name[Student,2]
Score[Student] Score[Student + 1] ←
Name[Student,1] Name[Student + 1,1] ←
Name[Student,2] Name[Student + 1,2] ←
Score[Student + 1] Temp1 ←
Name[Student + 1,1] Temp2 ←
Name[Student + 1,2] Temp3 ←
Flag TRUE ←
ENDIF
NEXT Student
ENDWHILE

© UCLES 2021 9618/33/M/J/21

 11

Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [6]

© UCLES 2021 9618/33/M/J/21 [Turn over

 12

9 (a) Describe what is meant by an imperative (procedural) programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Describe what is meant by a declarative programming language.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Identify the programming paradigm for each of these program code examples.

Program code example Programming paradigm

male(john).
female(ethel).
parent(john, ethel).
FOR Counter = 1 TO 20
X = X * Counter
NEXT Counter
Start: LDD Counter
INC ACC
STO Counter
public class Vehicle
{
private speed;
public Vehicle()
{
speed = 0;
}
}
[4]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/33/M/J/21

 Cambridge International AS & A Level
* 4 6 0 2 1 9 7 8 1 9 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory May/June 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (EF) 311847
© UCLES 2022 [Turn over
 2

1 Data types can be defined using pseudocode.

The data type, LibraryRecord, is defined in pseudocode as:

TYPE LibraryRecord
DECLARE Title : STRING
DECLARE Fiction : BOOLEAN
DECLARE Author : STRING
DECLARE NumberOfCopies : INTEGER
ENDTYPE

A variable, LibraryBook, is declared in pseudocode as:

DECLARE LibraryBook : LibraryRecord

(a) Write pseudocode statements to assign:

• A Level Computer Science to Title of LibraryBook
• FALSE to Fiction of LibraryBook.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The type definition for LibraryRecord is changed.

(i) The value for NumberOfCopies must be between 1 and 10 inclusive.

Write the updated line of pseudocode from the type definition of LibraryRecord to
implement the change.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Every copy of every book is now uniquely identified by an accession number,
AccessionNumber, as it is added to the library. Each library record will include one or
more accession numbers. Each accession number is an integer.

Write the extra line of pseudocode needed in the type definition of LibraryRecord.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/31/M/J/22

 3

(c) A record is a user-defined composite data type.

Explain what is meant by a user-defined composite data type.

Include an example of another user-defined composite data type in your answer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

© UCLES 2022 9618/31/M/J/22 [Turn over

 4

2 A declarative language is used to represent the following facts about cats.

01 type(leopard, wild).
02 type(lion, wild).
03 type(cheetah, wild).
04 type(savannah, hybrid).
05 type(persian, domestic).
06
07 hair(leopard, medium).
08 hair(lion, short).
09 hair(cheetah, medium).
10 hair(savannah, medium).
11 hair(persian, long).
12
13 spots(leopard, yes).
14 spots(lion, no).
15 spots(cheetah, yes).
16 spots(savannah, yes).
17 spots(persian, no).

These clauses have the following meaning:

Clause Meaning
01 A leopard is a type of wild cat.
08 A lion has short hair.
16 A savannah has spots.

© UCLES 2022 9618/31/M/J/22

 5

(a) More facts are to be included. A caracal is a wild cat with short hair.

Write the additional clauses to record these facts.

18 .............................................................................................................................................

19 .............................................................................................................................................
[2]

(b) Using the variable Cat, the goal:

hair(Cat, medium)

returns

Cat = leopard, cheetah, savannah

Write the result returned by the goal:

hair(Cat, long)

Cat = ................................................................................................................................. [1]

(c) (i) Write the goal, using the variable Pet, to find all the domestic cats.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Write the goal, using the variable WildSpotty, to find all the wild cats with spots.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/31/M/J/22 [Turn over

 6

3 Data can be sent over networks using either circuit switching or packet switching.

Describe both methods of data transmission. Include a different advantage and disadvantage for
each method.

Circuit switching ...............................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Advantage ........................................................................................................................................

..........................................................................................................................................................

Disadvantage ...................................................................................................................................

..........................................................................................................................................................

Packet switching ..............................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Advantage ........................................................................................................................................

..........................................................................................................................................................

Disadvantage ...................................................................................................................................

..........................................................................................................................................................
[8]

© UCLES 2022 9618/31/M/J/22

 7

4 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) Describe what is meant by RISC and CISC processors.

RISC .........................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

CISC .........................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Identify two differences between RISC and CISC processors.

1 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[2]

© UCLES 2022 9618/31/M/J/22 [Turn over

 8

5 Part of a program’s calculations uses the integer variables j, k, m, n and p.

j = 3
k = 2
m = 10
n = (j + k)/(j - k)
p = m * (m - j * k)

(a) Write the Reverse Polish Notation (RPN) for the expression:

(j + k)/(j - k)

............................................................................................................................................. [2]

(b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN
expression:
m m j k * - *

[4]

(ii) Describe the main steps in the evaluation of this RPN expression using a stack.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2022 9618/31/M/J/22

 9

(c) State two other uses of a stack.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................
[2]

6 A virtual machine is used to emulate a new computer system.

Describe two benefits and one limitation of using a virtual machine for this purpose.

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Limitation ..........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[6]

© UCLES 2022 9618/31/M/J/22 [Turn over

 10

7 A program is to be written using Object-Oriented Programming (OOP) for a shop that sells knitting
yarn. There are three types of yarn: acrylic, wool or mix.

The following data are stored for each type.

• Name
• Colour
• Batch code
• Weight
• Number of balls of yarn in stock (can be edited)
• Type of yarn

The following statements apply to yarn.

• Acrylic can be soft or not soft.

• Wool can be lamb, merino or alpaca.
• Mix contains a percentage of acrylic.

Each type of yarn has a method that will display all the information about the yarn.

(a) Complete this class inheritance diagram to show the properties, methods and inheritance.

Yarn
Name: STRING
Colour: STRING
BatchCode: STRING
Weight: INTEGER
NumberBalls: INTEGER
Type: STRING
Constructor()
EditNumberBalls()
YarnInfo()

Acrylic Wool Mix

Percentage: INTEGER
Constructor()
.......................................... ..........................................
YarnInfo()
Constructor() Constructor()

.......................................... ..........................................

[5]

© UCLES 2022 9618/31/M/J/22

 11

(b) Describe what is meant by the terms properties, methods and inheritance.

Properties .................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Methods ....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Inheritance ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[6]

© UCLES 2022 9618/31/M/J/22 [Turn over

 12

8 A message is to be sent securely. Software uses a key to encrypt the message before it is sent.

(a) (i) Give two reasons for using key cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................
[2]

(ii) Give two methods of key cryptography that can be used.

1 ........................................................................................................................................

2 ........................................................................................................................................
[2]

(b) When there is a secure exchange of key(s), the message is sent.

The use of quantum cryptography is being considered for the secure exchange.

(i) State two possible benefits of using quantum cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

(ii) State two possible drawbacks of using quantum cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

© UCLES 2022 9618/31/M/J/22

 13

BLANK PAGE

© UCLES 2022 9618/31/M/J/22 [Turn over

 14

9 The table shows assembly language instructions for a processor that has one general purpose
register, the Accumulator (ACC).

Instruction Explanation
Label Opcode Operand
LDM #n Load the number n to ACC
LDD <address> Load the contents of the given address to ACC
The address to be used is at the given address
LDI <address>
Load the contents of this second address to ACC
ADD <address> Add the contents of the given address to the ACC
STO <address> Store the contents of the ACC at the given address
Gives a symbolic address <label> to the memory
<label>: <data> location with the contents <data>
<label> can be used in place of <address>
# denotes a denary number, e.g. #123

(a) The address 500 contains the value 100 and the address 100 contains the value 20.

State the addressing mode and the contents of ACC after each instruction has been executed.

LDM #500 Addressing mode ...............................................................................................

Contents of ACC .................................................................................................

LDD 500 Addressing mode ...............................................................................................

Contents of ACC .................................................................................................

LDI 500 Addressing mode ................................................................................................

Contents of ACC .................................................................................................

[3]

© UCLES 2022 9618/31/M/J/22

 15

(b) Use only the given instruction set to write assembly language code to:
• use the constant 20 which needs to be stored
• add this constant to the value stored in the address contained in the variable Y
• store the result in variable Z.

Instruction
Label Opcode Operand

[7]

© UCLES 2022 9618/31/M/J/22

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/31/M/J/22

 Cambridge International AS & A Level
* 5 4 1 6 3 1 4 2 4 8 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory May/June 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (CE/SG) 303765/2
© UCLES 2022 [Turn over
 2

1 Data types can be defined using pseudocode.

The data type, BuildingRecord, is defined in pseudocode as:

TYPE BuildingRecord
DECLARE BuildingID : INTEGER
DECLARE BuildingGroup : STRING
DECLARE OwnerName : STRING
DECLARE BuildingAddress : STRING
DECLARE DateLastSold : DATE
DECLARE PriceLastSold : REAL
ENDTYPE

A variable, BuildingRegister, is declared in pseudocode as:

DECLARE BuildingRegister : BuildingRecord

(a) Write pseudocode statements to assign:

• 1067 to the BuildingID of BuildingRegister

• house to the BuildingGroup of BuildingRegister

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The type definition for BuildingRecord is changed. The data type for BuildingGroup is
changed to an enumerated type, BuildingType, with values of house, bungalow, apartment
and farm.

(i) Write the type declaration for BuildingType in pseudocode.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Write the new declaration for BuildingGroup in pseudocode.

...........................................................................................................................................

..................................................................................................................................... [1]

(iii) Write the new pseudocode statement to assign house to BuildingGroup of

BuildingRegister.

...........................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2022 9618/32/M/J/22

 3

(c) The program is to be rewritten using Object-Oriented Programming (OOP). The data type
BuildingRecord is to be changed to a class, BuildingClass.

The properties for BuildingClass are BuildingID, BuildingGroup, OwnerName,

BuildingAddress, DateLastSold and PriceLastSold.

All the properties are set to PRIVATE, for example:

PRIVATE PriceLastSold : REAL

(i) Write the declaration in pseudocode for OwnerName as PRIVATE.

������������������������������������������������������������������������������������������������������������������������������������������������������������

����������������������������������������������������������������������������������������������������������������������������������������������������� [1]

(ii) Explain why the properties have been set to PRIVATE.

������������������������������������������������������������������������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������

������������������������������������������������������������������������������������������������������������������������������������������������������������

����������������������������������������������������������������������������������������������������������������������������������������������������� [2]

© UCLES 2022 9618/32/M/J/22 [Turn over

 4

2 A declarative language is used to represent the following facts about a school.

01 teaches(alan, mathematics).
02 teaches(ioana, geography).
03 teaches(nina, history).
04 teaches(alan, statistics).
05
06 studies(ahmed, history).
07 studies(freya, history).
08 studies(kim, history).
09 studies(freya, geography).
10 studies(hua, mathematics).
11 studies(hua, statistics).
12 studies(hua, geography).
13
14 tutors(alan, kim).
15 tutors(alan, hua).
16 tutors(alan, freya).
17 tutors(nina, ahmed).

These clauses have the following meaning:

Clause Meaning
01 Alan teaches mathematics.
06 Ahmed studies history.
14 Alan is Kim’s tutor.

(a) More facts are to be included. Sam studies history and Nina is his tutor.

Write the additional clauses to record these facts.

18 .............................................................................................................................................

19 .............................................................................................................................................
[2]

(b) Using the variable Student, the goal:

studies(Student, history)

returns

Student = freya, ahmed, kim

Write the result returned by the goal:

studies(Student, geography)

Student = ....................................................................................................................... [1]

© UCLES 2022 9618/32/M/J/22

 5

(c) Write the goal, using the variable X, to find all the students who have a tutor that teaches
them. For example, Hua has Alan for a tutor and is also taught mathematics by Alan.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

3 The TCP/IP protocol suite has four layers. The application layer provides user services.

(a) Identify two protocols used by this layer. Describe the use of each protocol.

Protocol 1 .................................................................................................................................

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Protocol 2 .................................................................................................................................

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Identify two other layers of the TCP/IP protocol suite. Describe the function of each layer.

Layer 1 ......................................................................................................................................

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Layer 2 ......................................................................................................................................

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2022 9618/32/M/J/22 [Turn over

 6

4 The following syntax diagrams show the syntax of:

• a variable
• an unsigned integer
• a letter
• a digit
• an operator
• an assignment statement.

variable
letter unsigned integer

unsigned integer
digit digit

letter digit
X 1

Y 2

Z 3

operator
+

*
assignment
statement
variable = variable operator variable

(a) The following assignment statements are invalid. State the reason in each case.

X1 = Y2 – 12

Reason .....................................................................................................................................

...................................................................................................................................................

Z = Y12 + Z1

Reason .....................................................................................................................................

...................................................................................................................................................
[2]

© UCLES 2022 9618/32/M/J/22

 7

(b) Complete the Backus-Naur Form (BNF) for the syntax diagrams shown.

<letter> has been completed for you.

<variable> ::= ..................................................................................................................

...................................................................................................................................................

<unsigned_integer> ::= .................................................................................................

...................................................................................................................................................

<letter> ::= X | Y | Z

<digit> ::= ..........................................................................................................................

...................................................................................................................................................

<operator> ::= ..................................................................................................................

...................................................................................................................................................

<assignment_statement> ::= ........................................................................................

...................................................................................................................................................
[5]

(c) The syntax of an assignment statement is changed to allow each of the variables on the
right-hand side of the ‘=’ symbol to be either a variable or an unsigned integer.

(i) Draw a syntax diagram for the new syntax of the assignment statement.

[3]

(ii) Write the Backus-Naur Form (BNF) for your syntax diagram.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

© UCLES 2022 9618/32/M/J/22 [Turn over

 8

5 There are four basic categories of computer architecture. Single Instruction Single Data (SISD) is
one architecture.

Identify the three other categories of computer architecture.

Describe each category that you identify.

Architecture 1 ...................................................................................................................................

Description .......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Architecture 2 ...................................................................................................................................

Description .......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Architecture 3 ...................................................................................................................................

Description .......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[6]

© UCLES 2022 9618/32/M/J/22

 9

6 A logic circuit has two inputs A and B, and two outputs E and F.

A
E

(a) Complete the truth table for this logic circuit.

INPUT OUTPUT
A B E F
0 0
0 1
1 0
1 1
[2]

(b) (i) State the name of this logic circuit.

..................................................................................................................................... [1]

(ii) State the purpose of each output E and F.

Purpose of E .....................................................................................................................

Purpose of F ......................................................................................................................
[2]

© UCLES 2022 9618/32/M/J/22 [Turn over

 10

7 A digital signature is used to validate the authenticity of an electronic message.

In order to produce a digital signature, a digital certificate is required.

(a) State how a digital certificate is obtained.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) (i) Explain how a digital signature is produced before the message is sent.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

(ii) Explain how the digital signature can be checked on receipt to ensure that the message
has not been altered during transmission.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2022 9618/32/M/J/22

 11

8 A binary search or a linear search can be used to look for a specific value in an array.

(a) Complete this pseudocode algorithm for a linear search.

DECLARE MyList : ARRAY[0:9] OF INTEGER

DECLARE MaxIndex : INTEGER
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
DECLARE ValueToFind : ...................................................................................................

INPUT ValueToFind
Found ←
FALSE
Index 0 ←
MaxIndex ←
.........................................................................................................................

REPEAT
IF MyList[Index] = ValueToFind THEN
Found TRUE ←
ENDIF
Index ←
.........................................................................................................................
UNTIL Found OR Index > MaxIndex

IF Found THEN
OUTPUT "Value found at position ", Index
ELSE
OUTPUT ..............................................................................................................................
ENDIF
[4]

(b) (i) State the necessary condition for a binary search.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Describe how to perform a binary search.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2022 9618/32/M/J/22 [Turn over

 12

(iii) Explain how the performance of a binary search varies according to the number of values
in the array.

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [1]

(c) Compare the performance of the algorithms for a binary search and a linear search using
Big O notation for order of time complexity.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

9 State the reasons for including exception handling routines when writing a program.

Include an example of an exception in your answer.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/32/M/J/22

 Cambridge International AS & A Level
* 8 8 7 9 8 5 5 5 9 2 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory May/June 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (LK) 303735/2
© UCLES 2022 [Turn over
 2

1 Data types can be defined using pseudocode.

The data type, LibraryRecord, is defined in pseudocode as:

TYPE LibraryRecord
DECLARE Title : STRING
DECLARE Fiction : BOOLEAN
DECLARE Author : STRING
DECLARE NumberOfCopies : INTEGER
ENDTYPE

A variable, LibraryBook, is declared in pseudocode as:

DECLARE LibraryBook : LibraryRecord

(a) Write pseudocode statements to assign:

• A Level Computer Science to Title of LibraryBook
• FALSE to Fiction of LibraryBook.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The type definition for LibraryRecord is changed.

(i) The value for NumberOfCopies must be between 1 and 10 inclusive.

Write the updated line of pseudocode from the type definition of LibraryRecord to
implement the change.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Every copy of every book is now uniquely identified by an accession number,
AccessionNumber, as it is added to the library. Each library record will include one or
more accession numbers. Each accession number is an integer.

Write the extra line of pseudocode needed in the type definition of LibraryRecord.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/33/M/J/22

 3

(c) A record is a user-defined composite data type.

Explain what is meant by a user-defined composite data type.

Include an example of another user-defined composite data type in your answer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

© UCLES 2022 9618/33/M/J/22 [Turn over

 4

2 A declarative language is used to represent the following facts about cats.

01 type(leopard, wild).
02 type(lion, wild).
03 type(cheetah, wild).
04 type(savannah, hybrid).
05 type(persian, domestic).
06
07 hair(leopard, medium).
08 hair(lion, short).
09 hair(cheetah, medium).
10 hair(savannah, medium).
11 hair(persian, long).
12
13 spots(leopard, yes).
14 spots(lion, no).
15 spots(cheetah, yes).
16 spots(savannah, yes).
17 spots(persian, no).

These clauses have the following meaning:

Clause Meaning
01 A leopard is a type of wild cat.
08 A lion has short hair.
16 A savannah has spots.

© UCLES 2022 9618/33/M/J/22

 5

(a) More facts are to be included. A caracal is a wild cat with short hair.

Write the additional clauses to record these facts.

18 .............................................................................................................................................

19 .............................................................................................................................................
[2]

(b) Using the variable Cat, the goal:

hair(Cat, medium)

returns

Cat = leopard, cheetah, savannah

Write the result returned by the goal:

hair(Cat, long)

Cat = ................................................................................................................................. [1]

(c) (i) Write the goal, using the variable Pet, to find all the domestic cats.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Write the goal, using the variable WildSpotty, to find all the wild cats with spots.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/33/M/J/22 [Turn over

 6

3 Data can be sent over networks using either circuit switching or packet switching.

Describe both methods of data transmission. Include a different advantage and disadvantage for
each method.

Circuit switching ...............................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Advantage ........................................................................................................................................

..........................................................................................................................................................

Disadvantage ...................................................................................................................................

..........................................................................................................................................................

Packet switching ..............................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Advantage ........................................................................................................................................

..........................................................................................................................................................

Disadvantage ...................................................................................................................................

..........................................................................................................................................................
[8]

© UCLES 2022 9618/33/M/J/22

 7

4 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) Describe what is meant by RISC and CISC processors.

RISC .........................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

CISC .........................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Identify two differences between RISC and CISC processors.

1 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[2]

© UCLES 2022 9618/33/M/J/22 [Turn over

 8

5 Part of a program’s calculations uses the integer variables j, k, m, n and p.

j = 3
k = 2
m = 10
n = (j + k)/(j - k)
p = m * (m - j * k)

(a) Write the Reverse Polish Notation (RPN) for the expression:

(j + k)/(j - k)

............................................................................................................................................. [2]

(b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN
expression:
m m j k * - *

[4]

(ii) Describe the main steps in the evaluation of this RPN expression using a stack.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2022 9618/33/M/J/22

 9

(c) State two other uses of a stack.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................
[2]

6 A virtual machine is used to emulate a new computer system.

Describe two benefits and one limitation of using a virtual machine for this purpose.

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Limitation ..........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[6]

© UCLES 2022 9618/33/M/J/22 [Turn over

 10

7 A program is to be written using Object-Oriented Programming (OOP) for a shop that sells knitting
yarn. There are three types of yarn: acrylic, wool or mix.

The following data are stored for each type.

• Name
• Colour
• Batch code
• Weight
• Number of balls of yarn in stock (can be edited)
• Type of yarn

The following statements apply to yarn.

• Acrylic can be soft or not soft.

• Wool can be lamb, merino or alpaca.
• Mix contains a percentage of acrylic.

Each type of yarn has a method that will display all the information about the yarn.

(a) Complete this class inheritance diagram to show the properties, methods and inheritance.

Yarn
Name: STRING
Colour: STRING
BatchCode: STRING
Weight: INTEGER
NumberBalls: INTEGER
Type: STRING
Constructor()
EditNumberBalls()
YarnInfo()

Acrylic Wool Mix

Percentage: INTEGER
Constructor()
.......................................... ..........................................
YarnInfo()
Constructor() Constructor()

.......................................... ..........................................

[5]

© UCLES 2022 9618/33/M/J/22

 11

(b) Describe what is meant by the terms properties, methods and inheritance.

Properties .................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Methods ....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Inheritance ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[6]

© UCLES 2022 9618/33/M/J/22 [Turn over

 12

8 A message is to be sent securely. Software uses a key to encrypt the message before it is sent.

(a) (i) Give two reasons for using key cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................
[2]

(ii) Give two methods of key cryptography that can be used.

1 ........................................................................................................................................

2 ........................................................................................................................................
[2]

(b) When there is a secure exchange of key(s), the message is sent.

The use of quantum cryptography is being considered for the secure exchange.

(i) State two possible benefits of using quantum cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

(ii) State two possible drawbacks of using quantum cryptography.

1 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

2 ........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

© UCLES 2022 9618/33/M/J/22

 13

BLANK PAGE

© UCLES 2022 9618/33/M/J/22 [Turn over

 14

9 The table shows assembly language instructions for a processor that has one general purpose
register, the Accumulator (ACC).

Instruction Explanation
Label Opcode Operand
LDM #n Load the number n to ACC
LDD <address> Load the contents of the given address to ACC
The address to be used is at the given address
LDI <address>
Load the contents of this second address to ACC
ADD <address> Add the contents of the given address to the ACC
STO <address> Store the contents of the ACC at the given address
Gives a symbolic address <label> to the memory
<label>: <data> location with the contents <data>
<label> can be used in place of <address>
# denotes a denary number, e.g. #123

(a) The address 500 contains the value 100 and the address 100 contains the value 20.

State the addressing mode and the contents of ACC after each instruction has been executed.

LDM #500 Addressing mode ...............................................................................................

Contents of ACC .................................................................................................

LDD 500 Addressing mode ...............................................................................................

Contents of ACC .................................................................................................

LDI 500 Addressing mode ................................................................................................

Contents of ACC .................................................................................................

[3]

© UCLES 2022 9618/33/M/J/22

 15

(b) Use only the given instruction set to write assembly language code to:
• use the constant 20 which needs to be stored
• add this constant to the value stored in the address contained in the variable Y
• store the result in variable Z.

Instruction
Label Opcode Operand

[7]

© UCLES 2022 9618/33/M/J/22

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/33/M/J/22

 Cambridge International AS & A Level
* 2 6 9 2 3 9 2 3 6 8 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory May/June 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (KS) 327186
© UCLES 2023 [Turn over
 2

1 Numbers are stored in two different computer systems by using floating-point representation.

System 1 uses:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

System 2 uses:

• 8 bits for the mantissa

• 8 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of 113.75 and show how it would be
represented in each of these two systems.

Show your working.

System 1

Mantissa Exponent

System 2

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/31/M/J/23

 3

(b) Explain the problem that occurred in part (a) when representing the number in system 2.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

2 (a) Draw one line from each machine learning category to its most appropriate description.

Machine learning category Description

simulates the data-processing

capabilities of the human brain to
make decisions
Supervised
learning
enables learning by mapping an input
to an output based on example input–
output pairs
Reinforcement
learning
enables information related to errors
produced by the neural network to be
transmitted
Deep
learning
enables learning in an interactive
environment by trial and error using
its own experiences
Unsupervised
learning
enables learning by allowing the
process to discover patterns on its
own that were previously undetected
[4]

(b) Describe the purpose of both the A* algorithm and Dijkstra’s algorithm.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/M/J/23 [Turn over

 4

3 (a) A hashing algorithm is used to calculate storage locations for records in a random access file.
It calculates hash values by using the function modulus 3.

The function modulus gives the remainder after integer division.

For example, 1030 modulus 3 = 1. Therefore, the record key 1030 gives a hash value of 1.

Complete the table to show the remaining hash values.

Record key Hash value

1030 1

1050

1025
[2]

(b) Describe what happens, in relation to the storage or retrieval of a record in the file, when
the calculated hash value is a duplicate of a previously calculated hash value for a different
record key.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2023 9618/31/M/J/23

 5

4 Two descriptions of user-defined data types are given.

Give appropriate type declaration statements for each, including appropriate names.

(a) A data type to hold a set of prime numbers below 20. These prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) A data type to point to a day in the week, for example Monday.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

5 (a) State, with a reason, where it would be appropriate to use circuit switching.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Give two benefits and two drawbacks of circuit switching.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

...................................................................................................................................................

Drawback 1 ...............................................................................................................................

...................................................................................................................................................

Drawback 2 ...............................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/31/M/J/23 [Turn over

 6

6 Several syntax diagrams are shown.

operator digit
+ 0

– 1

* 2

/ 3

symbol
$ 4

% 5

& 6

@ 7

# 8

letter 9
A

password
letter digit symbol

© UCLES 2023 9618/31/M/J/23

 7

(a) State whether each of the following passwords is valid or invalid and give a reason for your
choice.

DPAD99$ ...................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................

DAD#95 .....................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................

ADY123? ...................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................
[3]

(b) Complete the Backus-Naur Form (BNF) for the syntax diagrams shown.

<symbol> ::= ........................................................................................................................

...................................................................................................................................................

<letter> ::= ........................................................................................................................

...................................................................................................................................................
[1]

(c) An identifier begins with one or more letters, followed by zero digits or one digit or more
digits.

Valid letters and digits are shown in the syntax diagrams on page 6.

Draw a syntax diagram for an identifier.

[4]

© UCLES 2023 9618/31/M/J/23 [Turn over

 8

7 (a) Complete the Karnaugh map (K-map) for the following Boolean expression.

Z = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

AB

CD 00 01 11 10

00

01

11

10

[2]

(b) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(c) Write the Boolean logic expression from your answer to part (b) as a simplified
sum-of-products.

Z = ............................................................................................................................................

............................................................................................................................................. [2]

(d) Use Boolean algebra to give your answer to part (c) in its simplest form.

Z = ...................................................................................................................................... [1]

© UCLES 2023 9618/31/M/J/23

 9

8 Outline the characteristics of massively parallel computers.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [3]

9 (a) Encryption is used to alter data into a form that makes it meaningless if intercepted.

Describe the purpose of asymmetric key cryptography.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Identify two benefits and two drawbacks of quantum cryptography.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

...................................................................................................................................................

Drawback 1 ...............................................................................................................................

...................................................................................................................................................

Drawback 2 ...............................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/31/M/J/23 [Turn over

 10

10 The pseudocode algorithm shown copies an active accounts text file ActiveFile.txt to an
archive accounts text file ArchiveFile.txt, one line at a time. Any blank lines found in the
active accounts text file are replaced with the words "Account not present" in the archive
accounts text file.

Complete this file-handling pseudocode.

DECLARE Account : STRING

..........................................................................................................................................................

OPENFILE "ArchiveFile.txt" FOR WRITE

WHILE NOT ......................................................................................................................................

READFILE "ActiveFile.txt", Account
IF Account = "" THEN

WRITEFILE "ArchiveFile.txt", " .........................................................................."

ELSE

WRITEFILE "ArchiveFile.txt", ...............................................................................

ENDIF
ENDWHILE

..........................................................................................................................................................
CLOSEFILE "ArchiveFile.txt"
[5]

11 Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the
string data type. This will be implemented using the information in the table.

Identifier Data type Description

FrontPointer INTEGER points to the start of the queue

RearPointer INTEGER points to the end of the queue

Length INTEGER the current size of the queue

Queue STRING 1D array to implement the queue

A constant, with identifier MaxSize, limits the size of the queue to 60 items.

(a) Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and
Queue.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
© UCLES 2023 9618/31/M/J/23
 11

(b) Complete the following pseudocode for the function Dequeue to remove the front item from
the queue.

FUNCTION Dequeue RETURNS STRING

DECLARE Item : STRING

......................................................................................................................... > 0 THEN

Item ← .......................................................................................................................

......................................................................................................................................
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN

....................................................................................................................... ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
[4]

(c) Explain how a new element can be added to the queue if it is implemented using two stacks.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

12 (a) Describe what is meant by recursion.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/M/J/23 [Turn over

 12

(b) A Fibonacci sequence is a series of numbers formed by adding together the two preceding
numbers, for example:

0, 1, 1, 2, …

This function calculates and returns values in the Fibonacci sequence and uses recursion.

FUNCTION Fib(Number : INTEGER) RETURNS INTEGER

IF Number <= 1 THEN
Result ← Number
ELSE
Result ← Fib(Number – 1) + Fib(Number – 2)
ENDIF
RETURN Result
ENDFUNCTION

Complete the trace table for the function when it is called as Fib(5).

Call number Function call Number Result Return value

5

[5]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/31/M/J/23

 Cambridge International AS & A Level
* 8 9 8 2 6 9 4 8 9 0 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory May/June 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (RW/FC) 313065/3
© UCLES 2023 [Turn over
 2

1 Numbers are stored in a computer using floating point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(a) Write the normalised floating‑point representation of the following binary number using this
system:

0101010.111
Show your working.

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Mantissa Exponent

[2]

(b) Describe the reason why the normalised form of the following binary number cannot be
represented accurately using this system.

0101011.111001
...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/M/J/23

 3

2 (a) Describe how records are organised and accessed in a sequential file.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) A hashing algorithm is used to calculate storage locations for records in a random access file.
The algorithm calculates hash values using the function modulus 5.

The function modulus gives the remainder after integer division.

For example, 3003 modulus 5 = 3, so the record key 3003 gives a hash value of 3.

Complete the table to show the remaining hash values.

Record key Hash value

3003 3

1029

7630
[2]

© UCLES 2023 9618/32/M/J/23 [Turn over

 4

3 Several syntax diagrams are shown.

digit letter
0 A

1 C

2 E

3 G

4 I

5 K

6 M

7 O

8 Q

9 S

Y
variable
letter digit

© UCLES 2023 9618/32/M/J/23

 5

(a) State whether each variable is valid or invalid and give a reason for your choice in each case.

9SW ...........................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................

UWY ...........................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................
[2]

(b) <word> contains one or more letters.

Complete the Backus‑Naur Form (BNF) for <word> and use this to complete the BNF for
<variable>.

<word> ::= ............................................................................................................................

...................................................................................................................................................

<variable> ::= ...................................................................................................................

...................................................................................................................................................
[3]

(c) Vehicle registrations must begin with two letters and be followed by one, two or three digits.

Valid letters and digits are shown in the syntax diagrams on page 4.

(i) State an example of a valid vehicle registration.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Draw a syntax diagram for a vehicle registration.

[3]

© UCLES 2023 9618/32/M/J/23 [Turn over

 6

4 Draw one line from each Object‑Oriented Programming (OOP) term to its most appropriate
description.

OOP term Description

methods used to return the value of

a property
Encapsulation

the process of putting data and

methods together as a single unit
Getters
methods used to update the value of
a property
Polymorphism
allows methods to be redefined for
derived classes

Setters
enables the defining of a new class
that inherits from a parent class

[4]

5 (a) Encryption is used to scramble data to make it meaningless if intercepted.

Describe the purpose of quantum cryptography.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain the differences between symmetric and asymmetric cryptography when encrypting
and decrypting data.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/M/J/23

 7

6 (a) Write pseudocode statements to declare the composite data type, TAppointments, to hold
data about patients for a dental clinic. It will include for each patient:

• name (first name and last name)

• date of birth
• telephone number
• date of last appointment
• date of next appointment
• all treatments are complete (yes or no).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(b) This pseudocode algorithm reads dental records stored in a random file using the user‑defined
data type TAppointments and prints the contents of the file, one record at a time.

Complete this file handling pseudocode:

DECLARE DentalRecord : ARRAY[1:250] OF TAppointments

DECLARE DentalFile : STRING
DECLARE Count : INTEGER
DentalFile "DentalFile.dat"
OUTPUT "The file ", DentalFile, " contains these records:"

OPENFILE .................................................................................................................

.......................................................................................... 1

REPEAT
SEEK DentalFile, Count

.....................................................................................................................
OUTPUT DentalRecord[Count]
Count Count + 1

.....................................................................(DentalFile)

.............................................................................................
[5]

© UCLES 2023 9618/32/M/J/23 [Turn over

 8

7 (a) State two examples of where it would be appropriate to use packet switching.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Give four differences between circuit switching and packet switching.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................

3 ................................................................................................................................................

...................................................................................................................................................

4 ................................................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/32/M/J/23

 9

8 (a) Describe the use of pipelining in Reduced Instruction Set Computers (RISC).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The processing of instructions is divided into five stages:

• instruction fetch (IF)

• instruction decode (ID)
• operand fetch (OF)
• instruction execute (IE)
• write back result (WB)

Each stage is carried out using a different register when pipelining is used.

Complete the table to show how a program consisting of six instructions would be completed
using pipelining.

Clock cycles

1 2 3 4 5 6 7 8 9 10 11 12

IF
Processor stages

ID

OF

IE

WB
[4]

© UCLES 2023 9618/32/M/J/23 [Turn over

 10

9 This truth table represents a logic circuit.

INPUT OUTPUT

A B C D Z

0 0 0 0 1

0 0 0 1 1

0 0 1 0 1

0 0 1 1 1

0 1 0 0 0

0 1 0 1 0

0 1 1 0 1

0 1 1 1 1

1 0 0 0 0

1 0 0 1 0

1 0 1 0 0

1 0 1 1 0

1 1 0 0 0

1 1 0 1 0

1 1 1 0 0

1 1 1 1 0

(a) Write the Boolean logic expression that corresponds to the given truth table as the
sum‑of‑products.

Z = ............................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/M/J/23

 11

(b) Complete the Karnaugh map (K‑map) for the given truth table.

AB
CD 00 01 11 10

00

01

11

10

[2]

(c) Draw loop(s) around appropriate group(s) in the K‑map to produce an optimal sum‑of‑products.
[2]

(d) Write the Boolean logic expression from your answer to part (c) as a simplified
sum‑of‑products.

Z = ............................................................................................................................................

............................................................................................................................................. [2]

(e) Use Boolean algebra to give your answer to part (d) in its simplest form.

Z = ...................................................................................................................................... [1]

10 (a) State one category of machine learning.

............................................................................................................................................. [1]

© UCLES 2023 9618/32/M/J/23 [Turn over

 12

(b) Calculate the path that takes the shortest time to travel from the Begin node to the End node,
using the A* algorithm.
Show your working in the table provided.

The first two rows have already been completed.

12

g=5 Begin
h=8 4 11
A 5
D
6 7
7 C
6 B
8 6
2
8 7
E

5
7 G
End

7 1
4

1 F

Cost from
Destination Heuristic Total
Start node start node
node (h) (f = g + h)
(g)
Begin Begin 0 12 12

Begin A 5 8 13

Final path
[5]
© UCLES 2023 9618/32/M/J/23
 13

11 (a) The pseudocode shown represents a queue Abstract Data Type (ADT) with procedures for
initialisation and to add new items. It is incomplete.

CONSTANT MaxLength = 50
DECLARE FrontPointer : INTEGER
DECLARE RearPointer : INTEGER
DECLARE Length : INTEGER
DECLARE Queue : ARRAY[0 : MaxLength – 1] OF STRING

// initialisation of queue
PROCEDURE Initialise
FrontPointer ‑1

.....................................................................................................................

................................................................. 0
ENDPROCEDURE

// adding a new item to the queue

PROCEDURE Enqueue(NewItem : STRING)

IF ............................................................................................. THEN

RearPointer ..................................................................................
IF RearPointer > MaxLength – 1 THEN
RearPointer 0
ENDIF

................................................................................................................
Length Length + 1
ENDIF
ENDPROCEDURE

(i) Study the pseudocode and insert the identifiers to complete this table.

Identifier Data type Description

STRING An array to store the contents of the queue.

INTEGER Points to the last item of the queue.

INTEGER Indicates the number of items in the queue.

INTEGER Points to the first item of the queue.

[2]

(ii) Complete the given pseudocode. [5]

© UCLES 2023 9618/32/M/J/23 [Turn over

 14

(b) Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/M/J/23

 15

BLANK PAGE

© UCLES 2023 9618/32/M/J/23

 16

BLANK PAGE

Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/32/M/J/23

 Cambridge International AS & A Level
* 3 5 5 8 9 5 6 0 0 9 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory May/June 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (KN) 313066/2
© UCLES 2023 [Turn over
 2

1 Numbers are stored in two different computer systems by using floating-point representation.

System 1 uses:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

System 2 uses:

• 8 bits for the mantissa

• 8 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of 113.75 and show how it would be
represented in each of these two systems.

Show your working.

System 1

Mantissa Exponent

System 2

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/33/M/J/23

 3

(b) Explain the problem that occurred in part (a) when representing the number in system 2.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

2 (a) Draw one line from each machine learning category to its most appropriate description.

Machine learning category Description

simulates the data-processing

capabilities of the human brain to
make decisions
Supervised
learning
enables learning by mapping an input
to an output based on example input–
output pairs
Reinforcement
learning
enables information related to errors
produced by the neural network to be
transmitted
Deep
learning
enables learning in an interactive
environment by trial and error using
its own experiences
Unsupervised
learning
enables learning by allowing the
process to discover patterns on its
own that were previously undetected
[4]

(b) Describe the purpose of both the A* algorithm and Dijkstra’s algorithm.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/M/J/23 [Turn over

 4

3 (a) A hashing algorithm is used to calculate storage locations for records in a random access file.
It calculates hash values by using the function modulus 3.

The function modulus gives the remainder after integer division.

For example, 1030 modulus 3 = 1. Therefore, the record key 1030 gives a hash value of 1.

Complete the table to show the remaining hash values.

Record key Hash value

1030 1

1050

1025
[2]

(b) Describe what happens, in relation to the storage or retrieval of a record in the file, when
the calculated hash value is a duplicate of a previously calculated hash value for a different
record key.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2023 9618/33/M/J/23

 5

4 Two descriptions of user-defined data types are given.

Give appropriate type declaration statements for each, including appropriate names.

(a) A data type to hold a set of prime numbers below 20. These prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) A data type to point to a day in the week, for example Monday.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

5 (a) State, with a reason, where it would be appropriate to use circuit switching.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Give two benefits and two drawbacks of circuit switching.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

...................................................................................................................................................

Drawback 1 ...............................................................................................................................

...................................................................................................................................................

Drawback 2 ...............................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/33/M/J/23 [Turn over

 6

6 Several syntax diagrams are shown.

operator digit
+ 0

– 1

* 2

/ 3

symbol
$ 4

% 5

& 6

@ 7

# 8

letter 9
A

password
letter digit symbol

© UCLES 2023 9618/33/M/J/23

 7

(a) State whether each of the following passwords is valid or invalid and give a reason for your
choice.

DPAD99$ ...................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................

DAD#95 .....................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................

ADY123? ...................................................................................................................................

Reason .....................................................................................................................................

...................................................................................................................................................
[3]

(b) Complete the Backus-Naur Form (BNF) for the syntax diagrams shown.

<symbol> ::= ........................................................................................................................

...................................................................................................................................................

<letter> ::= ........................................................................................................................

...................................................................................................................................................
[1]

(c) An identifier begins with one or more letters, followed by zero digits or one digit or more
digits.

Valid letters and digits are shown in the syntax diagrams on page 6.

Draw a syntax diagram for an identifier.

[4]

© UCLES 2023 9618/33/M/J/23 [Turn over

 8

7 (a) Complete the Karnaugh map (K-map) for the following Boolean expression.

Z = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

AB

CD 00 01 11 10

00

01

11

10

[2]

(b) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(c) Write the Boolean logic expression from your answer to part (b) as a simplified
sum-of-products.

Z = ............................................................................................................................................

............................................................................................................................................. [2]

(d) Use Boolean algebra to give your answer to part (c) in its simplest form.

Z = ...................................................................................................................................... [1]

© UCLES 2023 9618/33/M/J/23

 9

8 Outline the characteristics of massively parallel computers.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [3]

9 (a) Encryption is used to alter data into a form that makes it meaningless if intercepted.

Describe the purpose of asymmetric key cryptography.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Identify two benefits and two drawbacks of quantum cryptography.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

...................................................................................................................................................

Drawback 1 ...............................................................................................................................

...................................................................................................................................................

Drawback 2 ...............................................................................................................................

...................................................................................................................................................
[4]

© UCLES 2023 9618/33/M/J/23 [Turn over

 10

10 The pseudocode algorithm shown copies an active accounts text file ActiveFile.txt to an
archive accounts text file ArchiveFile.txt, one line at a time. Any blank lines found in the
active accounts text file are replaced with the words "Account not present" in the archive
accounts text file.

Complete this file-handling pseudocode.

DECLARE Account : STRING

..........................................................................................................................................................

OPENFILE "ArchiveFile.txt" FOR WRITE

WHILE NOT ......................................................................................................................................

READFILE "ActiveFile.txt", Account
IF Account = "" THEN

WRITEFILE "ArchiveFile.txt", " .........................................................................."

ELSE

WRITEFILE "ArchiveFile.txt", ...............................................................................

ENDIF
ENDWHILE

..........................................................................................................................................................
CLOSEFILE "ArchiveFile.txt"
[5]

11 Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the
string data type. This will be implemented using the information in the table.

Identifier Data type Description

FrontPointer INTEGER points to the start of the queue

RearPointer INTEGER points to the end of the queue

Length INTEGER the current size of the queue

Queue STRING 1D array to implement the queue

A constant, with identifier MaxSize, limits the size of the queue to 60 items.

(a) Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and
Queue.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
© UCLES 2023 9618/33/M/J/23
 11

(b) Complete the following pseudocode for the function Dequeue to remove the front item from
the queue.

FUNCTION Dequeue RETURNS STRING

DECLARE Item : STRING

......................................................................................................................... > 0 THEN

Item ← .......................................................................................................................

......................................................................................................................................
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN

....................................................................................................................... ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
[4]

(c) Explain how a new element can be added to the queue if it is implemented using two stacks.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

12 (a) Describe what is meant by recursion.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/M/J/23 [Turn over

 12

(b) A Fibonacci sequence is a series of numbers formed by adding together the two preceding
numbers, for example:

0, 1, 1, 2, …

This function calculates and returns values in the Fibonacci sequence and uses recursion.

FUNCTION Fib(Number : INTEGER) RETURNS INTEGER

IF Number <= 1 THEN
Result ← Number
ELSE
Result ← Fib(Number – 1) + Fib(Number – 2)
ENDIF
RETURN Result
ENDFUNCTION

Complete the trace table for the function when it is called as Fib(5).

Call number Function call Number Result Return value

5

[5]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/33/M/J/23

 Cambridge International AS & A Level
* 6 2 8 1 0 3 5 9 0 4 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory May/June 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages. Any blank pages are indicated.

DC (PQ) 341261
© UCLES 2024 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the denary value of the given normalised floating-point number.

Show your working.

Mantissa Exponent

0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

(b) Calculate the normalised floating-point representation of –102.75 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

© UCLES 2024 9618/31/M/J/24

 3

2 The TCP / IP protocol suite has four layers:

Transport, Application, Link, Internet

(a) Complete the diagram to show the correct order for these layers.

[2]

(b) Describe the function of the Transport layer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Outline one protocol that is associated with the Application layer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

3 (a) Explain what is meant by non-composite and composite data types.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/31/M/J/24 [Turn over

 4

(b) Write pseudocode statements to declare the record data type FootballClub to hold data
about football clubs in a league, to include:

• name of team
• date team joined the league
• main telephone number
• name of the manager
• number of members
• current position in the league.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

4 (a) Describe the sequential method of file access.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how the sequential method of file access is applied to files with serial organisation
and to files with sequential organisation.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/31/M/J/24

 5

5 (a) Write this Reverse Polish Notation (RPN) in infix form:

5 2 + 9 3 - / 3 *

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Write this infix expression in RPN:

((7 + 3) - (2 * 8)) / 6

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Evaluate this RPN expression:

a b - c d + * e /

when

a = 17, b = 5, c = 7, d = 3 and e = 10

Show the changing contents of the stack as the RPN expression is evaluated.

[4]

© UCLES 2024 9618/31/M/J/24 [Turn over

 6

6 The diagram shows a logic circuit.

A Q

P R
B Z

(a) Complete the truth table for the given logic circuit.

Show your working.

Working space
A B C P Q R S Z

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1
[3]

(b) Write the Boolean expression that corresponds to the logic circuit as a sum-of-products.

Z = ............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2024 9618/31/M/J/24

 7

(c) (i) Complete the Karnaugh map (K-map) for the Boolean expression:

A.B.C + A.B.C + A.B.C + A.B.C + A.B.C + A.B.C

BC
00 01 11 10
A

[2]

(ii) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part (c)(ii) as a simplified
sum-of-products.

...........................................................................................................................................

..................................................................................................................................... [1]

7 (a) Describe what is meant by a digital certificate.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Explain the role of a digital certificate in creating a digital signature.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2024 9618/31/M/J/24 [Turn over

 8

8 A declarative programming language is used to represent the features that are available and the
features that are unavailable on different body styles of a car.

01 feature(sunroof).
02 feature(automatic_tailgate).
03 feature(heated_seats).
04 feature(extra_seats).
05 feature(reversing_camera).
06 feature(dashboard_camera).
07 feature(air_conditioning).
08 feature(heated_windscreen).
09 feature(satnav).
10 bodystyle(saloon).
11 bodystyle(hatchback).
12 bodystyle(estate).
13 bodystyle(minivan).
14 bodystyle(convertible).
15 available(sunroof, hatchback).
16 available(sunroof, minivan).
17 available(reversing_camera, hatchback).
18 available(extra_seats, minivan).
19 available(reversing_camera, saloon).
20 unavailable(sunroof, convertible).
21 unavailable(automatic_tailgate, saloon).
22 unavailable(extra_seats, hatchback).

These clauses have the meanings:

Clause Meaning
01 Sunroof is a feature.
10 Saloon is a body style.
15 Sunroof is available on a hatchback.
20 Sunroof is unavailable on a convertible.

(a) Sliding doors is a feature that is available on a minivan but unavailable on a hatchback.

Write additional clauses to represent this information.

23 .............................................................................................................................................

24 .............................................................................................................................................

25 .............................................................................................................................................
[3]

© UCLES 2024 9618/31/M/J/24

 9

(b) Using the variable Options, the goal:

available(Options, saloon)

returns

Options = reversing_camera

Write the result returned by the goal:

available(Options, hatchback)

Options = ........................................................................................................................ [1]

(c) F may be available for B if F is a feature and B is a body style and F is not unavailable for that
body style.

Write this as a rule:

may_choose_option(F, B)

IF .............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

9 Explain what is meant by Deep Learning in relation to Artificial Intelligence (AI).

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [3]

© UCLES 2024 9618/31/M/J/24 [Turn over

 10

10 (a) State a condition that must be true for an array to be searchable for a binary search.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) Complete the given pseudocode to find an item in a 1D array Names of type STRING using a
binary search.

DECLARE Names : ARRAY[1:100000] OF STRING

DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE CurrentItem : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList 1 ←
EndOfList 100000 ←
OUTPUT "Which name do you wish to find? "
INPUT ToFind

...................................................................................................................................................

NotInList ← FALSE
WHILE ................................................ AND ................................................
CurrentItem ←
(TopOfList + EndOfList) DIV 2

IF ........................................................................................................... THEN
Found ← TRUE
ELSE
IF TopOfList >= EndOfList THEN

...........................................................................................................
ELSE
IF ToFind > Names[CurrentItem] THEN

...........................................................................................................
ELSE
EndOfList ←
CurrentItem – 1
ENDIF
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", CurrentItem, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
[5]

© UCLES 2024 9618/31/M/J/24

 11

(c) Describe the performance of a binary search in relation to the number of data items in the
array being searched. Refer to Big O notation in your answer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

11 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) State two features of RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Outline the process of interrupt handling as it could be applied to RISC or CISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(c) Explain how pipelining affects interrupt handling for RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/31/M/J/24

 12

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2024 9618/31/M/J/24

 Cambridge International AS & A Level
* 4 9 7 1 7 0 3 6 1 7 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory May/June 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (DE) 352034/4
© UCLES 2024 [Turn over
 2

1 (a) Describe the effect of changing the allocation of bits used for the mantissa and for the
exponent in a floating-point number with a fixed total number of bits.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Real numbers are stored in a computer, using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

Calculate the normalised floating-point representation of +54.8125 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/32/M/J/24

 3

2 (a) Outline why protocols are essential for communication between computers.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) State the names of two different protocols associated with the sending and receiving of
emails between computers.

Sending ....................................................................................................................................

Receiving ..................................................................................................................................
[2]

(c) Explain the meaning of the phrase:

BitTorrent protocol provides peer-to-peer file sharing.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/32/M/J/24 [Turn over

 4

3 (a) Explain what is meant by the term non-composite data type and give an example of a
non-composite data type.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Example ....................................................................................................................................
[3]

(b) Write pseudocode statements to declare the set data type EvenNumbers to hold this set of
even numbers between 2 and 12:

2, 4, 6, 8, 10, 12

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2024 9618/32/M/J/24

 5

4 Sheila has a customer called Fred. Fred wants to send Sheila a confidential document as part of a
transaction.

Explain how Fred uses asymmetric encryption to send his document securely.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

© UCLES 2024 9618/32/M/J/24 [Turn over

 6

5 (a) Write this infix expression in Reverse Polish Notation (RPN):

(7 – 2 + 8) / (9 – 5)

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Evaluate this RPN expression:

a d + a b + c - *

when

a = 6, b = 3, c = 7 and d = 9

Show the changing contents of the stack as the RPN expression is evaluated.

[4]

(c) Write this RPN expression in infix form:

b a c - + d b + * c /

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/32/M/J/24

 7

6 The diagram shows a logic circuit.

P
A
S

Q
B Z

T
R
C

(a) Complete the truth table for the given logic circuit.
Show your working.

Working space
A B C P Q R S T Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
[3]

(b) Write the Boolean expression that corresponds to the logic circuit as a sum-of-products.

Z = ............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2024 9618/32/M/J/24 [Turn over

 8

(c) (i) Complete the Karnaugh map (K-map) for this Boolean expression:
–– – – – – –– –
A.B.C + A.B.C + A.B.C + A.B.C + A.B.C + A.B.C

BC
A 00 01 11 10

[2]

(ii) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part c(ii) as a simplified
sum-of-products.

...........................................................................................................................................

..................................................................................................................................... [1]

7 (a) Outline what is meant by direct access as a method of file access.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how direct access is used to locate a specific record in sequential files and random
files.

(i) Sequential files ..................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Random files .....................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2024 9618/32/M/J/24

 9

8 (a) Complete the pseudocode to find an item in a 1D array Widgets of type STRING, using a
linear search.

DECLARE Widgets : ARRAY[1:50000] OF STRING

DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE Count : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList 1
EndOfList 50000
OUTPUT "Enter the name of the item you wish to find "
INPUT ToFind

…………………………………………………………………………………………………………………………………
NotInList FALSE
Count TopOfList

WHILE …………………………………………………………… AND ………………………………………………………………………

IF ……………………………………………………………………………………………………………………………… THEN
Found TRUE
ENDIF
Count Count + 1

IF …………………………………………………………………………………………………………………………… THEN
NotInList TRUE
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", Count - 1, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
[4]

(b) Compare the methods used by the linear and binary search algorithms to find an item in an
array. Refer to Big O notation in your answer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2024 9618/32/M/J/24 [Turn over

 10

9 (a) Outline two benefits and two limitations of a virtual machine.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Limitation 1 ...............................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Limitation 2 ...............................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Explain the roles of the host operating system and the guest operating system as used in a
computer system running a virtual machine.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2024 9618/32/M/J/24

 11

10 A declarative programming language is used to allow clients to choose daily activities at the
beach.

01 activity(paddleboarding).
02 activity(sailing).
03 activity(rowing).
04 activity(kayaking).
05 activity(jetskiing).
06 client(stevie).
07 client(antonio).
08 client(henry).
09 client(eliza).
10 client(rebeka).
11 client(danny).
12 client(erik).
13 client(simone).
14 client(petra).
15 client(frankie).
16 choice(petra, rowing).
17 choice(frankie, sailing).
18 choice(erik, sailing).
19 choice(eliza, rowing).
20 choice(stevie, jetskiing).
21 choice(henry, sailing).
22 done(henry, jetskiing).
23 done(rebeka, jetskiing).
24 done(antonio, kayaking).

These clauses have the meanings:

Clause Meaning
01 Paddle boarding is an activity.
06 Stevie is a client.
16 Petra has chosen rowing.
22 Henry has already done jet skiing.

(a) Jane is a client who would like to choose the activity surfing and she has already done sailing.

Write additional clauses to represent this information.

25 .............................................................................................................................................

26 .............................................................................................................................................

27 .............................................................................................................................................

28 .............................................................................................................................................
[4]

© UCLES 2024 9618/32/M/J/24 [Turn over

 12

(b) Using the variable List, the goal:

choice(List, rowing)

returns

List = petra, eliza

Write the result returned by the goal:

choice(List, sailing)

List = .............................................................................................................................. [1]

(c) C is a client who would like to choose A if A is an activity and C has not already done A.

Write this as a rule:

may_choose_activity(C, A)

IF ............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

11 Explain what is meant by Reinforcement Learning in relation to Artificial Intelligence.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [3]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2024 9618/32/M/J/24

 * 0019655539701 *

,

  
,

Cambridge International AS & A Level

¬Wz> 3mKsgy=–<—5 W
¬šš`E¤ifbpŠœŠWBtN‚
¥5u•5•Eu5e¥U5 eUEU
* 0 5 3 4 4 0 8 3 9 9 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory May/June 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages. Any blank pages are indicated.

DC (LK/CGW) 329375/5
© UCLES 2024 [Turn over
 * 0019655539702 *

DO NOT WRITE IN THIS MARGIN

2
,

  
,

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the denary value of the given normalised floating-point number.

Show your working.

Mantissa Exponent

DO NOT WRITE IN THIS MARGIN

0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

(b) Calculate the normalised floating-point representation of –102.75 in this system.

Show your working.

Mantissa Exponent

Working ..................................................................................................................................... DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................
[3]

ĬÕú¾Ġ³íËóçù½Ė¹ĕ·Ğ×
© UCLES 2024 ĬĚĜßÈĨÝÄÙāð÷²ÝòÌÖĂ
ĥĥĥĕõõąĕąĥµĕµÅÅĕĥÕ
9618/33/M/J/24
 * 0019655539703 *
DO NOT WRITE IN THIS MARGIN

3
,

  
,

2 The TCP / IP protocol suite has four layers:

Transport, Application, Link, Internet

(a) Complete the diagram to show the correct order for these layers.
DO NOT WRITE IN THIS MARGIN

[2]

(b) Describe the function of the Transport layer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [2]

(c) Outline one protocol that is associated with the Application layer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]
DO NOT WRITE IN THIS MARGIN

3 (a) Explain what is meant by non-composite and composite data types.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

Ĭ×ú¾Ġ³íËóçù½Ė¹ė·Ğ×
© UCLES 2024 ĬĚěàÀĢá´à÷ā²ĦÕæÌæĂ
ĥĥĕÕµĕĥõĕĕĥĕµååÕõÕ
9618/33/M/J/24 [Turn over
 * 0019655539704 *

DO NOT WRITE IN THIS MARGIN

4
,

  
,

(b) Write pseudocode statements to declare the record data type FootballClub to hold data
about football clubs in a league, to include:

• name of team
• date team joined the league
• main telephone number
• name of the manager
• number of members
• current position in the league.

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

4 (a) Describe the sequential method of file access.

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how the sequential method of file access is applied to files with serial organisation
and to files with sequential organisation.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

ĬÕú¾Ġ³íËóçù½Ė»ĕ·Ġ×
© UCLES 2024 ĬĚěÝÀĬÓµÛùĊ¹ÈùĈÜÎĂ
ĥÕÅÕõĕĥÕõµĕĕõåąÕĥÕ
9618/33/M/J/24
 * 0019655539705 *
DO NOT WRITE IN THIS MARGIN

5
,

  
,

5 (a) Write this Reverse Polish Notation (RPN) in infix form:

5 2 + 9 3 - / 3 *

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
DO NOT WRITE IN THIS MARGIN

(b) Write this infix expression in RPN:

((7 + 3) - (2 * 8)) / 6

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]
DO NOT WRITE IN THIS MARGIN

(c) Evaluate this RPN expression:

a b - c d + * e /

when

a = 17, b = 5, c = 7, d = 3 and e = 10

Show the changing contents of the stack as the RPN expression is evaluated.
DO NOT WRITE IN THIS MARGIN

[4]
DO NOT WRITE IN THIS MARGIN

Ĭ×ú¾Ġ³íËóçù½Ė»ė·Ġ×
© UCLES 2024 ĬĚĜÞÈĞÏÅÞÿ÷ðĔāÔÜÞĂ
ĥÕµĕµõąµĥÅÅĕõÅĥĕõÕ
9618/33/M/J/24 [Turn over
 * 0019655539706 *

DO NOT WRITE IN THIS MARGIN

6
,

  
,

6 The diagram shows a logic circuit.

A Q

P R
B Z

DO NOT WRITE IN THIS MARGIN

S

(a) Complete the truth table for the given logic circuit.

Show your working.

DO NOT WRITE IN THIS MARGIN

Working space
A B C P Q R S Z

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

DO NOT WRITE IN THIS MARGIN

1 1 0

1 1 1
[3]

(b) Write the Boolean expression that corresponds to the logic circuit as a sum-of-products.

Z = ............................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

............................................................................................................................................. [2]

ĬÙú¾Ġ³íËóçù½Ėºė¶Ğ×
© UCLES 2024 ĬĚěÞËĨ·¿æČĆąôù±ôÎĂ
ĥąĕĕµÕąĕååĥĕµÅÅÕåÕ
9618/33/M/J/24
 * 0019655539807 *
DO NOT WRITE IN THIS MARGIN

7
,

 
,

(c) (i) Complete the Karnaugh map (K-map) for the Boolean expression:

A.B.C + A.B.C + A.B.C + A.B.C + A.B.C + A.B.C

BC
00 01 11 10
A

1
DO NOT WRITE IN THIS MARGIN

[2]

(ii) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part (c)(ii) as a simplified
sum-of-products.

...........................................................................................................................................

..................................................................................................................................... [1]
DO NOT WRITE IN THIS MARGIN

7 (a) Describe what is meant by a digital certificate.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(b) Explain the role of a digital certificate in creating a digital signature.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]
DO NOT WRITE IN THIS MARGIN

ĬÛù¿Ġ³íËóçù½Ė¹ė¶Ğ×
© UCLES 2024 ĬĚěàÈīÈéÕĉú²Ë¹±ÄæĂ
ĥµµÕµõåõÅåÅĕõąÅĕĕÕ
9618/33/M/J/24 [Turn over
 * 0019655539808 *

DO NOT WRITE IN THIS MARGIN

8
,

 
,

8 A declarative programming language is used to represent the features that are available and the
features that are unavailable on different body styles of a car.

01 feature(sunroof).
02 feature(automatic_tailgate).
03 feature(heated_seats).
04 feature(extra_seats).
05 feature(reversing_camera).
06 feature(dashboard_camera).
07 feature(air_conditioning).
08 feature(heated_windscreen).

DO NOT WRITE IN THIS MARGIN

09 feature(satnav).
10 bodystyle(saloon).
11 bodystyle(hatchback).
12 bodystyle(estate).
13 bodystyle(minivan).
14 bodystyle(convertible).
15 available(sunroof, hatchback).
16 available(sunroof, minivan).
17 available(reversing_camera, hatchback).
18 available(extra_seats, minivan).
19 available(reversing_camera, saloon).
20 unavailable(sunroof, convertible).

DO NOT WRITE IN THIS MARGIN

21 unavailable(automatic_tailgate, saloon).
22 unavailable(extra_seats, hatchback).

These clauses have the meanings:

Clause Meaning
01 Sunroof is a feature.
10 Saloon is a body style.
15 Sunroof is available on a hatchback.
20 Sunroof is unavailable on a convertible.

DO NOT WRITE IN THIS MARGIN

(a) Sliding doors is a feature that is available on a minivan but unavailable on a hatchback.

Write additional clauses to represent this information.

23 .............................................................................................................................................

24 .............................................................................................................................................

25 .............................................................................................................................................
[3]
DO NOT WRITE IN THIS MARGIN

ĬÙù¿Ġ³íËóçù½Ė»ĕ¶Ġ×
© UCLES 2024 ĬĚěÝÈġ¶àâćñ¹ĩĕēÔÎĂ
ĥąĥÕõõåÕåąµĕµąĥĕąÕ
9618/33/M/J/24
 * 0019655539809 *
DO NOT WRITE IN THIS MARGIN

9
,

 
,

(b) Using the variable Options, the goal:

available(Options, saloon)

returns

Options = reversing_camera

Write the result returned by the goal:

available(Options, hatchback)
DO NOT WRITE IN THIS MARGIN

Options = ........................................................................................................................ [1]

(c) F may be available for B if F is a feature and B is a body style and F is not unavailable for that
body style.

Write this as a rule:

may_choose_option(F, B)

IF .............................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

9 Explain what is meant by Deep Learning in relation to Artificial Intelligence (AI).

..........................................................................................................................................................

..........................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [3]
DO NOT WRITE IN THIS MARGIN

ĬÛù¿Ġ³íËóçù½Ė»ė¶Ġ×
© UCLES 2024 ĬĚĜÞÀħºÐ×ñĀð­ĝÇÔÞĂ
ĥąĕĕµĕŵµõĥĕµĥąÕĕÕ
9618/33/M/J/24 [Turn over
 * 0019655539810 *

DO NOT WRITE IN THIS MARGIN

10
,

  
,

10 (a) State a condition that must be true for an array to be searchable for a binary search.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) Complete the given pseudocode to find an item in a 1D array Names of type STRING using a
binary search.

DECLARE Names : ARRAY[1:100000] OF STRING

DECLARE TopOfList : INTEGER

DO NOT WRITE IN THIS MARGIN

DECLARE EndOfList : INTEGER
DECLARE CurrentItem : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList 1 ←
EndOfList 100000 ←
OUTPUT "Which name do you wish to find? "
INPUT ToFind

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

NotInList ← FALSE
WHILE ................................................ AND ................................................
CurrentItem ←
(TopOfList + EndOfList) DIV 2

IF ........................................................................................................... THEN
Found ← TRUE
ELSE
IF TopOfList >= EndOfList THEN

...........................................................................................................
ELSE

DO NOT WRITE IN THIS MARGIN

IF ToFind > Names[CurrentItem] THEN

...........................................................................................................
ELSE
EndOfList ←
CurrentItem – 1
ENDIF
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", CurrentItem, " in array"
ELSE
OUTPUT "Item not in array"
DO NOT WRITE IN THIS MARGIN

ENDIF
[5]

ĬÙù¿Ġ³íËóçù½Ėºĕ¸Ğ×
© UCLES 2024 ĬĚĚݽģ®ºàĀúēąė÷ĬæĂ
ĥÕąĕõõąÕąµµÕµåĥĕµÕ
9618/33/M/J/24
 * 0019655539811 *
DO NOT WRITE IN THIS MARGIN

11
,

  ,

(c) Describe the performance of a binary search in relation to the number of data items in the
array being searched. Refer to Big O notation in your answer.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]
DO NOT WRITE IN THIS MARGIN

11 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) State two features of RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [2]

(b) Outline the process of interrupt handling as it could be applied to RISC or CISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(c) Explain how pipelining affects interrupt handling for RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

............................................................................................................................................. [3]

ĬÛù¿Ġ³íËóçù½Ėºė¸Ğ×
© UCLES 2024 ĬĚęÞÅĥ²ÊÙúćÖÑğãĬÖĂ
ĥÕõÕµĕĥµĕÅĥÕµÅąÕåÕ
9618/33/M/J/24
 * 0019655539812 *

DO NOT WRITE IN THIS MARGIN

12
,

  ,

BLANK PAGE

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.
ĬÙù¿Ġ³íËóçù½Ė¼ĕ¸Ġ×
© UCLES 2024 ĬĚęßÅğÄ¿ÞøĀÍóÃāüÞĂ
ĥĥåÕõĕĥĕõĥĕÕõÅåÕµÕ
9618/33/M/J/24
 Cambridge International AS & A Level
* 6 2 5 8 7 8 7 9 8 3 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory October/November 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (SLM) 220617
© UCLES 2021 [Turn over
 2

1 (a) Numbers are stored in a computer using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(i) Write the normalised floating-point representation of the following unsigned binary
number using this system.

1011100.011001
Working .............................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

Mantissa Exponent

[2]

(ii) State the consequence of storing the binary number in part (a)(i) as a floating-point
number in this system. Justify your answer.

Consequence ....................................................................................................................

...........................................................................................................................................

Justification .......................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

(b) Explain the reason why binary numbers are stored in normalised form.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
© UCLES 2021 9618/31/O/N/21
 3

2 Draw one line from each programming paradigm to its most appropriate description.

Programming paradigm Description

Programs using the instruction set of a

processor

Declarative
Programs based on events such as user
actions or sensor outputs

Imperative
Programs using the concepts of class,
inheritance, encapsulation and
polymorphism
Low-level

Programs with an explicit sequence of

commands that update the program state,
Object-oriented with or without procedure calls

Programs that specify the desired result

rather than how to get to it

[4]

3 Enumerated and pointer are two non-composite data types.

(a) Write pseudocode to create an enumerated type called Parts to include these parts sold in
a computer shop:

Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Write pseudocode to create a pointer type called SelectParts that will reference the
memory location in which the current part name is stored.

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/31/O/N/21 [Turn over

 4

4 The following syntax diagrams for a particular programming language show the syntax of:

• a digit
• a capital letter
• a character.

digit capital letter

0 A

1 E

2 I

3 O

4 U

5 character
$

6
%

7
&

8
*

9
#

(a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character.

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/31/O/N/21

 5

(b) A password must begin with a character and be followed by one or more digits or capital
letters.

(i) State an example of a valid password.

..................................................................................................................................... [1]

(ii) A valid password is represented by the syntax diagram:

password
character digit

capital letter

Write the BNF notation of the syntax diagram for password.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2021 9618/31/O/N/21 [Turn over

 6

5 (a) Compare sequential and serial methods of file organisation.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(b) State the most suitable method of file access when a record is referenced by a unique
address on a disk-type storage medium.

............................................................................................................................................. [1]

(c) State the most suitable method of file access when a bank stores its data records in ascending
order of account number.

............................................................................................................................................. [1]

© UCLES 2021 9618/31/O/N/21

 7

6 (a) Explain how packet switching is used to transfer messages across the internet.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [5]

(b) Outline the function of a router in packet switching.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2021 9618/31/O/N/21 [Turn over

 8

7 (a) Write the Boolean expression that corresponds to the given truth table as a sum-of-products.

INPUT OUTPUT

A B C D Z

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

1 0 1 0 0

1 0 1 1 1

1 1 0 0 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 1

Z = ............................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2021 9618/31/O/N/21

 9

(b) (i) Complete the Karnaugh map (K-map) for the given truth table.

AB

CD 00 01 11 10

00

01

11

10

[2]

(ii) Draw loop(s) around appropriate group(s) of 1s in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part b(ii) as a simplified
sum-of-products.

Z = .....................................................................................................................................

..................................................................................................................................... [2]

(iv) Write the simplified Boolean expression for your answer to part b(iii).

Z = .....................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2021 9618/31/O/N/21 [Turn over

 10

8 (a) Describe the purpose of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS)
protocols.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how SSL/TLS protocols are used when a client-server communication is initiated.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/31/O/N/21

 11

9 (a) The diagram shown represents an artificial neural network.

Output
Layer
Input
Layer
Hidden Hidden
Layer 1 Hidden Layer 3
Layer 2

(i) State the reason for having multiple hidden layers in an artificial neural network.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Explain how artificial neural networks enable machine learning.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2021 9618/31/O/N/21 [Turn over

 12

(b) Find the shortest path between the Home and School nodes using the A* algorithm.
Show your working in the table provided.

The first two rows in the table have been completed.

14

h = 10 Home 9
g=1 4
A 5 C
3
7
B 6
2
6
D 6
3
7
F
1
2
3
E
3 5
School

Node Cost from Home node (g) Heuristic (h) Total (f = g + h)

Home 0 14 14

A 1 10 11

Final path
[5]

© UCLES 2021 9618/31/O/N/21

 13

10 (a) State three essential features of recursion.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................

3 ................................................................................................................................................

...................................................................................................................................................
[3]

(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement
recursion.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(c) Identify two ADTs other than a stack.

1 ................................................................................................................................................

2 ................................................................................................................................................
[2]

© UCLES 2021 9618/31/O/N/21 [Turn over

 14

(d) The function StackFull() checks whether a stack is full.

The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.

FUNCTION StackFull() RETURNS BOOLEAN

IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION

An algorithm AddInteger is required to add a new integer data element to a stack.

The stack is implemented as an array ArrayStack.

The function AddInteger() calls StackFull() and returns an appropriate message.

Complete the pseudocode for the function AddInteger().

FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

ENDFUNCTION
[5]

© UCLES 2021 9618/31/O/N/21

 15

BLANK PAGE

© UCLES 2021 9618/31/O/N/21

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/31/O/N/21

 Cambridge International AS & A Level
* 7 9 2 0 7 5 1 8 6 5 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (RW/SW) 206388/2
© UCLES 2021 [Turn over
 2

1 (a) Numbers are stored in a computer using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(i) Write the normalised floating-point representation of the following unsigned binary
number using this system.

1011100.011001
Working .............................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

Mantissa Exponent

[2]

(ii) State the consequence of storing the binary number in part (a)(i) as a floating-point
number in this system. Justify your answer.

Consequence ....................................................................................................................

...........................................................................................................................................

Justification .......................................................................................................................

...........................................................................................................................................

...........................................................................................................................................
[2]

(b) Explain the reason why binary numbers are stored in normalised form.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
© UCLES 2021 9618/32/O/N/21
 3

2 Draw one line from each programming paradigm to its most appropriate description.

Programming paradigm Description

Programs using the instruction set of a

processor

Declarative
Programs based on events such as user
actions or sensor outputs

Imperative
Programs using the concepts of class,
inheritance, encapsulation and
polymorphism
Low-level

Programs with an explicit sequence of

commands that update the program state,
Object-oriented with or without procedure calls

Programs that specify the desired result

rather than how to get to it

[4]

3 Enumerated and pointer are two non-composite data types.

(a) Write pseudocode to create an enumerated type called Parts to include these parts sold in
a computer shop:

Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Write pseudocode to create a pointer type called SelectParts that will reference the
memory location in which the current part name is stored.

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/32/O/N/21 [Turn over

 4

4 The following syntax diagrams for a particular programming language show the syntax of:

• a digit
• a capital letter
• a character.

digit capital letter

0 A

1 E

2 I

3 O

4 U

5 character
$

6
%

7
&

8
*

9
#

(a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character.

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2021 9618/32/O/N/21

 5

(b) A password must begin with a character and be followed by one or more digits or capital
letters.

(i) State an example of a valid password.

..................................................................................................................................... [1]

(ii) A valid password is represented by the syntax diagram:

password
character digit

capital letter

Write the BNF notation of the syntax diagram for password.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2021 9618/32/O/N/21 [Turn over

 6

5 (a) Compare sequential and serial methods of file organisation.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(b) State the most suitable method of file access when a record is referenced by a unique
address on a disk-type storage medium.

............................................................................................................................................. [1]

(c) State the most suitable method of file access when a bank stores its data records in ascending
order of account number.

............................................................................................................................................. [1]

© UCLES 2021 9618/32/O/N/21

 7

6 (a) Explain how packet switching is used to transfer messages across the internet.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [5]

(b) Outline the function of a router in packet switching.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2021 9618/32/O/N/21 [Turn over

 8

7 (a) Write the Boolean expression that corresponds to the given truth table as a sum-of-products.

INPUT OUTPUT

A B C D Z

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

1 0 1 0 0

1 0 1 1 1

1 1 0 0 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 1

Z = ............................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2021 9618/32/O/N/21

 9

(b) (i) Complete the Karnaugh map (K-map) for the given truth table.

AB

CD 00 01 11 10

00

01

11

10

[2]

(ii) Draw loop(s) around appropriate group(s) of 1s in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part b(ii) as a simplified
sum-of-products.

Z = .....................................................................................................................................

..................................................................................................................................... [2]

(iv) Write the simplified Boolean expression for your answer to part b(iii).

Z = .....................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2021 9618/32/O/N/21 [Turn over

 10

8 (a) Describe the purpose of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS)
protocols.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how SSL/TLS protocols are used when a client-server communication is initiated.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2021 9618/32/O/N/21

 11

9 (a) The diagram shown represents an artificial neural network.

Output
Layer
Input
Layer
Hidden Hidden
Layer 1 Hidden Layer 3
Layer 2

(i) State the reason for having multiple hidden layers in an artificial neural network.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Explain how artificial neural networks enable machine learning.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [4]

© UCLES 2021 9618/32/O/N/21 [Turn over

 12

(b) Find the shortest path between the Home and School nodes using the A* algorithm.
Show your working in the table provided.

The first two rows in the table have been completed.

14

h = 10 Home 9
g=1 4
A 5 C
3
7
B 6
2
6
D 6
3
7
F
1
2
3
E
3 5
School

Node Cost from Home node (g) Heuristic (h) Total (f = g + h)

Home 0 14 14

A 1 10 11

Final path
[5]

© UCLES 2021 9618/32/O/N/21

 13

10 (a) State three essential features of recursion.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................

3 ................................................................................................................................................

...................................................................................................................................................
[3]

(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement
recursion.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(c) Identify two ADTs other than a stack.

1 ................................................................................................................................................

2 ................................................................................................................................................
[2]

© UCLES 2021 9618/32/O/N/21 [Turn over

 14

(d) The function StackFull() checks whether a stack is full.

The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.

FUNCTION StackFull() RETURNS BOOLEAN

IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION

An algorithm AddInteger is required to add a new integer data element to a stack.

The stack is implemented as an array ArrayStack.

The function AddInteger() calls StackFull() and returns an appropriate message.

Complete the pseudocode for the function AddInteger().

FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

ENDFUNCTION
[5]

© UCLES 2021 9618/32/O/N/21

 15

BLANK PAGE

© UCLES 2021 9618/32/O/N/21

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/32/O/N/21

 Cambridge International AS & A Level
* 4 9 1 1 3 9 2 1 4 2 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory October/November 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages. Any blank pages are indicated.

DC (LK/CGW) 302515/4
© UCLES 2022 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 8 bits for the mantissa

• 8 bits for the exponent
• two’s complement form for both mantissa and exponent.

(a) Write the normalised floating-point representation of +202 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Write the normalised floating-point representation of –202 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

© UCLES 2022 9618/31/O/N/22

 3

(c) A binary number is stored in the computer system.

Mantissa Exponent

0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0

(i) State why the number is not normalised.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Write the normalised floating-point representation of the number.

Mantissa Exponent

[2]

2 Outline the functions of the Transport and Internet layers of the TCP/IP protocol suite.

Transport layer .................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Internet layer ....................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[5]

© UCLES 2022 9618/31/O/N/22 [Turn over

 4

3 (a) State what is meant by the term enumerated data type.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) State what is meant by the term pointer data type.

...................................................................................................................................................

............................................................................................................................................. [1]

(c) The months of the year are: January, February, March, April, May, June, July, August,
September, October, November and December.

Write the pseudocode statement to define the data type Quarter1, to hold the names of the
first three months of a year.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(d) The composite data type Pet is used to store data about the various pets of a group of
students. It uses these fields:

Field name Data type

PetName String
AnimalType String
PetAge Integer
PetGender Char
OwnerName String

(i) Write the pseudocode statement to set up a variable for one record of the composite
data type Pet.

...........................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2022 9618/31/O/N/22

 5

(ii) Write pseudocode to store the details of the following pet, in the variable you set up in
part (d)(i).

PetName AnimalType PetAge PetGender OwnerName

Tibbles Cat 8 M Jasmine Smith

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

4 Draw one line to connect each stage of compilation to its most appropriate description.

Stage of compilation Description

minimising a program’s execution time and

memory requirement

Lexical analysis
converting an intermediate representation of
source code into an executable form

Syntax analysis
converting a sequence of characters into a
sequence of tokens

Code generation
directly executing instructions written in a
scripting language

Optimisation
using parsing algorithms to interpret the
meaning of a sequence of tokens

[4]

© UCLES 2022 9618/31/O/N/22 [Turn over

 6

5 (a) Write the infix expression in Reverse Polish Notation (RPN).

a * b + b - d + 15

...................................................................................................................................................

............................................................................................................................................. [1]

(b) (i) Write the RPN expression in infix form.

a b - c d + * a /

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Evaluate your infix expression from part (b)(i) when a = 5, b = 10, c = 27 and d = 12.

...........................................................................................................................................

..................................................................................................................................... [1]

6 A message is encrypted using a private key and sent to an individual using asymmetric encryption.

(a) State what is meant by a private key.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Describe the process of asymmetric encryption.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/31/O/N/22

 7

(c) Explain how a digital signature is used to verify a message when it is received.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

7 (a) Complete the Karnaugh map (K-map) for the Boolean expression.

Z = Ā. B. C̄. D̄ + Ā. B. C̄. D + A. B. C̄. D̄ + A. B. C̄. D + A. B̄. C̄. D̄ + A. B̄. C̄. D

AB

CD 00 01 11 10

00

01

11

10

[2]

(b) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(c) Write the Boolean expression from your answer to part (b) as a simplified sum-of-products.
Use Boolean algebra to give your answer in its simplest form.

Simplified sum-of-products

Z = ............................................................................................................................................

Simplest form

Z = ............................................................................................................................................
[3]

© UCLES 2022 9618/31/O/N/22 [Turn over

 8

8 Virtual memory, paging and segmentation are used in memory management.

(a) Explain what is meant by virtual memory.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) State one difference between paging and segmentation in the way memory is divided.

...................................................................................................................................................

............................................................................................................................................. [1]

9 Deep learning is used in Artificial Intelligence (AI).

(a) Describe what is meant by deep learning.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Outline the reasons for using deep learning.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/31/O/N/22

 9

10 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) Tick (3) one box in each row to show if the statement applies to RISC or CISC processors.

Statement RISC CISC

uses a smaller instruction set
uses single-cycle instructions and limited addressing modes
uses fewer general-purpose registers
uses both hardwired and micro-coded control unit
uses a system where cache is split between data and
instructions
[2]

(b) Describe the process of pipelining during the fetch-execute cycle in RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2022 9618/31/O/N/22 [Turn over

 10

11 (a) Define these Object-Oriented Programming (OOP) terms:

Instance ....................................................................................................................................

...................................................................................................................................................

Inheritance ................................................................................................................................

...................................................................................................................................................

Polymorphism ...........................................................................................................................

...................................................................................................................................................
[3]

(b) In OOP, a class contains attributes and methods.

Complete the pseudocode for the class Car to enable objects to be created. The class needs
to include:

• string attributes to store the make, model, body type and fuel type
• an integer attribute to store the number of cars of that type built.

The attributes must be available only through the methods of the class.

CLASS .....................................

PRIVATE Make : STRING

PRIVATE ................................................................

................................................................................

................................................................................

................................................................................

PUBLIC PROCEDURE New(CarMake : STRING, ................................................... ,

.....................................................)

Make ← ......................................
Model ← ......................................

BodyType ← CarBodyType

Fuel ← ""

NumberBuilt ← 0

ENDPROCEDURE

GetFuel()

GetNumberBuilt()

.....................................
[5]
© UCLES 2022 9618/31/O/N/22
 11

12 (a) The array Names[0:99] is in alphabetical order.

Complete this pseudocode binary search algorithm.

Lower ←0
......................................................................................................
Mid ← 0
Exit ← FALSE
OUTPUT "Enter the name to be found "
INPUT Target
REPEAT

....................................................................................................... THEN

OUTPUT Target, " does not exist"

Exit ←
TRUE
ENDIF
Mid ←Lower + (Upper – Lower + 1) DIV 2
IF Names[Mid] < Target THEN

Lower ←
.....................................................................................................
ENDIF
IF Names[Mid] > Target THEN

.....................................................................................................
ENDIF

...................................................................................................... THEN
OUTPUT Target, " was found at location ", Mid
Exit ← TRUE
ENDIF

......................................................................................................
[6]

(b) Big O notation is used to classify efficiency of algorithms.

The Big O notation for time complexity in a binary search is O(log n).

(i) State the Big O notation for time complexity of a linear search.

..................................................................................................................................... [1]

(ii) Describe the meaning of O(log n) as it applies to a binary search algorithm.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/31/O/N/22

 12

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/31/O/N/22

 Cambridge International AS & A Level
* 9 7 4 0 2 6 7 5 7 0 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages. Any blank pages are indicated.

DC (RW/CGW) 302516/4
© UCLES 2022 [Turn over
 2

1 Normalised floating-point numbers are stored in a computer system using two’s complement for
both the mantissa and the exponent with:

• 11 bits for the mantissa

• 5 bits for the exponent.

(a) Write the largest positive two’s complement binary number that can be stored in this system.

Mantissa Exponent

[1]

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

(c) State when underflow occurs in a binary floating-point system.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/32/O/N/22

 3

2 Lexical analysis and syntax analysis are stages in the compilation of a program.

(a) Identify two other stages that take place during the compilation of a program.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................
[2]

(b) Outline the purpose of syntax analysis.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

3 (a) Explain why a protocol is used in communication between computers.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) The TCP/IP protocol implementation can be viewed as a stack.

Complete the diagram for the TCP/IP protocol stack.

Transport

Link
[2]

(c) Describe the purpose of the IMAP protocol.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]
© UCLES 2022 9618/32/O/N/22 [Turn over
 4

4 A program to manage regular flight details at an airport requires some user-defined data types.

(a) Write pseudocode statements to declare the enumerated data type Aircraft to hold data
about the types of aircraft used for a flight.

These types of aircraft are: C300, C350, D242, E757, X380.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Write pseudocode statements to declare the composite data type Flight to hold data about
flights to a specific destination. These include:

• flight number, which could be any combination of letters and numbers

• destination
• date of departure
• type of aircraft used.

Use the enumerated data type you created in part (a).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(c) (i) Write the pseudocode statement to set up a variable for one record of the composite
data type Flight.

...........................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2022 9618/32/O/N/22

 5

(ii) Write pseudocode to store the details of the following flight in the variable you set up in
part (c)(i).

Field Data
flight number XA782
destination Cambridge
date of departure 12/12/2022
type of aircraft used C350

Use the field names you created in part (b).

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

5 Describe what is meant by a virtual machine.

Include in your answer two benefits and two drawbacks of using a virtual machine.

Description .......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Benefit 1 ...........................................................................................................................................

..........................................................................................................................................................

Benefit 2 ...........................................................................................................................................

..........................................................................................................................................................

Drawback 1 ......................................................................................................................................

..........................................................................................................................................................

Drawback 2 ......................................................................................................................................

..........................................................................................................................................................
[6]

© UCLES 2022 9618/32/O/N/22 [Turn over

 6

6 (a) State two differences between symmetric and asymmetric encryption.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain the process by which an organisation may acquire its digital certificate.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

7 Supervised and unsupervised learning are two categories of machine learning.

Describe supervised learning and unsupervised learning.

Supervised learning .........................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Unsupervised learning .....................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2022 9618/32/O/N/22

 7

8 (a) Draw a logic circuit for an SR flip-flop and label the inputs.

.................

Q̄

.................

[4]

(b) State the purpose of a flip-flop.

...................................................................................................................................................

............................................................................................................................................. [1]

(c) Simplify the following expression using Boolean algebra, including De Morgan’s laws.
Show your working.

(A.B).(A.C).(B.D)

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

© UCLES 2022 9618/32/O/N/22 [Turn over

 8

9 (a) Explain the need for scheduling in process management.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Describe these scheduling routines and identify a benefit for each one.

Shortest job first ........................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Round robin ..............................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

First come first served ..............................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[6]

© UCLES 2022 9618/32/O/N/22

 9

10 (a) Define these Object-Oriented Programming (OOP) terms:

Encapsulation ...........................................................................................................................

...................................................................................................................................................

Getter ........................................................................................................................................

...................................................................................................................................................

Setter ........................................................................................................................................

...................................................................................................................................................
[3]

(b) A school has a program written using OOP to maintain its staff and student records.

The object SubstituteTeacher allows the details of the school’s substitute teachers to be
stored. This includes their full name, telephone number and whether or not they are in school
today. For example:

SubName Sarah Jones

Telephone 01223658721
InSchool TRUE

Complete the diagram for the object SubstituteTeacher, including appropriate properties
and their getters and setters.

SubstituteTeacher
SubName : STRING

....................................................................................................

InSchool : BOOLEAN

....................................................................................................

SetTelephone(Tel : STRING)

....................................................................................................

GetSubName()

....................................................................................................

....................................................................................................

[3]

© UCLES 2022 9618/32/O/N/22 [Turn over

 10

11 A simplified linked list is used to store the names of flowers in alphabetical order. It is implemented
using two 1D arrays:

• Flower stores the names of the flowers.

• NextPointer stores the pointer to the next flower name in the list.

HeadPointer indicates the index of the first flower name in the linked list.

HeadPointer 6

When the end of the linked list is reached, the next pointer has the value of 0.

The following table shows the initial content of the arrays.

Index Flower NextPointer

1 Rose 7
2 Marigold 1
3 Foxglove 10
4 Iris 9
5 Daisy 3
6 Dahlia 5
7 Saxifrage 0
8 Lupin 2
9 Lily 8
10 Hydrangea 4

(a) Several flower names have been deleted from the linked list. These are crossed out in the
following table.

Complete the table to show the new values of HeadPointer and NextPointer to keep the
remaining flower names in alphabetical order.

HeadPointer

Index Flower NextPointer

1 Rose
2 Marigold
3 Foxglove
4 Iris
5 Daisy
6 Dahlia
7 Saxifrage
8 Lupin
9 Lily
10 Hydrangea
[3]
© UCLES 2022 9618/32/O/N/22
 11

(b) Complete the pseudocode algorithm so that it achieves the following when applied to the
arrays:

• The flower name is input.

• The linked list is searched, in order, for the flower name.
• If the flower name is found, an appropriate message is output to indicate it has been
found.
• If the flower name is not found, an appropriate message is output to indicate it has not
been found.
• The algorithm terminates when the next pointer value is 0.

Pointer HeadPointer
Found 0
OUTPUT "Enter a flower name "

………………………………………………………………….

………………………………………………………………….
IF Flower[Pointer] = FlowerName THEN
Found Pointer
Pointer 0
ELSE

………………………………………………………………….
ENDIF
ENDWHILE

………………………………………………………………….
OUTPUT Flower[Found], " is found"
ELSE

………………………………………………………………….
ENDIF
[5]

(c) Explain how you could improve the simplified linked list structure.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/32/O/N/22

 12

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/32/O/N/22

 Cambridge International AS & A Level
* 7 6 6 6 3 6 3 0 7 4 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory October/November 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages. Any blank pages are indicated.

DC (DE) 320392
© UCLES 2022 [Turn over
 2

1 Real numbers are stored in a computer system using floating-point representation with:

• 8 bits for the mantissa

• 8 bits for the exponent
• two’s complement form for both mantissa and exponent.

(a) Write the normalised floating-point representation of +202 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Write the normalised floating-point representation of –202 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

© UCLES 2022 9618/33/O/N/22

 3

(c) A binary number is stored in the computer system.

Mantissa Exponent

0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0

(i) State why the number is not normalised.

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Write the normalised floating-point representation of the number.

Mantissa Exponent

[2]

2 Outline the functions of the Transport and Internet layers of the TCP/IP protocol suite.

Transport layer .................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Internet layer ....................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[5]

© UCLES 2022 9618/33/O/N/22 [Turn over

 4

3 (a) State what is meant by the term enumerated data type.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) State what is meant by the term pointer data type.

...................................................................................................................................................

............................................................................................................................................. [1]

(c) The months of the year are: January, February, March, April, May, June, July, August,
September, October, November and December.

Write the pseudocode statement to define the data type Quarter1, to hold the names of the
first three months of a year.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(d) The composite data type Pet is used to store data about the various pets of a group of
students. It uses these fields:

Field name Data type

PetName String
AnimalType String
PetAge Integer
PetGender Char
OwnerName String

(i) Write the pseudocode statement to set up a variable for one record of the composite
data type Pet.

...........................................................................................................................................

..................................................................................................................................... [1]

© UCLES 2022 9618/33/O/N/22

 5

(ii) Write pseudocode to store the details of the following pet, in the variable you set up in
part (d)(i).

PetName AnimalType PetAge PetGender OwnerName

Tibbles Cat 8 M Jasmine Smith

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [3]

4 Draw one line to connect each stage of compilation to its most appropriate description.

Stage of compilation Description

minimising a program’s execution time and

memory requirement

Lexical analysis
converting an intermediate representation of
source code into an executable form

Syntax analysis
converting a sequence of characters into a
sequence of tokens

Code generation
directly executing instructions written in a
scripting language

Optimisation
using parsing algorithms to interpret the
meaning of a sequence of tokens

[4]

© UCLES 2022 9618/33/O/N/22 [Turn over

 6

5 (a) Write the infix expression in Reverse Polish Notation (RPN).

a * b + b - d + 15

...................................................................................................................................................

............................................................................................................................................. [1]

(b) (i) Write the RPN expression in infix form.

a b - c d + * a /

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Evaluate your infix expression from part (b)(i) when a = 5, b = 10, c = 27 and d = 12.

...........................................................................................................................................

..................................................................................................................................... [1]

6 A message is encrypted using a private key and sent to an individual using asymmetric encryption.

(a) State what is meant by a private key.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Describe the process of asymmetric encryption.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/33/O/N/22

 7

(c) Explain how a digital signature is used to verify a message when it is received.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

7 (a) Complete the Karnaugh map (K-map) for the Boolean expression.

Z = Ā. B. C̄. D̄ + Ā. B. C̄. D + A. B. C̄. D̄ + A. B. C̄. D + A. B̄. C̄. D̄ + A. B̄. C̄. D

AB

CD 00 01 11 10

00

01

11

10

[2]

(b) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal
sum-of-products. [2]

(c) Write the Boolean expression from your answer to part (b) as a simplified sum-of-products.
Use Boolean algebra to give your answer in its simplest form.

Simplified sum-of-products

Z = ............................................................................................................................................

Simplest form

Z = ............................................................................................................................................
[3]

© UCLES 2022 9618/33/O/N/22 [Turn over

 8

8 Virtual memory, paging and segmentation are used in memory management.

(a) Explain what is meant by virtual memory.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) State one difference between paging and segmentation in the way memory is divided.

...................................................................................................................................................

............................................................................................................................................. [1]

9 Deep learning is used in Artificial Intelligence (AI).

(a) Describe what is meant by deep learning.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Outline the reasons for using deep learning.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2022 9618/33/O/N/22

 9

10 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are
two types of processor.

(a) Tick (3) one box in each row to show if the statement applies to RISC or CISC processors.

Statement RISC CISC

uses a smaller instruction set
uses single-cycle instructions and limited addressing modes
uses fewer general-purpose registers
uses both hardwired and micro-coded control unit
uses a system where cache is split between data and
instructions
[2]

(b) Describe the process of pipelining during the fetch-execute cycle in RISC processors.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2022 9618/33/O/N/22 [Turn over

 10

11 (a) Define these Object-Oriented Programming (OOP) terms:

Instance ....................................................................................................................................

...................................................................................................................................................

Inheritance ................................................................................................................................

...................................................................................................................................................

Polymorphism ...........................................................................................................................

...................................................................................................................................................
[3]

(b) In OOP, a class contains attributes and methods.

Complete the pseudocode for the class Car to enable objects to be created. The class needs
to include:

• string attributes to store the make, model, body type and fuel type
• an integer attribute to store the number of cars of that type built.

The attributes must be available only through the methods of the class.

CLASS .....................................

PRIVATE Make : STRING

PRIVATE ................................................................

................................................................................

................................................................................

................................................................................

PUBLIC PROCEDURE New(CarMake : STRING, ................................................... ,

.....................................................)

Make ← ......................................
Model ← ......................................

BodyType ← CarBodyType

Fuel ← ""

NumberBuilt ← 0

ENDPROCEDURE

GetFuel()

GetNumberBuilt()

.....................................
[5]
© UCLES 2022 9618/33/O/N/22
 11

12 (a) The array Names[0:99] is in alphabetical order.

Complete this pseudocode binary search algorithm.

Lower ←0
......................................................................................................
Mid ← 0
Exit ← FALSE
OUTPUT "Enter the name to be found "
INPUT Target
REPEAT

....................................................................................................... THEN

OUTPUT Target, " does not exist"

Exit ←
TRUE
ENDIF
Mid ←Lower + (Upper – Lower + 1) DIV 2
IF Names[Mid] < Target THEN

Lower ←
.....................................................................................................
ENDIF
IF Names[Mid] > Target THEN

.....................................................................................................
ENDIF

...................................................................................................... THEN
OUTPUT Target, " was found at location ", Mid
Exit ← TRUE
ENDIF

......................................................................................................
[6]

(b) Big O notation is used to classify efficiency of algorithms.

The Big O notation for time complexity in a binary search is O(log n).

(i) State the Big O notation for time complexity of a linear search.

..................................................................................................................................... [1]

(ii) Describe the meaning of O(log n) as it applies to a binary search algorithm.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]

© UCLES 2022 9618/33/O/N/22

 12

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2022 9618/33/O/N/22

 Cambridge International AS & A Level
* 1 6 1 2 7 9 9 2 0 7 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory October/November 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (PQ/CB) 318339/3
© UCLES 2023 [Turn over
 2

1 Real numbers are stored in a computer using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(a) Write the normalised floating-point representation of +65.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Explain the problem that will occur in storing the normalised floating-point representation of
+65.20 in this system.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/O/N/23

 3

2 (a) Draw one line to connect each protocol to its most appropriate use.

Protocol Use

to provide peer-to-peer file sharing

HTTP

when retrieving email messages from a

mail server over a TCP/IP connection
BitTorrent

when transmitting hypertext documents

SMTP

to map MAC addresses onto IP addresses

IMAP
when sending email messages towards
the intended destination

[4]

(b) Outline the purpose of the Link layer in the TCP / IP protocol suite.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

3 Describe what is meant by enumerated and pointer data types.

Enumerated ......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Pointer ..............................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2023 9618/31/O/N/23 [Turn over

 4

4 (a) Describe sequential and random methods of file organisation.

Sequential file organisation .......................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Random file organisation ..........................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Outline the process of sequential access for serial and sequential files.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

5 Describe the features of SISD and MIMD computer architectures.

SISD .................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

MIMD ................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2023 9618/31/O/N/23

 5

BLANK PAGE

© UCLES 2023 9618/31/O/N/23 [Turn over

 6

6 This diagram represents a logic circuit.

A
B Z
C

(a) Complete the truth table for the given logic circuit.

Working space
A B C D Z

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1
[3]

© UCLES 2023 9618/31/O/N/23

 7

(b) Simplify the given Boolean expression using Boolean algebra.

Show your working.

Y = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

7 (a) A student buys a new computer.

State one benefit to the student of a user interface and give an example.

Benefit ......................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Example ....................................................................................................................................

...................................................................................................................................................
[2]

(b) Two of the process states are the running state and the ready state.

Identify one other process state.

............................................................................................................................................. [1]

(c) Outline conditions under which a process could change from the running state to the ready
state.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/O/N/23 [Turn over

 8

8 (a) A pseudocode algorithm finds a customer account record in a random file and outputs it. The
records are stored using the user-defined data type TAccount.

TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE LastName : STRING
DECLARE FirstName : STRING
DECLARE Address : STRING
DECLARE ContactNumber : STRING
ENDTYPE

Complete the file handling pseudocode.

The function Hash() takes the customer account number as a parameter, calculates and
returns the hash value.

DECLARE Customer : TAccount

DECLARE Location : INTEGER
DECLARE AccountFile : STRING

.................................................................................................. "AccountRecords.dat"

............................................................... AccountFile ..........................................................

OUTPUT "Please enter an account number"
INPUT Customer.AccountNumber

Location Hash( ..............................................................................................................)

SEEK ..................................................................................................................... , Location

............................................................. AccountFile, ..........................................................

OUTPUT Customer // output customer record
CLOSEFILE AccountFile
[5]

(b) Define the term exception handling.

...................................................................................................................................................

............................................................................................................................................. [1]

(c) State two possible causes of an exception.

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/O/N/23

 9

9 (a) (i) Write the infix expression for this Reverse Polish Notation (RPN) expression:

5 2 – 5 4 + * 9 /

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Show how the contents of the following stack will change as the RPN expression in
part (a)(i) is evaluated.

[4]

(b) Explain how a stack can be used to evaluate RPN expressions.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/31/O/N/23 [Turn over

 10

10 A stack is to be set up using the information in the table.

Identifier Data type Description

BasePointer INTEGER points to the bottom of the stack

TopPointer INTEGER points to the top of the stack

Stack REAL 1D array to implement the stack

A constant, with identifier Capacity, limits the size of the stack to 25 items.

(a) Write the pseudocode for the required declarations.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Complete the pseudocode function Pop() to pop an item from Stack.

// popping an item from the stack

FUNCTION Pop()...............................................................................
DECLARE Item : REAL
Item 0

............................................................................... BasePointer THEN

Item ...............................................................................

TopPointer ...............................................................................
ELSE
OUTPUT "The stack is empty – error"
ENDIF

...............................................................................
ENDFUNCTION
[5]

© UCLES 2023 9618/31/O/N/23

 11

(c) Compare and contrast the queue and stack Abstract Data Types (ADT).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/31/O/N/23 [Turn over

 12

11 A declarative programming language is used to represent subjects that students can choose to
study.

Students must choose two subjects.

01 subject(mathematics).
02 subject(physics).
03 subject(chemistry).
04 subject(computer_science).
05 subject(geography).
06 subject(history).
07 subject(english).
08 subject(biology).
09 student(tomaz).
10 student(josephine).
11 student(elspeth).
12 student(nico).
13 student(teresa).
14 student(pietre).
15 choice1(tomaz, mathematics).
16 choice1(teresa, chemistry).
17 choice1(pietre, mathematics).
18 choice1(nico, mathematics).
19 choice1(elspeth, chemistry).
20 choice2(tomaz, computer_science).
21 choice2(nico, geography).

These clauses have the meanings:

Clause Meaning
01 Mathematics is a subject.
09 Tomaz is a student.
15 Tomaz has chosen mathematics as his first choice.
20 Tomaz has chosen computer science as his second choice.

© UCLES 2023 9618/31/O/N/23

 13

(a) Anthony is a student who would like to study history and geography.

Write additional clauses to represent this information.

22 .............................................................................................................................................

23 .............................................................................................................................................

24 .............................................................................................................................................
[3]

(b) Using the variable X, the goal:

choice1(X, chemistry)

returns

X = teresa, elspeth

Write the result returned by the goal:

choice1(X, mathematics)

X = ..................................................................................................................................... [1]

(c) Students must choose two different subjects such that:

N may choose S, if N is a student and S is a subject and N has not chosen S as the first
choice.

Write this as a rule.

may_choose_subject(N, S)

IF .............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2023 9618/31/O/N/23 [Turn over

 14

12 Artificial neural networks have played a significant role in the development of machine learning.

Explain what is meant by the term artificial neural network.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

© UCLES 2023 9618/31/O/N/23

 15

BLANK PAGE

© UCLES 2023 9618/31/O/N/23

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/31/O/N/23

 Cambridge International AS & A Level
* 5 5 6 9 4 6 3 9 9 4 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (EF/CT) 318340/2
© UCLES 2023 [Turn over
 2

1 (a) Real numbers are stored in a computer using floating point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

Write the normalised floating‑point representation of –96.75 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Explain why a binary representation is sometimes only an approximation to the real number it
represents.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/O/N/23

 3

2 Describe what is meant by composite and non‑composite data types.

Composite ........................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Non‑composite .................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

3 The location of a record in a random file is determined using a hashing algorithm.

A collision may occur during the process of adding a record.

(a) Outline what is meant by the term collision in this context.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain how a collision can be dealt with when writing records to a random file.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/O/N/23 [Turn over

 4

4 Complete the following paragraph about a protocol suite, using words from the given list.

Some words are not used.

BitTorrent circuit switching layered link list

peer‑to‑peer queue stack star TCP/IP

The protocols in a ............................................................................. determine the interconnectivity

rules for a ............................................................................. network model such as the

............................................................................. model.
[3]

5 (a) Outline the reasons why an operating system may need to use virtual memory.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) Explain the circumstances in which disk thrashing could occur.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/O/N/23

 5

6 (a) The Reverse Polish Notation (RPN) expression:

a b * 2 / c d / *

is to be evaluated where a = 20, b = 3, c = 10 and d = 5.

Show the changing contents of the following stack as the RPN expression is evaluated.

[4]

(b) Explain how an expression stored in RPN can be evaluated.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/O/N/23 [Turn over

 6

7 (a) This logic circuit represents the Boolean expression: X = A + B + C

B X

Complete this truth table for the given logic circuit.

A B C X

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

[1]

(b) Apply De Morgan’s laws to the expression: X = A + B + C

X = ...................................................................................................................................... [1]

(c) Simplify the following expression using Boolean algebra.

Show all the stages in your simplification.

T = X.Y.Z + X.Y.Z + X

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/32/O/N/23

 7

8 Calculate the shortest distance between the Start and each of the destinations in the diagram
using Dijkstra’s algorithm.

Show your working and write your answers in the table provided.

4 8
A B
C

2
3

8 9

D
2

Start 10
F

Working ............................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Answers:

A B C D E F

[5]

© UCLES 2023 9618/32/O/N/23 [Turn over

 8

9 (a) A stack Abstract Data Type (ADT) is to be implemented using pseudocode, with procedures
to initialise it and to push new items onto the stack.

A 1D array Stack stores the contents of the stack.

(i) Study the pseudocode in part (a)(ii) and complete the table of identifiers by writing the
missing data types and descriptions.

Identifier Data type Description

BasePointer

TopPointer

Stack REAL

[2]

(ii) Complete the pseudocode.

CONSTANT MaxSize = 40
DECLARE BasePointer : INTEGER
DECLARE TopPointer : INTEGER
DECLARE Stack : ARRAY[1:40] OF REAL

// initialisation of stack
PROCEDURE Initialise()

................................................................................ 1

................................................................................ 0
ENDPROCEDURE

// push an item onto the stack

PROCEDURE Push(NewItem : REAL)

................................................................................ MaxSize THEN

..........................................................................................................

Stack[TopPointer] .............................................................
ENDIF
ENDPROCEDURE
[5]

© UCLES 2023 9618/32/O/N/23

 9

(b) Justify the use of a linked list instead of an array to implement a stack.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(c) Explain how a compiler makes use of a stack when translating recursive programming code.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

10 Describe the features of the SIMD and MISD computer architectures.

SIMD ................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

MISD ................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2023 9618/32/O/N/23 [Turn over

 10

11 A declarative programming language is used to represent some facts about people and their
hobbies.

01 hobby(music).
02 hobby(caving).
03 hobby(climbing).
04 hobby(camping).
05 hobby(baking).
06 hobby(travelling).
07 person(toby).
08 person(natasha).
09 person(fatima).
10 person(joseph).
11 person(elijah).
12 person(nina).
13 enjoys(natasha, travelling).
14 enjoys(toby, climbing).
15 enjoys(nina, climbing).
16 enjoys(elijah, camping).
17 enjoys(fatima, baking).
18 enjoys(joseph, camping).
19 dislikes(toby, caving).

These clauses have the meanings:

Clause Meaning
01 Music is a hobby
07 Toby is a person
13 Natasha enjoys travelling
19 Toby dislikes caving

(a) Carlos is a person who enjoys the hobby of cycling but does not like music.

Write additional clauses to represent this information.

20 ............................................................................................................................................

21 ............................................................................................................................................

22 ............................................................................................................................................

23 ............................................................................................................................................
[4]

© UCLES 2023 9618/32/O/N/23

 11

(b) Using the variable P, the goal:

enjoys(P, camping)

returns

P = elijah, joseph

Write the result returned by the goal:

enjoys(P, climbing)

P = .................................................................................................................................... [1]

(c) N is a person who might enjoy H if H is a hobby and N does not dislike H.

Write this as a rule.

might_enjoy(N, H)

IF ............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

12 (a) Describe, with an example, what is meant by an exception.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/32/O/N/23 [Turn over

 12

(b) A pseudocode algorithm searches for a customer record in a random file

AccountRecord.dat. A user inputs the name of the customer.

The records are stored using the user‑defined data type TAccount.

TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE Name : STRING
DECLARE Address : STRING
DECLARE Telephone : STRING
ENDTYPE

If the record is found, it is output, otherwise an error message is displayed.

Complete the file handling pseudocode.

DECLARE Customer : TAccount

DECLARE Location : INTEGER
DECLARE MaxSize : INTEGER
DECLARE FoundFlag : BOOLEAN
DECLARE SearchCustomer : STRING
MaxSize 1000

OPENFILE ...............................................................................................................
Location 1

............................................................................................................... FALSE
OUTPUT "Enter the customer’s name"

...............................................................................................................

................................................................................... AND Location <= MaxSize

................................... "AccountRecord.dat", ............................................

GETRECORD "AccountRecord.dat", Customer
IF SearchCustomer = Customer.Name THEN
OUTPUT "Customer found: "
OUTPUT Customer // output customer record
FoundFlag TRUE
ENDIF
Location Location + 1
ENDWHILE
IF NOT FoundFlag THEN

OUTPUT ".........................................................................................................."
ENDIF
[7]
© UCLES 2023 9618/32/O/N/23
 13

BLANK PAGE

© UCLES 2023 9618/32/O/N/23

 14

BLANK PAGE

© UCLES 2023 9618/32/O/N/23

 15

BLANK PAGE

© UCLES 2023 9618/32/O/N/23

 16

BLANK PAGE

Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/32/O/N/23

 Cambridge International AS & A Level
* 9 2 8 5 5 0 8 1 6 2 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory October/November 2023

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (AP) 333121
© UCLES 2023 [Turn over
 2

1 Real numbers are stored in a computer using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(a) Write the normalised floating-point representation of +65.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Explain the problem that will occur in storing the normalised floating-point representation of
+65.20 in this system.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/O/N/23

 3

2 (a) Draw one line to connect each protocol to its most appropriate use.

Protocol Use

to provide peer-to-peer file sharing

HTTP

when retrieving email messages from a

mail server over a TCP/IP connection
BitTorrent

when transmitting hypertext documents

SMTP

to map MAC addresses onto IP addresses

IMAP
when sending email messages towards
the intended destination

[4]

(b) Outline the purpose of the Link layer in the TCP / IP protocol suite.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

3 Describe what is meant by enumerated and pointer data types.

Enumerated ......................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

Pointer ..............................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2023 9618/33/O/N/23 [Turn over

 4

4 (a) Describe sequential and random methods of file organisation.

Sequential file organisation .......................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Random file organisation ..........................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Outline the process of sequential access for serial and sequential files.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

5 Describe the features of SISD and MIMD computer architectures.

SISD .................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

MIMD ................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2023 9618/33/O/N/23

 5

BLANK PAGE

© UCLES 2023 9618/33/O/N/23 [Turn over

 6

6 This diagram represents a logic circuit.

A
B Z
C

(a) Complete the truth table for the given logic circuit.

Working space
A B C D Z

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1
[3]

© UCLES 2023 9618/33/O/N/23

 7

(b) Simplify the given Boolean expression using Boolean algebra.

Show your working.

Y = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

7 (a) A student buys a new computer.

State one benefit to the student of a user interface and give an example.

Benefit ......................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Example ....................................................................................................................................

...................................................................................................................................................
[2]

(b) Two of the process states are the running state and the ready state.

Identify one other process state.

............................................................................................................................................. [1]

(c) Outline conditions under which a process could change from the running state to the ready
state.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/O/N/23 [Turn over

 8

8 (a) A pseudocode algorithm finds a customer account record in a random file and outputs it. The
records are stored using the user-defined data type TAccount.

TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE LastName : STRING
DECLARE FirstName : STRING
DECLARE Address : STRING
DECLARE ContactNumber : STRING
ENDTYPE

Complete the file handling pseudocode.

The function Hash() takes the customer account number as a parameter, calculates and
returns the hash value.

DECLARE Customer : TAccount

DECLARE Location : INTEGER
DECLARE AccountFile : STRING

.................................................................................................. "AccountRecords.dat"

............................................................... AccountFile ..........................................................

OUTPUT "Please enter an account number"
INPUT Customer.AccountNumber

Location Hash( ..............................................................................................................)

SEEK ..................................................................................................................... , Location

............................................................. AccountFile, ..........................................................

OUTPUT Customer // output customer record
CLOSEFILE AccountFile
[5]

(b) Define the term exception handling.

...................................................................................................................................................

............................................................................................................................................. [1]

(c) State two possible causes of an exception.

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/O/N/23

 9

9 (a) (i) Write the infix expression for this Reverse Polish Notation (RPN) expression:

5 2 – 5 4 + * 9 /

...........................................................................................................................................

..................................................................................................................................... [2]

(ii) Show how the contents of the following stack will change as the RPN expression in
part (a)(i) is evaluated.

[4]

(b) Explain how a stack can be used to evaluate RPN expressions.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

© UCLES 2023 9618/33/O/N/23 [Turn over

 10

10 A stack is to be set up using the information in the table.

Identifier Data type Description

BasePointer INTEGER points to the bottom of the stack

TopPointer INTEGER points to the top of the stack

Stack REAL 1D array to implement the stack

A constant, with identifier Capacity, limits the size of the stack to 25 items.

(a) Write the pseudocode for the required declarations.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Complete the pseudocode function Pop() to pop an item from Stack.

// popping an item from the stack

FUNCTION Pop()...............................................................................
DECLARE Item : REAL
Item 0

............................................................................... BasePointer THEN

Item ...............................................................................

TopPointer ...............................................................................
ELSE
OUTPUT "The stack is empty – error"
ENDIF

...............................................................................
ENDFUNCTION
[5]

© UCLES 2023 9618/33/O/N/23

 11

(c) Compare and contrast the queue and stack Abstract Data Types (ADT).

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

© UCLES 2023 9618/33/O/N/23 [Turn over

 12

11 A declarative programming language is used to represent subjects that students can choose to
study.

Students must choose two subjects.

01 subject(mathematics).
02 subject(physics).
03 subject(chemistry).
04 subject(computer_science).
05 subject(geography).
06 subject(history).
07 subject(english).
08 subject(biology).
09 student(tomaz).
10 student(josephine).
11 student(elspeth).
12 student(nico).
13 student(teresa).
14 student(pietre).
15 choice1(tomaz, mathematics).
16 choice1(teresa, chemistry).
17 choice1(pietre, mathematics).
18 choice1(nico, mathematics).
19 choice1(elspeth, chemistry).
20 choice2(tomaz, computer_science).
21 choice2(nico, geography).

These clauses have the meanings:

Clause Meaning
01 Mathematics is a subject.
09 Tomaz is a student.
15 Tomaz has chosen mathematics as his first choice.
20 Tomaz has chosen computer science as his second choice.

© UCLES 2023 9618/33/O/N/23

 13

(a) Anthony is a student who would like to study history and geography.

Write additional clauses to represent this information.

22 .............................................................................................................................................

23 .............................................................................................................................................

24 .............................................................................................................................................
[3]

(b) Using the variable X, the goal:

choice1(X, chemistry)

returns

X = teresa, elspeth

Write the result returned by the goal:

choice1(X, mathematics)

X = ..................................................................................................................................... [1]

(c) Students must choose two different subjects such that:

N may choose S, if N is a student and S is a subject and N has not chosen S as the first
choice.

Write this as a rule.

may_choose_subject(N, S)

IF .............................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

© UCLES 2023 9618/33/O/N/23 [Turn over

 14

12 Artificial neural networks have played a significant role in the development of machine learning.

Explain what is meant by the term artificial neural network.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

© UCLES 2023 9618/33/O/N/23

 15

BLANK PAGE

© UCLES 2023 9618/33/O/N/23

 16

BLANK PAGE

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.

© UCLES 2023 9618/33/O/N/23

 * 0000800000001 *

,










,

Cambridge International AS & A Level

¬OŠ. 4mHuOªEŠ_z6€W
¬a/|P¤x‹^pw~w-2s—‚
¥5EU55euUU¥E uEuuU
* 7 6 0 6 8 7 7 1 6 1 *

COMPUTER SCIENCE 9618/31

Paper 3 Advanced Theory October/November 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (JP/SG) 336461/5
© UCLES 2024 [Turn over
 * 0000800000002 *

DO NOT WRITE IN THIS MARGIN

2
,










,

1 Numbers are stored in a computer using binary floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised binary floating-point representation of +201.125 in this system.

Show your working.

Mantissa Exponent

DO NOT WRITE IN THIS MARGIN

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Calculate the denary value of the given normalised binary floating-point number.

Show your working.

Mantissa Exponent

1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1

DO NOT WRITE IN THIS MARGIN

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

ĬÍĊ®Ġ´íÈõÏĪÅĊÞü¸þ×
© UCLES 2024 Ĭá­ûÍĨôĝÕāāġ¿ÇĂËďĂ
ĥĥÕÕõÕĥĕĥĕµąąµåµÕÕ
9618/31/O/N/24
 * 0000800000003 *
DO NOT WRITE IN THIS MARGIN

3
,










,

2 Reduced Instruction Set Computers (RISC) is a type of processor.

Identify four features of a RISC processor.

1 .......................................................................................................................................................

..........................................................................................................................................................

2 .......................................................................................................................................................

..........................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

3 .......................................................................................................................................................

..........................................................................................................................................................

4 .......................................................................................................................................................

..........................................................................................................................................................
[4]

3 (a) Describe circuit switching as a method of data transmission.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) State one benefit and one drawback of circuit switching as a method of data transmission.
DO NOT WRITE IN THIS MARGIN

Benefit ......................................................................................................................................

...................................................................................................................................................

Drawback ..................................................................................................................................

...................................................................................................................................................
[2]
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊÞú¸þ×
© UCLES 2024 Ĭá®üÕĢðčä÷ðèě¯ÖËğĂ
ĥĥåĕµµąõõĥĥąąÕÅõÅÕ
9618/31/O/N/24 [Turn over
 * 0000800000004 *

DO NOT WRITE IN THIS MARGIN

4
,










,

4 The TCP/IP protocol may be viewed as a stack that contains four layers: Application, Transport,
Internet, Link.

Describe how the layers of the TCP/IP protocol stack interact with each other.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

5 (a) Explain what is meant by a hashing algorithm in the context of file access.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) The use of a hashing algorithm can result in the same storage location being identified for

DO NOT WRITE IN THIS MARGIN

more than one record.

Outline two methods of overcoming this issue.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................
[2]
DO NOT WRITE IN THIS MARGIN

ĬÍĊ®Ġ´íÈõÏĪÅĊàü¸Ā×
© UCLES 2024 Ĭá®ùÕĬþĜ×ù÷ß¹ēøÛėĂ
ĥÕõĕõµąÕĕÅĕąÅÕĥõÕÕ
9618/31/O/N/24
 * 0000800000005 *
DO NOT WRITE IN THIS MARGIN

5
,










,

6 (a) Describe the user-defined data type set.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(b) Write pseudocode statements to declare the set data type, SymbolSet, to hold the following
set of mathematical operators, using the variable Operators.

+ – * / ^

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊàú¸Ā×
© UCLES 2024 Ĭá­úÍĞĂĬâÿĊĪĝīäÛħĂ
ĥÕąÕµÕĥµąµÅąÅµąµÅÕ
9618/31/O/N/24 [Turn over
 * 0000800000006 *

DO NOT WRITE IN THIS MARGIN

6
,










,

7 The truth table for a logic circuit is shown.

INPUT OUTPUT

A B C D T

0 0 0 0 0

0 0 0 1 1

0 0 1 0 0

DO NOT WRITE IN THIS MARGIN

0 0 1 1 1

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

DO NOT WRITE IN THIS MARGIN

1 0 1 0 0

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

(a) Write the Boolean logic expression that corresponds to the given truth table as the
sum-of-products.

DO NOT WRITE IN THIS MARGIN

T = ............................................................................................................................................

............................................................................................................................................. [3] DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊÝúµþ×
© UCLES 2024 Ĭá®úÒĨĪĢêČûēýēÁóėĂ
ĥąåÕµõĥĕÅÕĥąąµåõĕÕ
9618/31/O/N/24
 * 0000800000007 *
DO NOT WRITE IN THIS MARGIN

7
,










,

(b) Complete the Karnaugh map (K-map) for the given truth table.

AB

CD
00 01 11 10

00

01
DO NOT WRITE IN THIS MARGIN

11

10

[2]

(c) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal sum-of-products.
[2]

(d) (i) Write the Boolean logic expression from your answer to part (c) as the simplified
sum-of-products.
DO NOT WRITE IN THIS MARGIN

T = ......................................................................................................................................

..................................................................................................................................... [2]

(ii) Use Boolean algebra to write your answer to part (d)(i) in its simplest form.

T = ............................................................................................................................... [1]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÝüµþ×
© UCLES 2024 Ĭá­ùÚĢĦĒÏîĆÖÙīĕóħĂ
ĥąÕĕõĕąõÕåµąąÕŵąÕ
9618/31/O/N/24 [Turn over
 * 0000800000008 *

DO NOT WRITE IN THIS MARGIN

8
,










,

8 (a) Describe the process of segmentation for memory management.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(b) Explain what is meant by disk thrashing.

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊßúµĀ×
© UCLES 2024 Ĭá­üÚĬĘėìôýÍûÇ·ģďĂ
ĥµąĕµĕąÕµąÅąÅÕĥµĕÕ
9618/31/O/N/24
 * 0000800000009 *
DO NOT WRITE IN THIS MARGIN

9
,










,

9 A veterinary surgery wants to create a class for individual pets.

Some of the attributes required in the class are listed in the table.

Attribute Data type Description

PetID STRING unique ID assigned at registration

PetType STRING type of pet assigned at registration

telephone number of owner assigned at
OwnerTelephone STRING
registration
DO NOT WRITE IN THIS MARGIN

DateRegistered DATE date of registration

(a) State one reason why the attributes would be declared as PRIVATE.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) Complete the class diagram for Pet, to include:

• an attribute and data type for the name of the pet

• an attribute and data type for the name of the owner
DO NOT WRITE IN THIS MARGIN

• a method to create a Pet object and set attributes at the time of registration
• a method to assign a pet ID
• a method to assign the date of registration
• a method to return the pet name
• a method to return the owner’s telephone number.

Pet
PetID : STRING
PetType : STRING
OwnerTelephone : STRING
DO NOT WRITE IN THIS MARGIN

DateRegistered : DATE

.............................................................. : ..............................................................

.............................................................. : ..............................................................

.................................................................................................................................

.................................................................................................................................

.................................................................................................................................
DO NOT WRITE IN THIS MARGIN

.................................................................................................................................

.................................................................................................................................

[5]
ĬÓĊ®Ġ´íÈõÏĪÅĊßüµĀ×
© UCLES 2024 Ĭá®ûÒĞĜħÍĆôĜ߯ģģğĂ
ĥµõÕõõĥµåõĕąÅµąõąÕ
9618/31/O/N/24 [Turn over
 * 0000800000010 *

DO NOT WRITE IN THIS MARGIN

10
,










,

10 Several syntax diagrams are shown.

letter operator
A +

E –

I *

DO NOT WRITE IN THIS MARGIN

O /

U digit
0

Y
1

symbol
# 2

DO NOT WRITE IN THIS MARGIN

$ 3

? 4

& 5

@ 6

DO NOT WRITE IN THIS MARGIN

7

label
letter digit digit
DO NOT WRITE IN THIS MARGIN

equation
label = label operator label

ĬÑĊ®Ġ´íÈõÏĪÅĊÞú·þ×
© UCLES 2024 Ĭá°üÓĪĐāæûĆ÷ėÅÓÛħĂ
ĥĥĥÕµĕåÕĕµÅÅÅõĥµåÕ
9618/31/O/N/24
 * 0000800000011 *
DO NOT WRITE IN THIS MARGIN

11
,









,

(a) Complete the Backus-Naur Form (BNF) for the given syntax diagrams.

<operator> ::= ..................................................................................................................

...................................................................................................................................................

<label> ::= .........................................................................................................................

...................................................................................................................................................

<equation> ::= ..................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................
[4]

(b) A new syntax rule, password, is required. It must begin with a letter or a symbol, followed by
a digit and end with one or two symbols.

(i) Draw a syntax diagram for password.

DO NOT WRITE IN THIS MARGIN

[3]

(ii) Write the BNF for password.

DO NOT WRITE IN THIS MARGIN

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÞü·þ×
© UCLES 2024 Ĭá¯ûÛĠĔñÓýû²Ã­ćÛėĂ
ĥĥĕĕõõŵąÅĕÅÅĕąõµÕ
9618/31/O/N/24 [Turn over
 * 0000800000012 *

DO NOT WRITE IN THIS MARGIN

12
,









,

11 The following diagram shows an ordered binary tree.

Red

Green Yellow

DO NOT WRITE IN THIS MARGIN

Blue Orange Violet

Indigo

(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data
and a right pointer.

–1 is used to represent a null pointer.

DO NOT WRITE IN THIS MARGIN

Complete this linked list to represent the given binary tree.

RootPtr

LeftPtr Data RightPtr

Red

Green

DO NOT WRITE IN THIS MARGIN

–1 Blue –1

DO NOT WRITE IN THIS MARGIN

[4]
ĬÑĊ®Ġ´íÈõÏĪÅĊàú·Ā×
© UCLES 2024 Ĭá¯úÛĦĢøèăô¹ġđåËğĂ
ĥÕÅĕµõÅĕĥĥĥÅąĕåõåÕ
9618/31/O/N/24
 * 0000800000013 *
DO NOT WRITE IN THIS MARGIN

13
,









,

(b) A user-defined record structure is used to store the nodes of the linked list in part (a).

Complete the diagram, using your answer for part (a).

RootPtr Index LeftPtr Data RightPtr

0 0 Red

1 Green

2 Yellow
DO NOT WRITE IN THIS MARGIN

3 Blue

4 Orange

5 Indigo

FreePtr 6 Violet

7
[4]

(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a
left pointer, data and a right pointer.
DO NOT WRITE IN THIS MARGIN

The following pseudocode represents a function that searches for an element in the array of
records BinTree. It returns the index of the record if the element is found, or it returns a null
pointer if the element is not found.

Complete the pseudocode for the function.

FUNCTION SearchTree(Item : STRING) ........................................................................

NowPtr .........................................................................................................................
WHILE NowPtr <> -1
DO NOT WRITE IN THIS MARGIN

IF ..................................................................................................................... THEN
NowPtr BinTree[NowPtr].LeftPtr
ELSE
IF BinTree[NowPtr].Data < Item THEN

.........................................................................................................................
ELSE
RETURN NowPtr
ENDIF
DO NOT WRITE IN THIS MARGIN

ENDIF
ENDWHILE
RETURN NowPtr
ENDFUNCTION
[4]
ĬÓĊ®Ġ´íÈõÏĪÅĊàü·Ā×
© UCLES 2024 Ĭá°ùÓĤĞĈÑõýðµĩñËďĂ
ĥÕµÕõĕåõõĕµÅąõŵµÕ
9618/31/O/N/24
 © UCLES 2024
,




* 0000800000014 *

ĥõµĕµõĥÕĕąµąÅµĥõĥÕ
Ĭá¯ûÒĞđðãóĊÓę´õûėĂ
ĬÍĊ®Ġ´íÈõÏĪÅĊßû¶Ă×






,
14

9618/31/O/N/24
BLANK PAGE

DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN

© UCLES 2024
,




* 0000800000015 *

ĥõÅÕõĕąµąõĥąÅÕąµõÕ
Ĭá°üÚĬčĀÖą÷Ė½ÌáûħĂ
ĬÏĊ®Ġ´íÈõÏĪÅĊßù¶Ă×






,
15

9618/31/O/N/24
BLANK PAGE
 * 0000800000016 *

DO NOT WRITE IN THIS MARGIN

16
,









,

BLANK PAGE

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.
ĬÍĊ®Ġ´íÈõÏĪÅĊÝû¶Ą×
© UCLES 2024 Ĭá°ùÚĢğĉáċðčğĨăīďĂ
ĥÅĕÕµĕąĕĥÕĕąąÕåµĥÕ
9618/31/O/N/24
 * 0000800000001 *

,










,

Cambridge International AS & A Level

¬OŠ. 4mHuOªEŠ_y5€W
¬kXrO«p›Nv‡mCL-Œ¥‚
¥eE•55E•Ee5 •¥5•U
* 2 3 0 8 8 6 0 8 6 3 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (WW/FC) 337425/4
© UCLES 2024 [Turn over
 * 0000800000002 *

DO NOT WRITE IN THIS MARGIN

2
,










,

1 (a) Describe how packet switching is used to transmit messages across a network.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(b) State two benefits and two drawbacks of packet switching as a method of transmitting
messages across a network.

Benefit 1 ...................................................................................................................................

...................................................................................................................................................

Benefit 2 ...................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

Drawback 1 ...............................................................................................................................

...................................................................................................................................................

Drawback 2 ...............................................................................................................................

...................................................................................................................................................
[4]

2 (a) Describe serial file organisation as a method of storing data records in a file.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) State one example of a use for serial file organisation.

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [1]

ĬÍĊ®Ġ´íÈõÏĪÅĊÞû·þ×
© UCLES 2024 ĬëÖñÎğüíåċñĒû²ý´ĝĂ
ĥõÕĕõÕąõõĥĥÅąÕąõµÕ
9618/32/O/N/24
 * 0000800000003 *
DO NOT WRITE IN THIS MARGIN

3
,










,

3 (a) Describe the user‑defined data type record.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(b) A programmer defines a record, Order, to store the following data:

• account number
• order number
• order price
• order date.

Write pseudocode statements to define this record.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [4]
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊÞù·þ×
© UCLES 2024 ĬëÕòÖĩøýÔíĀ×ßÊÙ´čĂ
ĥõåÕµµĥĕĥĕµÅąµĥµåÕ
9618/32/O/N/24 [Turn over
 * 0000800000004 *

DO NOT WRITE IN THIS MARGIN

4
,










,

4 Numbers are stored in a computer using binary floating‑point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the denary value of the given normalised binary floating‑point number.

Show your working.

Mantissa Exponent

DO NOT WRITE IN THIS MARGIN

0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Answer ......................................................................................................................................
[2]

DO NOT WRITE IN THIS MARGIN

(b) Calculate the normalised binary floating‑point representation of – 49.1875 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]
DO NOT WRITE IN THIS MARGIN

ĬÍĊ®Ġ´íÈõÏĪÅĊàû·Ā×
© UCLES 2024 ĬëÕóÖģĆČçóćÐýĦûäĥĂ
ĥÅõÕõµĥµąµÅÅŵŵµÕ
9618/32/O/N/24
 * 0000800000005 *
DO NOT WRITE IN THIS MARGIN

5
,










,

5 (a) Name and describe two protocols used by the Application Layer of the TCP/IP protocol suite.

Protocol 1 .................................................................................................................................

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

Protocol 2 .................................................................................................................................
DO NOT WRITE IN THIS MARGIN

Description ................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[4]

(b) Explain the purpose and function of the Application Layer in the TCP/IP protocol suite.

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊàù·Ā×
© UCLES 2024 ĬëÖôÎĥĊüÒąúęÙĎßäĕĂ
ĥÅąĕµÕąÕĕÅĕÅÅÕåõåÕ
9618/32/O/N/24 [Turn over
 * 0000800000006 *

DO NOT WRITE IN THIS MARGIN

6
,










,

6 The truth table for a logic circuit is shown.

INPUT OUTPUT

A B C D X

0 0 0 0 0

0 0 0 1 1

0 0 1 0 1

DO NOT WRITE IN THIS MARGIN

0 0 1 1 0

0 1 0 0 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

DO NOT WRITE IN THIS MARGIN

1 0 1 0 1

1 0 1 1 0

1 1 0 0 0

1 1 0 1 1

1 1 1 0 1

1 1 1 1 0

(a) Write the Boolean logic expression that corresponds to the given truth table as the

DO NOT WRITE IN THIS MARGIN

sum‑of‑products.

X = ............................................................................................................................................

............................................................................................................................................. [3]
DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊÝù¶þ×
© UCLES 2024 ĬëÕôÑğĢòÚĂċĤ¹Ħ¾ČĥĂ
ĥĕåĕµõąõÕåµÅąÕąµõÕ
9618/32/O/N/24
 * 0000800000007 *
DO NOT WRITE IN THIS MARGIN

7
,










,

(b) Complete the Karnaugh map (K‑map) for the given truth table.

AB
CD
00 01 11 10

00

01
DO NOT WRITE IN THIS MARGIN

11

10

[2]

(c) Draw loop(s) around appropriate group(s) in the K‑map to produce an optimal sum‑of‑products.
[2]

(d) Write the Boolean logic expression from your answer to part (c) as the simplified
sum‑of‑products.
DO NOT WRITE IN THIS MARGIN

X = ............................................................................................................................................

............................................................................................................................................. [2]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÝû¶þ×
© UCLES 2024 ĬëÖóÙĩĞĂßøöåĝĎĚČĕĂ
ĥĕÕÕõĕĥĕÅÕĥÅąµĥõĥÕ
9618/32/O/N/24 [Turn over
 * 0000800000008 *

DO NOT WRITE IN THIS MARGIN

8
,










,

7 Several syntax diagrams are shown.

odd even
1 0

3 2

5 4

DO NOT WRITE IN THIS MARGIN

7 6

9 8

symbol letter
% A

£ B

DO NOT WRITE IN THIS MARGIN

# C

@ D

$ E

DO NOT WRITE IN THIS MARGIN

number
odd odd

even
DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊßù¶Ā×
© UCLES 2024 ĬëÖòÙģĐćÜúíÞ¿²¼ĜĝĂ
ĥåąÕµĕĥµåõĕÅŵÅõõÕ
9618/32/O/N/24
 * 0000800000009 *
DO NOT WRITE IN THIS MARGIN

9
,










,

(a) State why each number is invalid for the given syntax diagrams.

21

Reason .....................................................................................................................................

...................................................................................................................................................

123

Reason .....................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................
[2]

(b) Complete the Backus‑Naur Form (BNF) for the given syntax diagrams.

<symbol> ::= ........................................................................................................................

...................................................................................................................................................

<number> ::= ........................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................
[2]

(c) A new syntax rule, code, is required. It must begin with a letter, followed by one or two
numbers, and end with a symbol.

(i) Draw a syntax diagram for code.

DO NOT WRITE IN THIS MARGIN

[3]

(ii) Write the BNF for code.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊßû¶Ā×
© UCLES 2024 ĬëÕñÑĥĔ÷ÝĀĄīěÊĠĜčĂ
ĥåõĕõõąÕµąÅÅÅÕåµĥÕ
9618/32/O/N/24 [Turn over
 * 0000800000010 *

DO NOT WRITE IN THIS MARGIN

10
,










,

8 Complex Instruction Set Computer (CISC) is a type of processor.

Identify four features of a CISC processor.

1 .......................................................................................................................................................

..........................................................................................................................................................

2 .......................................................................................................................................................

..........................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

3 .......................................................................................................................................................

..........................................................................................................................................................

4 .......................................................................................................................................................

..........................................................................................................................................................
[4]

9 (a) The kernel is the central component of an Operating System (OS).

DO NOT WRITE IN THIS MARGIN

Outline how the kernel of an OS acts as an interrupt handler.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [2]

(b) (i) State what is meant by the term multi‑tasking in an Operating System.

DO NOT WRITE IN THIS MARGIN

...........................................................................................................................................

..................................................................................................................................... [1]

(ii) Describe how multi‑tasking is implemented in an Operating System.

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]
DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊÞù¸þ×
© UCLES 2024 Ĭë×òÔġĘđÖñöĈã´ÐäĕĂ
ĥõĥĕµĕŵąÅĕąÅĕÅõÅÕ
9618/32/O/N/24
 * 0000800000011 *
DO NOT WRITE IN THIS MARGIN

11
,









,

10 Objects and classes form the basic structure of Object‑Oriented Programming (OOP).

(a) Outline the structure of a class.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

............................................................................................................................................. [3]

(b) Give three differences between an object and a class.

1 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

2 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

3 ................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
[3]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÞû¸þ×
© UCLES 2024 ĬëØñÜħĜġãćċÁ÷ÌČäĥĂ
ĥõĕÕõõåÕĕµÅąÅõåµÕÕ
9618/32/O/N/24 [Turn over
 * 0000800000012 *

DO NOT WRITE IN THIS MARGIN

12
,









,

11 This binary tree shows an ordered list of integers.

25

4 36

1 16 64

DO NOT WRITE IN THIS MARGIN

9 49

(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data
and a right pointer.

−1 is used to represent a null pointer.

Complete this linked list to represent the given binary tree organisation.

DO NOT WRITE IN THIS MARGIN

RootPtr

LeftPtr Data RightPtr

25

DO NOT WRITE IN THIS MARGIN

–1 1 –1

[4]
DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊàù¸Ā×
© UCLES 2024 ĬëØôÜĝĪĨØĉĄÊÕĨê´čĂ
ĥÅÅÕµõåõõĕµąąõąµÅÕ
9618/32/O/N/24
 * 0000800000013 *
DO NOT WRITE IN THIS MARGIN

13
,









,

(b) A 2D array is used to store the nodes of the linked list in part (a).

Complete the diagram using your answer for part (a).

RootPtr Index LeftPtr Data RightPtr

0 0 25
1 4
2 36
DO NOT WRITE IN THIS MARGIN

3 1
4 16
5 64
FreePtr 6 9
7 49
8
[4]

(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a
left pointer, data and a right pointer.
DO NOT WRITE IN THIS MARGIN

The following pseudocode represents a function that searches for an element in the array of
records LinkList. It returns the index of the record if the element is found, or it returns a
null pointer if the element is not found.

Complete the pseudocode for the function.

FUNCTION SearchList(Item : INTEGER)........................................................................

NullPtr −1

.................................................................... RootPtr
DO NOT WRITE IN THIS MARGIN

WHILE NowPtr <> NullPtr

IF LinkList[NowPtr].Data < Item THEN
NowPtr LinkList[NowPtr].RightPtr
ELSE

IF .............................................................................................................. THEN

NowPtr .....................................................................................................
ELSE
RETURN NowPtr
DO NOT WRITE IN THIS MARGIN

ENDIF
ENDIF
ENDWHILE
RETURN NullPtr
ENDFUNCTION
[4]
ĬÓĊ®Ġ´íÈõÏĪÅĊàû¸Ā×
© UCLES 2024 Ĭë×óÔīĦĘáïíÿāĐî´ĝĂ
ĥŵĕõĕÅĕĥĥĥąąĕĥõÕÕ
9618/32/O/N/24
 © UCLES 2024
,




* 0000800000014 *

ĥĥµÕµõąµąõĥÅÅÕŵąÕ
ĬëØñÑĥęĠÓùúäÝÅúĄĥĂ
ĬÍĊ®Ġ´íÈõÏĪÅĊßüµĂ×






,
14

9618/32/O/N/24
BLANK PAGE

DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN

© UCLES 2024
,




* 0000800000015 *

ĥĥÅĕõĕĥÕĕąµÅŵåõĕÕ
Ĭë×òÙģĕĐæÿćĥù­ÞĄĕĂ
ĬÏĊ®Ġ´íÈõÏĪÅĊßúµĂ×






,
15

9618/32/O/N/24
BLANK PAGE
 * 0000800000016 *

DO NOT WRITE IN THIS MARGIN

16
,









,

BLANK PAGE

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.
ĬÍĊ®Ġ´íÈõÏĪÅĊÝüµĄ×
© UCLES 2024 Ĭë×óÙĩħęÑāĀĞÛđĀĔĝĂ
ĥÕĕĕµĕĥõõåÅÅąµąõąÕ
9618/32/O/N/24
 * 0000800000001 *

,










,

Cambridge International AS & A Level

¬OŠ. 4mHuOªEŠ`{6€W
¬[sRž¢™ln„J=œ‚œ€‚
¥uEU5UE•5•eE U¥5eU
* 1 0 8 6 5 2 0 5 9 9 *

COMPUTER SCIENCE 9618/33

Paper 3 Advanced Theory October/November 2024

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 16 pages. Any blank pages are indicated.

DC (EV) 347522
© UCLES 2024 [Turn over
 * 0000800000002 *

DO NOT WRITE IN THIS MARGIN

2
,










,

1 Numbers are stored in a computer using binary floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised binary floating-point representation of +201.125 in this system.

Show your working.

Mantissa Exponent

DO NOT WRITE IN THIS MARGIN

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................
[3]

(b) Calculate the denary value of the given normalised binary floating-point number.

Show your working.

Mantissa Exponent

1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1

DO NOT WRITE IN THIS MARGIN

Working .....................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

Answer ......................................................................................................................................
[3]

ĬÍĊ®Ġ´íÈõÏĪÅĊÝù¸þ×
© UCLES 2024 ĬāÙôÓĪĦïÓăöåõĢ²äĈĂ
ĥåÕÕõµąõąÕõąąĕąõąÕ
9618/33/O/N/24
 * 0000800000003 *
DO NOT WRITE IN THIS MARGIN

3
,










,

2 Reduced Instruction Set Computers (RISC) is a type of processor.

Identify four features of a RISC processor.

1 .......................................................................................................................................................

..........................................................................................................................................................

2 .......................................................................................................................................................

..........................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

3 .......................................................................................................................................................

..........................................................................................................................................................

4 .......................................................................................................................................................

..........................................................................................................................................................
[4]

3 (a) Describe circuit switching as a method of data transmission.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) State one benefit and one drawback of circuit switching as a method of data transmission.
DO NOT WRITE IN THIS MARGIN

Benefit ......................................................................................................................................

...................................................................................................................................................

Drawback ..................................................................................................................................

...................................................................................................................................................
[2]
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊÝû¸þ×
© UCLES 2024 ĬāÚóÛĠĪÿæõċĤáĚĦäøĂ
ĥååĕµÕĥĕĕååąąõĥµĕÕ
9618/33/O/N/24 [Turn over
 * 0000800000004 *

DO NOT WRITE IN THIS MARGIN

4
,










,

4 The TCP/IP protocol may be viewed as a stack that contains four layers: Application, Transport,
Internet, Link.

Describe how the layers of the TCP/IP protocol stack interact with each other.

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

..........................................................................................................................................................

.................................................................................................................................................... [4]

5 (a) Explain what is meant by a hashing algorithm in the context of file access.

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

(b) The use of a hashing algorithm can result in the same storage location being identified for

DO NOT WRITE IN THIS MARGIN

more than one record.

Outline two methods of overcoming this issue.

1 ................................................................................................................................................

...................................................................................................................................................

2 ................................................................................................................................................

...................................................................................................................................................
[2]
DO NOT WRITE IN THIS MARGIN

ĬÍĊ®Ġ´íÈõÏĪÅĊßù¸Ā×
© UCLES 2024 ĬāÚòÛĦĜĊÑûĄīă¶È´ĀĂ
ĥĕõĕõÕĥµõąÕąÅõŵąÕ
9618/33/O/N/24
 * 0000800000005 *
DO NOT WRITE IN THIS MARGIN

5
,










,

6 (a) Describe the user-defined data type set.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

............................................................................................................................................. [3]

(b) Write pseudocode statements to declare the set data type, SymbolSet, to hold the following
set of mathematical operators, using the variable Operators.

+ – * / ^

...................................................................................................................................................

...................................................................................................................................................
DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÏĊ®Ġ´íÈõÏĪÅĊßû¸Ā×
© UCLES 2024 ĬāÙñÓĤĘúèýíÞ×¾Ĕ´ðĂ
ĥĕąÕµµąÕĥõąąÅĕåõĕÕ
9618/33/O/N/24 [Turn over
 * 0000800000006 *

DO NOT WRITE IN THIS MARGIN

6
,










,

7 The truth table for a logic circuit is shown.

INPUT OUTPUT

A B C D T

0 0 0 0 0

0 0 0 1 1

0 0 1 0 0

DO NOT WRITE IN THIS MARGIN

0 0 1 1 1

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

DO NOT WRITE IN THIS MARGIN

1 0 1 0 0

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 1

(a) Write the Boolean logic expression that corresponds to the given truth table as the
sum-of-products.

DO NOT WRITE IN THIS MARGIN

T = ............................................................................................................................................

............................................................................................................................................. [3] DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊÞûµþ×
© UCLES 2024 ĬāÚñÐĪðôàĊĀ×·¶ñĜĀĂ
ĥÅåÕµĕąõåĕåąąĕąµÅÕ
9618/33/O/N/24
 * 0000800000007 *
DO NOT WRITE IN THIS MARGIN

7
,










,

(b) Complete the Karnaugh map (K-map) for the given truth table.

AB

CD
00 01 11 10

00

01
DO NOT WRITE IN THIS MARGIN

11

10

[2]

(c) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal sum-of-products.
[2]

(d) (i) Write the Boolean logic expression from your answer to part (c) as the simplified
sum-of-products.
DO NOT WRITE IN THIS MARGIN

T = ......................................................................................................................................

..................................................................................................................................... [2]

(ii) Use Boolean algebra to write your answer to part (d)(i) in its simplest form.

T = ............................................................................................................................... [1]
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÞùµþ×
© UCLES 2024 ĬāÙòØĠôĄÙðñĒģ¾åĜðĂ
ĥÅÕĕõõĥĕµĥõąąõĥõÕÕ
9618/33/O/N/24 [Turn over
 * 0000800000008 *

DO NOT WRITE IN THIS MARGIN

8
,










,

8 (a) Describe the process of segmentation for memory management.

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [4]

(b) Explain what is meant by disk thrashing.

...................................................................................................................................................

...................................................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

............................................................................................................................................. [3]

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN

ĬÑĊ®Ġ´íÈõÏĪÅĊàûµĀ×
© UCLES 2024 ĬāÙóØĦĂąÞòúęÁĢćČĈĂ
ĥõąĕµõĥµÕÅąąÅõÅõÅÕ
9618/33/O/N/24
 * 0000800000009 *
DO NOT WRITE IN THIS MARGIN

9
,










,

9 A veterinary surgery wants to create a class for individual pets.

Some of the attributes required in the class are listed in the table.

Attribute Data type Description

PetID STRING unique ID assigned at registration

PetType STRING type of pet assigned at registration

telephone number of owner assigned at
OwnerTelephone STRING
registration
DO NOT WRITE IN THIS MARGIN

DateRegistered DATE date of registration

(a) State one reason why the attributes would be declared as PRIVATE.

...................................................................................................................................................

............................................................................................................................................. [1]

(b) Complete the class diagram for Pet, to include:

• an attribute and data type for the name of the pet

• an attribute and data type for the name of the owner
DO NOT WRITE IN THIS MARGIN

• a method to create a Pet object and set attributes at the time of registration
• a method to assign a pet ID
• a method to assign the date of registration
• a method to return the pet name
• a method to return the owner’s telephone number.

Pet
PetID : STRING
PetType : STRING
OwnerTelephone : STRING
DO NOT WRITE IN THIS MARGIN

DateRegistered : DATE

.............................................................. : ..............................................................

.............................................................. : ..............................................................

.................................................................................................................................

.................................................................................................................................

.................................................................................................................................
DO NOT WRITE IN THIS MARGIN

.................................................................................................................................

.................................................................................................................................

[5]
ĬÓĊ®Ġ´íÈõÏĪÅĊàùµĀ×
© UCLES 2024 ĬāÚôÐĤþõÛĈćÐĕĚÓČøĂ
ĥõõÕõĕąÕÅµÕąÅĕåµÕÕ
9618/33/O/N/24 [Turn over
 * 0000800000010 *

DO NOT WRITE IN THIS MARGIN

10
,










,

10 Several syntax diagrams are shown.

letter operator
A +

E –

I *

DO NOT WRITE IN THIS MARGIN

O /

U digit
0

Y
1

symbol
# 2

DO NOT WRITE IN THIS MARGIN

$ 3

? 4

& 5

@ 6

DO NOT WRITE IN THIS MARGIN

7

label
letter digit digit
DO NOT WRITE IN THIS MARGIN

equation
label = label operator label

ĬÑĊ®Ġ´íÈõÏĪÅĊÝû·þ×
© UCLES 2024 ĬāÜóÍĨĊēäùñ³ÝĤģ´ðĂ
ĥåĥÕµõŵõõąÅÅÕÅõõÕ
9618/33/O/N/24
 * 0000800000011 *
DO NOT WRITE IN THIS MARGIN

11
,









,

(a) Complete the Backus-Naur Form (BNF) for the given syntax diagrams.

<operator> ::= ..................................................................................................................

...................................................................................................................................................

<label> ::= .........................................................................................................................

...................................................................................................................................................

<equation> ::= ..................................................................................................................

DO NOT WRITE IN THIS MARGIN

...................................................................................................................................................
[4]

(b) A new syntax rule, password, is required. It must begin with a letter or a symbol, followed by
a digit and end with one or two symbols.

(i) Draw a syntax diagram for password.

DO NOT WRITE IN THIS MARGIN

[3]

(ii) Write the BNF for password.

DO NOT WRITE IN THIS MARGIN

...........................................................................................................................................

...........................................................................................................................................

...........................................................................................................................................

..................................................................................................................................... [2]
DO NOT WRITE IN THIS MARGIN

ĬÓĊ®Ġ´íÈõÏĪÅĊÝù·þ×
© UCLES 2024 ĬāÛôÕĢĆģÕÿĀöùĜ·´ĀĂ
ĥåĕĕõĕåÕĥąÕÅŵåµĥÕ
9618/33/O/N/24 [Turn over
 * 0000800000012 *

DO NOT WRITE IN THIS MARGIN

12
,









,

11 The following diagram shows an ordered binary tree.

Red

Green Yellow

DO NOT WRITE IN THIS MARGIN

Blue Orange Violet

Indigo

(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data
and a right pointer.

–1 is used to represent a null pointer.

DO NOT WRITE IN THIS MARGIN

Complete this linked list to represent the given binary tree.

RootPtr

LeftPtr Data RightPtr

Red

Green

DO NOT WRITE IN THIS MARGIN

–1 Blue –1

DO NOT WRITE IN THIS MARGIN

[4]
ĬÑĊ®Ġ´íÈõÏĪÅĊßû·Ā×
© UCLES 2024 ĬāÛñÕĬøĦâāćíÛ¸ĕäøĂ
ĥĕÅĕµĕåõąååÅąµąµõÕ
9618/33/O/N/24
 * 0000800000013 *
DO NOT WRITE IN THIS MARGIN

13
,









,

(b) A user-defined record structure is used to store the nodes of the linked list in part (a).

Complete the diagram, using your answer for part (a).

RootPtr Index LeftPtr Data RightPtr

0 0 Red

1 Green

2 Yellow
DO NOT WRITE IN THIS MARGIN

3 Blue

4 Orange

5 Indigo

FreePtr 6 Violet

7
[4]

(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a
left pointer, data and a right pointer.
DO NOT WRITE IN THIS MARGIN

The following pseudocode represents a function that searches for an element in the array of
records BinTree. It returns the index of the record if the element is found, or it returns a null
pointer if the element is not found.

Complete the pseudocode for the function.

FUNCTION SearchTree(Item : STRING) ........................................................................

NowPtr .........................................................................................................................
WHILE NowPtr <> -1
DO NOT WRITE IN THIS MARGIN

IF ..................................................................................................................... THEN
NowPtr BinTree[NowPtr].LeftPtr
ELSE
IF BinTree[NowPtr].Data < Item THEN

.........................................................................................................................
ELSE
RETURN NowPtr
ENDIF
DO NOT WRITE IN THIS MARGIN

ENDIF
ENDWHILE
RETURN NowPtr
ENDFUNCTION
[4]
ĬÓĊ®Ġ´íÈõÏĪÅĊßù·Ā×
© UCLES 2024 ĬāÜòÍĞüĖ×÷ú¼ÿÀÁäĈĂ
ĥĕµÕõõÅĕĕÕõÅąÕĥõĥÕ
9618/33/O/N/24
 © UCLES 2024
,




* 0000800000014 *

ĥµµĕµĕąµõÅõąÅĕŵµÕ
ĬāÛôÐĤćĞåñíėãĕÅĔĀĂ
ĬÍĊ®Ġ´íÈõÏĪÅĊàú¶Ă×






,
14

9618/33/O/N/24
BLANK PAGE

DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN DO NOT WRITE IN THIS MARGIN

© UCLES 2024
,




* 0000800000015 *

ĥµÅÕõõĥÕĥµåąÅõåõåÕ
ĬāÜóØĦċĎÔćĄÒ÷ĝđĔðĂ
ĬÏĊ®Ġ´íÈõÏĪÅĊàü¶Ă×






,
15

9618/33/O/N/24
BLANK PAGE
 * 0000800000016 *

DO NOT WRITE IN THIS MARGIN

16
,









,

BLANK PAGE

DO NOT WRITE IN THIS MARGIN

DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN
DO NOT WRITE IN THIS MARGIN

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge
Local Examinations Syndicate (UCLES), which is a department of the University of Cambridge.
ĬÍĊ®Ġ´íÈõÏĪÅĊÞú¶Ą×
© UCLES 2024 ĬāÜòØĠùěçĉċÙÕÁ³ĄĈĂ
ĥąĕÕµõĥõąĕÕąąõąõµÕ
9618/33/O/N/24