Cambridge A Level Computer Science 9618 — 2025 May/June Paper 3 · Variant 3

1 A programmer is writing a program to manage a video library. They require a user-defined data type. (a) Write pseudocode statements to declare the composite data type VideoLibrary to hold data about each video in the collection. This data includes: • identity code (any combination of letters and numbers) • title • year released • date purchased • format (for example DVD, Blu-ray, 4K, MP4) • running time (minutes) Use the most appropriate data type in each case. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4] (b) Identify one field in VideoLibrary that could be an efficient enumerated data type and give a reason for your choice. Field .......................................................................................................................................... ................................................................................................................................................... Reason ..................................................................................................................................... ................................................................................................................................................... [2]

Mark scheme: Question Answer Marks 1(a) One mark per mark point 4 MP1 TYPE VideoLibrary and ENDTYPE correct MP2 Declare used correctly for every field in the response MP3 All Three STRING fields correct (shaded) MP4 Remaining Three fields correct (unshaded) Example answer TYPE VideoLibrary DECLARE VideoID : STRING DECLARE Title : STRING DECLARE ReleaseYear : INTEGER DECLARE PurchaseDate : DATE DECLARE VideoFormat : STRING DECLARE RunningTime : INTEGER ENDTYPE 1(b) One mark for identification of field and one mark for reason 2 VideoFormat This field can have a fixed range of possible values

2 Numbers are stored in a computer using binary floating-point representation with: • 8 bits for the mantissa • 8 bits for the exponent • two’s complement form for both the mantissa and the exponent. (a) Give the largest normalised positive two’s complement binary number that can be stored in this system and state its denary equivalent. The denary answer should be expressed in terms of powers of 2. Mantissa Exponent Denary ...................................................................................................................................... [2] (b) Calculate the normalised binary floating-point representation of –3.59375 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [4]

Mark scheme: 2(a) One mark for two’s complement version and one mark for denary version 2 Mantissa Exponent 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 127  2120 // 0.9921875 x 2127 // 127/128 x 2127 2(b) One mark per mark point for working (Max 2) 4 • number converted to binary e.g., positive binary version of 3.59375 = (0)11.10011 • negative two’s complement version - bits flipped and 1 added = 100.01101 • -4 + 1/4 + 1/8 + 1/32 // -4 + 025 +0.125 + 0.03125 // -(64 + 32 + 16 + 2 + 1)/32 • -22 + 2-2 + 2-3 + 2-5 • 22 (- 20 + 2-4 + 2-5 + 2-7) One mark per mark point • correct mantissa • correct exponent, with working seen. Mantissa Exponent 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0

3 This truth table represents a logic circuit. INPUT OUTPUT A B C D Z 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 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 = ............................................................................................................................................ ............................................................................................................................................. [2] (b) (i) Complete the Karnaugh map (K-map) for the given truth table. AB 00 01 11 10 CD 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 logic expression from your answer to part (b)(ii) as the simplified sum-of-products. Z = ..................................................................................................................................... ..................................................................................................................................... [2]

Mark scheme: 3(a) Two marks for all six correct terms 2 One mark for any four correct terms 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 3(b)(i) Two marks if no errors present 2 One mark if one error present AB CD 00 01 11 10 00 0 1 1 0 01 0 0 0 0 11 1 0 0 1 10 1 0 0 1 3(b)(ii) One mark for each correct loop (Max 2) 2 AB CD 00 01 11 10 00 0 1 1 0 01 0 0 0 0 11 1 0 0 1 10 1 0 0 1 3(b)(iii) One mark for each mark point 2 • One correct Boolean term • Boolean terms and operator correct and no other terms present Z = B.C + B.C.D // B.C.D + B.C

