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

Mark scheme: Question Answer Marks 1(a) One mark per mark point 2  correct mantissa  correct exponent with associated working Answer Mantissa Exponent 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 Working exponent = 6 (movement of 6 bicimal places seen to find what exponent should be) calculation of denary 6 to binary (000)110 1(b) One mark per mark point (Max 3) 3 MP1 the mantissa of the number would need to be 0.101011111001 / 13 bits / digits MP2 … it can only store 10 bits / digits MP3 The 3 least significant digits would be truncated MP4 …causing a loss of precision

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]

Mark scheme: 2(a) One mark per mark point (Max 3) 3 MP1 records are stored in a particular order MP2 the order is determined based on the value in a key field MP3 records are accessed one after the other MP4 records can be found by searching from the beginning of the file, record by record, MP5 … until the required record is found or key field value is exceeded. 2(b) One mark for each correct hash value (Max 2) 2 Record key Hash value 3003 3 1029 4 7630 0

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 U W Y variable letter digit (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]

Mark scheme: 3(a) One mark per correct valid/invalid and reason combination (Max 2) 2 9SW – Invalid Reason - This begins with a digit and a variable must begin with a letter UWY – Valid Reason – This begins with a letter and is followed by two other letters. 3(b) One mark per mark point (Max 3) 3  <word> ::= <letter>|  …<word><letter>  <variable> ::= <word>|<word><digit> Example answers <word> ::= <letter>|<word><letter> <word> ::= <letter><word>|<letter> <variable> ::= <word>|<word><digit> <variable> ::= <word><digit>|<word> 3(c)(i) Answer must be two letters followed by one, two or three digits using the letters 1 and digits on the syntax diagram. Example answer AC768 3(c)(ii) One mark per mark point (Max 3) 3  always has only two letters  one, two or three digits possible  correct arrows, boxes and name of syntax diagram Example answer Vehicle registration letter letter digit digit digit

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]

Mark scheme: 4 One mark for each correct line connecting an OOP term to its description 4 (Max 4). 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

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]

Mark scheme: 5(a) One mark per mark point (Max 2) 2 MP1 to produce a virtually unbreakable encryption system / send virtually un-hackable secure messages … MP2 …using the laws / principles of quantum mechanics / properties of photons MP3 detects eavesdropping … MP4 …because the properties of photons change MP5 to protect security of data transmitted over fibre optic cables MP6 to enable the use of longer keys. 5(b) One mark per mark point (Max 3) 3 MP1 Symmetric cryptography uses a single key to encrypt and decrypt messages, Asymmetric cryptography uses two. MP2 The symmetric key is shared, whereas with asymmetric, only the public key is shared (and the private key isn’t). MP3 … the risk of compromise is higher with symmetric encryption and asymmetric encryption is more secure. MP4 Symmetric cryptography is a simple process that can be carried out quickly, but asymmetric is much more complex, so slower. MP5 The length of the keys in symmetric encryption are (usually) shorter than those for asymmetric (128/256 bits v 2048 bits).

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]

Mark scheme: 6(a) One mark for TYPE TAppointments and ENDTYPE correct 4 One mark for every two correct declarations (Max 3) Example answer TYPE TAppointments DECLARE Name : STRING DECLARE DateOfBirth : DATE DECLARE Telephone : STRING DECLARE LastAppointment : DATE DECLARE NextAppointment : DATE DECLARE TreatmentsComplete : BOOLEAN ENDTYPE 6(b) One mark for each correctly completed line (Max 5) 5 DECLARE DentalRecord : ARRAY[1:250] OF TAppointments DECLARE DentalFile : STRING DECLARE Count : INTEGER DentalFile  "DentalFile.dat" OUTPUT "The file ", DentalFile, " contains these records:" OPENFILE DentalFile FOR RANDOM Count  1 REPEAT SEEK DentalFile, Count GETRECORD DentalFile, DentalRecord[Count] OUTPUT DentalRecord[Count] Count  Count + 1 UNTIL EOF(DentalFile) CLOSEFILE DentalFile

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]

Mark scheme: 7(a) One mark per mark point (Max 2) 2 MP1 Packet switching is most commonly used on data networks such as the internet to send large data files that don’t need to be live streamed MP2 Packet switching is used when it is necessary to be able to overcome failed/faulty lines by rerouting. MP3 Packet switching is used when it is necessary for the communication to be more secure. MP4 Packet switching is used for high volume data transmission. MP5 Packet switching is used when it isn’t necessary to use all the bandwidth. MP6 Specific examples e.g. email, text messages, documents, VOIP etc. (up to two marks). 7(b) One mark per mark point (Max 4) 4 MP1 Circuit switching uses a dedicated channel to make communication, whereas packet switching forms data into packets to transmit over a digital network. MP2 The dedicated path for circuit switching must be established before the transfer of data can commence, which is not the case with packet switching (as it doesn’t require a dedicated path). MP3 Data in packet switching is split into packets, in circuit switching the message remains intact. MP4 All of the transmission in circuit switching follows the same path whereas different packets in packet switching can take different routes. MP5 The message is received in the same order in which it is sent with circuit switching, but with packet switching, the packets can be received out of order (for assembly at the destination). MP6 Circuit switching is implemented at the physical layer while packet switching is implemented at the network layer. MP7 Circuit switching uses the whole bandwidth of the channel used, packet switching can share bandwidth. MP8 Circuit switching communication ends with an error but packet switching allows packets to be re-sent. MP9 Circuit switching is a simpler process than packet switching.

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 ID stages OF IE Processor WB [4]

