Cambridge A Level Computer Science 9618 — 2022 May/June Paper 3 · Variant 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] (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]

Mark scheme: 1(a) BuildingRegister.BuildingGroup  "house" 1(b)(i) One mark: TYPE BuildingType = One mark: (house, bungalow, apartment, farm) TYPE BuildingType = (house, bungalow, apartment, farm) 2 1(b)(ii) DECLARE BuildingGroup : BuildingType 1 1(b)(iii) BuildingRegister.BuildingGroup  house 1 1(c)(i) PRIVATE OwnerName : STRING 1 1(c)(ii) To ensure that attributes can only be accessed by the class’s own methods To enforce encapsulation // ensure they are hidden 2

More questions on User-defined data types

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] (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]

Mark scheme: 2(a) tutors(nina, sam). 2 2(b) freya, hua // hua, freya 1 2(c) one mark for correct use of X one mark for two other variables in correct positions one mark for three correct clauses in any order one mark for correct syntax teaches(R, S), studies(X, S), tutors(R, X). 4

More questions on Programming Paradigms

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]

Mark scheme: 3(a) Protocol one mark, description one mark, max four Any two from  HTTP(S) (1) for sending and receiving web pages / hypertext documents (1)  FTP (1) for sending and receiving files over a network / between devices (1)  SMTP (1) for sending/uploading emails /push protocol (1)  POP(3) (1) for receiving/downloading emails /pull protocol (1)  IMAP (1) for receiving/downloading emails /pull protocol (1) 4 3(b) Layer one mark, matching function one mark, max four Any two from  Transport (1) handles packets (1)  Internet (1) handles transmission of data using IP addresses // provides (optimal) route (1)  Network Access (Interface) // (Data) Link // Physical (1) Handles how data is physically sent (1) 4

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] (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]

Mark scheme: 4(a) An unsigned integer,12, is used instead of the last variable // 12 is not a valid variable  The variable Z is not a valid variable / missing an unsigned integer after the Z 2 4(b) One mark per bullet point  <variable> ::= <letter><unsigned_integer>  <unsigned_integer> ::= <digit>|<digit><digit>  <digit> ::= 1 | 2 | 3 and <operator> ::= + | - | *  <assignment_statement> ::= <variable> =  <variable><operator><variable> 5 Question Answer Marks 4(c)(i) One mark adding both boxes… One mark for correct position(s) and connector(s) … One mark … rest correct 3 4(c)(ii) Max three One mark for <assignment_statement>::=<variable>= One mark two or three correct options or two marks if all four options correct <variable><operator><variable> |<variable><operator><unsigned_integer> |<unsigned_integer><operator><variable> |<unsigned_integer><operator><unsigned_integer> <assignment_statement>::=<variable>= <variable><operator><variable>|<variable><operator> <unsigned_integer>|<unsigned_integer><operator><variable> |<unsigned_integer><operator><unsigned_integer> or One mark for each section <operand>::=<variable>|<unsigned_integer> <assignment_statement>::=<variable>= <operand><operator><operand> <operand>::=<variable>|<unsigned_integer> <assignment_statement>::=<variable>=<operand><operator><operand> 3 (assignment statement) variable = operator unsigned integer variable variable unsigned integer unsigned integer unsigned integer

More questions on Program Design

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]

Mark scheme: 5 SIMD (1) many/array processors execute the same instruction using different data sets (1) MISD (1) many processors (using different instructions) use the same data set (1) MIMD (1) many processors (using different instructions) using different data sets (1) 6

6 A logic circuit has two inputs A and B, and two outputs E and F. A E B F (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]

Mark scheme: 6(a) 1 mark per correct output column INPUT OUTPUT A B E F 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 2 6(b)(i) Half adder 1 6(b)(ii) Purpose of E: Sum Purpose of F: Carry 2

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]

Mark scheme: 7(a) Any three from MP1 enquiry made to Certificate Authority (CA) MP2 enquirer’s details checked by CA MP3 if enquirer details verified by CA then public key is agreed MP4 CA creates/issues certificate that includes the enquirers public key MP5 encrypting data sent to/by CA with the CA’s public/private key 3 7(b)(i) MP1 The message is hashed with (the agreed hashing algorithm)… MP2 … to produce a message digest MP3 The message digest is then encrypted with the sender’s private key to form the digital signature 3 7(b)(ii) Any four from MP1 The message together with the digital signature is decrypted using the receiver’s private key MP2 The digital signature received is decrypted with the sender’s public key to recover the message digest sent MP3 The decrypted message received is hashed with the agreed hashing algorithm to reproduce the message digest of the message received MP4 The two message digests are compared MP5 … if they are the same the message has not been altered // if they are different the message has been altered 4

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] (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]

Mark scheme: 8(a) 9 // LENGTH(MyList) - 1 Index + 1 "Value not found" (or any similar phrase) 8(b)(i) The list to be searched must be ordered/sorted 1 Question Answer Marks 8(b)(ii) Any four from MP1 Find the middle item / index MP2 Check the value of middle item in the list to be searched MP3 If equal item searched for is found MP4 If this is not equal/greater/less than the item searched for MP5 … discard the half of the list that does not contain the search item MP6 Repeat the above steps until the item searched for is found MP7 … or there is only one item left in the list and it is not the item searched for // lower bound > / = upper bound 4 8(b)(iii) As the number of items in the list increases the time to search the list increases 1 8(c) MP1 Linear search O(n) and Binary search O(log2n) / O(Log n) MP2 time to search increases linearly in relation to the number of items in the list for a linear search and logarithmically for a Binary search MP3 time to search increases less rapidly for a binary search and time to search increases more rapidly for a linear search 3

More questions on Algorithms

9 State the reasons for including exception handling routines when writing a program. Include an example of an exception in your answer. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .................................................................................................................................................... [4]

Mark scheme: 9 To trap (some) runtime errors To prevent a program halting unexpectedly To produce meaningful error messages for these errors Example divide by zero // end of file // file not found

More questions on File Processing and Exception Handling