4 (a) The Internet layer and Link layer are two layers of the TCP/IP protocol suite. Describe the purpose of the Internet layer and the purpose of the Link layer. Purpose of Internet layer .......................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Purpose of Link layer ................................................................................................................ ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [5] (b) Describe the function of a router in packet switching. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 4(a) One mark per mark point (Max 5) 5 One mark per mark point for purpose of Internet Layer (Max 3) MP1 To identify the intended network and host. MP2 To add header containing IP addresses. // To address packets with their source and destination IP Addresses. MP3 To prepare packets for delivery by formatting them into datagrams. MP4 To route datagrams through the optimum route over a network. One mark per mark point for purpose of Link Layer (Max 3) MP5 To prepare the next hop by managing the link between two directly connected devices. // To identify and move traffic across local segments. MP6 To format datagrams into frames for transmission. MP7 To identify network protocols in the packet header. // To ensure correct network protocols are/is followed. MP8 To deliver frames to the receiving network. // To receive frames from the sending network. // To map IP addresses to MAC physical addresses. MP9 To provide error checking/error correction/recovery/reconstruction MP10 including resend requests. 4(b) One mark for each correct marking point (Max 4) 4 MP1 The router reads the IP address of the destination from the packet header. MP2 A router uses a routing table to find information … MP3 … about e.g., available hops / netmask / gateway used / adjacent routers / the status of the routers along the route. MP4 The router determines the next hop / optimum route. // The router sends the packet on its next hop. MP5 The router manages the hop counter // The hop counter is reduced by 1 every time the packet passes a router.

5 Complete the table by filling in the missing object-oriented programming (OOP) terms and descriptions. OOP term Description A method that accesses the value of a property. ...................................... A method that changes the value of a property. ...................................... ................................................................................................. Object ................................................................................................. ................................................................................................. ................................................................................................. Method ................................................................................................. ................................................................................................. [4]

Mark scheme: 5 One mark per correct answer (Max 4) 4 OOP Term Purpose Getter A method that accesses the value of a property Setter A method that changes the value of a property Object An instantiation / instance of a class Method A programmed function / procedure / subroutine / subprogram defined as part of a class

6 The management and scheduling of processes are tasks carried out by an operating system. (a) Describe one reason why scheduling is necessary in process management. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Explain the function of the round robin scheduling routine and give a benefit of this routine. Function .................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Benefit ...................................................................................................................................... ................................................................................................................................................... [4]

Mark scheme: 6(a) One mark for each mark point (Max 2) 2 • Process scheduling is required to ensure that all processes are executed in a timely manner • … and enables multitasking/multiprogramming/multiprocessing • … to minimise CPU idle time • … to ensure that no process is starved of resources. // … to ensure fair access to resources. • … ensures jobs/processes are completed in order of priority. 6(b) One mark for each mark point (Max 3) 4 MP1 Processes are queued as they arrive. MP2 It is a pre-emptive scheduling routine. MP3 A fixed time quantum is given to each process. // Each process has an equal time slice. MP4 When a time slice ends, the status of the process is saved/queued so it can continue from where it left off in its next time slice. MP5 and the next process is executed for its time slice; its previous state is reinstated/restored, if applicable. MP6 If a process completes within its time slice, the next process is executed for its time slice. One mark for benefit (Max 1) MP7 Reduces average response time by limiting each process to a fixed amount of time. MP8 No issue with starvation of resources.

7 Secure Socket Layer (SSL) and Transport Layer Security (TLS) are two protocols. Explain how SSL/TLS is used when client-server communication is initiated. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .................................................................................................................................................... [4]

Mark scheme: 7 One mark for each correct marking point (Max 4) 4 MP1 An SSL/TLS connection is initiated by an application/client. MP2 Every new session begins with a handshake as defined by the SSL/TLS protocols. MP3 The client requests the digital certificate from the server // The server sends the digital certificate to the client. MP4 The client verifies the server’s digital certificate MP5 … and obtains the server’s public key. MP6 The encryption algorithms are agreed. // The symmetric session keys are generated/defined. MP7 A secure session is established between client and server.

8 Explain the process of syntax analysis during program compilation. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .................................................................................................................................................... [4]