Mark scheme: 8(a) One mark per mark point (Max 2) 2 MP1 Pipelining allows several instructions to be processed simultaneously / concurrently. MP2 … therefore, increasing the CPU instruction throughput / the number of instructions completed per unit of time. MP3 Each instruction stage / subtask is completed during one clock cycle MP4 No two instructions can execute their same stage of instruction / subtask at the same clock cycle. MP5 … e.g., while one instruction is being decoded, the next instruction can be fetched, etc. 8(b) One mark per mark point (Max 4) 4  First stage of first instruction in first clock cycle  First instruction successfully completed over five clock cycles  Remaining instructions completed over ten clock cycles …  … with no extra instruction sections added on any row. Example answer 1 Clock cycles 1 2 3 4 5 6 7 8 9 10 11 12 IF 1.1 2.1 3.1 4.1 5.1 6.1 ID 1.2 2.2 3.2 4.2 5.2 6.2 stages OF 1.3 2.3 3.3 4.3 5.3 6.3 IE 1.4 2.4 3.4 4.4 5.4 6.4 Processor WB 1.5 2.5 3.5 4.5 5.5 6.5 Example answer 2 Clock cycles 1 2 3 4 5 6 7 8 9 10 11 12 IF A B C D E F ID A B C D E F stages OF A B C D E F IE A B C D E F Processor WB A B C D E F

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

Mark scheme: 9(a) One mark for every two correct products (Max 3) 3 (Z =) ABCD + ABCD + ABCD + ABCD + ABCD + ABCD 9(b) Two marks if no errors present 2 One mark if one error present 9(c) One mark for each correct loop (Max 2) 2 9(d) One mark for each mark point (Max 2) 2  Any correct Boolean term  Boolean terms and operator correct and no other terms present (Z =) AB + AC 9(e) One mark for simplest form (Max 1) 1 (Z =) A (B + C)

10 (a) State one category of machine learning. ............................................................................................................................................. [1] (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 Begin g = 5 h = 8 4 11 5 A D 6 7 7 C B 6 8 6 2 8 E 7 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]

Mark scheme: 10(a) One mark from: 1 Supervised (learning) Unsupervised (learning) Reinforcement (learning) Deep (learning) 10(b) One mark for each correct calculation as follows (Max 2): 5  Node B (from Begin) (Line 3 in table)  Node C (from Begin) (Line 4 in table)  Node D (from Begin) (Line 5 in table) One mark for each correct calculation as follows (Max 2):  Node G (from C) (Line 6 in table)  Node F and Node End (from G) (Lines 7 and 8 in table)  Node End (from F) (Line 9 in table) One mark for correct path (Max 1):  Begin  C  G  F  End Cost from Start Destination Heuristic Total start node node node (h) (f = g + h) (g) Begin Begin 0 12 12 Begin A 5 8 13 Begin B 6 7 13 Begin C 5 7 12 Begin D 4 11 15 C G 5 + 2 = 7 5 12 G F 5 + 2 + 4 = 11 1 12 G End 5 + 2 + 7 = 14 0 14 5 + 2 + 4 + 1 = F End 0 12 12 Final Path Begin  C  G  F  End

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] (b) Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 11(a)(i) One mark for every two correct identifiers (Max 2) 2 Identifier Data type Description Queue STRING An array to store the contents of the queue. RearPointer INTEGER Points to the last term of the queue. Length INTEGER Indicates the number of items in the queue. FrontPointer INTEGER Points to the first term of the queue. 11(a)(ii) One mark for each correctly completed line (Max 5) 5 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 RearPointer  -1 Length  0 ENDPROCEDURE // Adding a new item to the queue PROCEDURE Enqueue(NewItem : STRING) IF Length < MaxLength THEN // IF Length <= MaxLength - 1 THEN RearPointer  RearPointer + 1 IF RearPointer > MaxLength – 1 THEN RearPointer  0 ENDIF Queue[RearPointer]  NewItem Length  Length + 1 ENDIF ENDPROCEDURE 11(b) One mark per mark point (Max 3) 3  Print jobs are expected to be actioned by the printer in the order they are received  … because the printer queue is a queue, the first job to be sent to the printer would be the first job printed.  If the printer queue was on a stack, the first job the printer received would not be printed until all the other jobs have been printed.