Mark scheme: 8 One mark per mark point (Max 4) 4 MP1 It is the second stage of compilation // It’s the compilation stage after lexical analysis. MP2 It takes input from the lexical analyser in the form of token streams. MP3 The source code is analysed / parsed against the rules of the language to detect any errors in the code. MP4 The output from this phase is a parse tree. MP5 Syntax errors are reported.

9 Several syntax diagrams are shown. upper digit J 0 K 1 L 2 V 3 X 4 Z 5 lower 6 a 7 e 8 i 9 p u y lower lower passcode upper digit digit digit (a) State why JJ90 is not a valid passcode for the given syntax diagrams. ................................................................................................................................................... ............................................................................................................................................. [1] (b) Complete the Backus-Naur Form (BNF) for <upper> and <passcode>. <upper> ::= .......................................................................................................................... ................................................................................................................................................... <passcode> ::= ................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (c) A character can be an upper, a lower or a digit. The rules for passcode have been changed so that the third character may also be selected from upper and the final character may be repeated one or more times. Complete the syntax diagram for passcode to show these changes. lower lower passcode upper digit digit digit [2]

Mark scheme: 9(a) The second character must come from either lower or digit. It can’t be upper. 1 9(b) Max 3 3 One mark MP1 <upper> ::= J | K | L | V | X | Z Either: fully written out answer MP2 Any two correct options for <passcode> MP3 Remaining two options correct for <passcode> Example answer <passcode> ::= <upper><lower><lower><digit>| <upper><lower><digit><digit>| <upper><digit><digit><digit>| <upper><digit><lower><digit> Or: answer with interim expression MP4 <passcode> ::= <upper><middle><middle><digit> MP5 <middle> ::= <lower>|<digit> 9(c) One mark per mark point 2 MP1 Box for upper in correct place with correct connections MP2 Correct repetition arrow for final digit lower lower passcode upper digit digit digit upper

10 (a) State the purpose of the A* and Dijkstra’s algorithms. ................................................................................................................................................... ............................................................................................................................................. [1] (b) Outline the difference between the A* and Dijkstra’s algorithms. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (c) Explain how unsupervised learning takes place in machine learning. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 10(a) To find the path between two points on a graph using the algorithm. 1 10(b) One mark per point (Max 2) 2 MP1 A* tries to find a better path (between two points) by using a heuristic function // A* finds the adjacent route with the shortest path and continues this until the destination is reached MP2 … Dijkstra’s just explores all possible routes. MP3 The heuristic function on the A* algorithm gives priority to nodes that are supposed to be better than others / less costly than others. MP4 Dijkstra’s algorithm cannot work with negative values/weights //A* algorithm can work with negative values/weights. 10(c) One mark for each mark point (Max 3) 3 MP1 Unsupervised learning uses algorithms to analyse / cluster MP2 … unlabelled data sets MP3 They discover hidden patterns / data groupings / clusters without the need for human intervention. MP4 It is able to discover similarities and differences in data / information.

11 The pseudocode algorithm below allows a user to input a new stock item. The random file is searched for the next empty location in the file and the new item is inserted there. A suitable message is displayed if the file is full. Complete this pseudocode. DECLARE Location : INTEGER DECLARE NewStock : STRING DECLARE CurrentStock : STRING DECLARE Stored : BOOLEAN DECLARE Max : INTEGER Max ← 100000 Stored ← FALSE Location ← 1 .......................................................................................................................................................... OUTPUT "Enter the new item you wish to store: " INPUT NewStock WHILE NOT Stored AND Location <= Max .................................................................................................................................................... GETRECORD "StockList.dat", .......................................................................................... IF CurrentStock = "" THEN ...................................................................................... "StockList.dat", NewStock Stored ← TRUE ELSE Location ← Location + 1 ENDIF ENDWHILE ................................................................................................................................................ THEN OUTPUT "The new item has not been stored as the file was full." ENDIF CLOSEFILE "StockList.dat" [5]

Mark scheme: 11 One mark for each correctly completed line 5 DECLARE Location : INTEGER DECLARE NewStock : STRING DECLARE CurrentStock : STRING DECLARE Stored : BOOLEAN DECLARE Max : INTEGER Max  100000 Stored  FALSE Location  1 OPENFILE "StockList.dat" FOR RANDOM OUTPUT "Enter the new item you wish to store" INPUT NewStock WHILE NOT Stored AND Location <= Max SEEK "StockList.dat", Location GETRECORD "StockList.dat", CurrentStock IF CurrentStock = "" THEN PUTRECORD "StockList.dat", NewStock Stored  TRUE ELSE Location  Location + 1 ENDIF ENDWHILE IF Stored = FALSE THEN OUTPUT "The new stock item has not been stored as the file was full" ENDIF CLOSEFILE "StockList.dat"

12 (a) An array is an Abstract Data Type (ADT). Identify two other ADTs. 1 ................................................................................................................................................ 2 ................................................................................................................................................ [1] (b) A 1D array DataArray holds up to 1000 elements of type integer and needs to be sorted in ascending order. Write the pseudocode for an insertion sort to sort the array into ascending order. Use the identifiers from the table in your algorithm. You do not need to declare any arrays or variables for this algorithm. You may assume this has already been done. Identifier Data type Description Index INTEGER counter for outer loop Position INTEGER counter for inner loop – insertion position DataArray INTEGER 1D array to store up to 1000 integers Value INTEGER value to insert The first line has been written for you. FOR Index ← 2 to 1000 ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4] (c) Describe two ways in which the performance of a sort routine is affected by the data to be sorted. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... [2]

Mark scheme: 12(a) One mark for any two correct ADTs (Max 1) 1 • Binary tree • Graph • Linked list • Queue • Stack 12(b) One mark for each marking point (Max 4) 4 MP1 Temporary assignment of the element being ‘inserted’ before inner loop MP2 Appropriate inner loop MP3 Check if current DataArray content is > Value MP4 Moving data to adjacent element as required MP5 Appropriate updating of Position variable MP6 Re-insertion of the element outside the inner loop Example algorithm FOR Index  2 to 1000 Value  DataArray[Index] Position  Index – 1 IF DataArray[Position] > Value THEN WHILE Position >= 1 AND DataArray[Position] > Value DataArray[Position + 1]  DataArray[Position] Position  Position – 1 ENDWHILE DataArray[Position + 1]  Value ENDIF NEXT Index 12(c) One mark for each marking point 2 MP1 The performance of a sorting routine should improve if the data is already partially sorted // The performance of a sorting routine is likely to be worse if the data is completely out of order MP2 The sort may take longer if the number of items to be sorted is larger // The sort may take less time if the number of items to be sorted is fewer.

13 The recursive procedure Delete() is defined as follows: PROCEDURE Delete(Index, Target) IF Numbers[Index] > 0 THEN IF Numbers[Index] >= Target THEN Numbers[Index] ← Numbers[Index + 1] ENDIF Index ← Index + 1 CALL Delete(Index, Target) ENDIF ENDPROCEDURE An array Numbers is used to store a sorted data set of non-zero positive integers. Unused cells contain zero. The contents of the array at the start of the algorithm are: Numbers [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 2 3 7 11 15 17 19 23 0 0 Complete the trace table for the algorithm for the procedure call: CALL Delete(1, 15) Numbers Index Target [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 2 3 7 11 15 17 19 23 0 0 [4]

Mark scheme: 13 One mark for each marking point 4 MP1 Correct Index and Target columns MP2 Correct Numbers[5] column MP3 Correct Numbers[6] and Numbers[7] columns MP4 Correct Numbers[8] column and no incorrect data added to any other of columns [1, 2, 3, 4, 9, 10] Numbers Index Target [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 1 15 2 3 7 11 15 17 19 23 0 0 2 3 4 5 17 6 19 7 23 8 0 9