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

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] (b) Explain the problem that occurred in part (a) when representing the number in system 2. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: Question Answer Marks 1(a) One mark per mark point (Max 4) 4  conversion of 113.75 to binary seen 1110001.11  exponent for normalisation 7 converted to binary 111 // evidence of binary point moved 7 places // evidence of finding exponent = 7  system 1 answer  system 2 answer showing correct version from system 1 System 1 Mantissa Exponent 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 System 2 Mantissa Exponent 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1(b) One mark per mark point (Max 2) 2  the mantissa in system 2 does not have enough bits to store the whole binary number // 10 bits required and only 8 bits available  so precision is lost / the number is truncated

More questions on Floating-point numbers, representation and manipulation

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]

Mark scheme: 2(a) One mark for each correct line connecting a machine learning technique to its 4 most appropriate description (Max 4). 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- Reinforcement output pairs 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 2(b) One mark per mark point (Max 2) 2  to find the optimal / shortest / most cost-effective route  … between two nodes in a  … based on distance / cost / time.

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]

Mark scheme: 3(a) One mark for each correct hash value (Max 2) 2 Record key Hash value 1030 1 1050 0 1025 2 3(b) One mark per mark point (Max 4) 4 MP1 A collision occurs when the record key doesn’t match the stored record key MP2 … this means the determined storage location has already been used for another record. If the record is to be stored MP3 Search the file linearly MP4 … to find the next available storage space (closed hash) MP5 Search the overflow area linearly MP6 … to find next available storage space (open hash) If the record is to be found MP7 … search the overflow area linearly (open hash) until the matching record key is found MP8 … search linearly from where you are (closed hash) until the matching record key is found MP9 If not found record is not in file

More questions on File organisation and access

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]

Mark scheme: 4(a) One mark per mark point (Max 2) 2  TYPE Prime  = (2, 3, 5, 7, 11, 13, 17, 19) Example answer TYPE Prime = (2, 3, 5, 7, 11, 13, 17, 19) 4(b) One mark per mark point (Max 2) 2  TYPE TDayPointer  = ^STRING //^DayOfWeek Example answer TYPE TDayPointer = ^STRING // ^DayOfWeek

More questions on User-defined data types

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]

Mark scheme: 5(a) One mark per mark point (Max 2) 2  Circuit switching is used where a dedicated path needs to be sustained throughout the call / communication // where the whole bandwidth is required // where a real time communication is used.  A typical application is standard voice communications / video streaming / private data networks 5(b) One mark per benefit (Max 2) 4 MP1 Whole of bandwidth is available MP2 Dedicated communication channel increases the quality of transmission MP3 Data is transmitted with a fixed data rate MP4 No waiting time at switches MP5 Suitable for long continuous communication MP6 Fast method of data transfer MP7 Data arrives in the same order as it was sent MP8 Data can’t get lost MP9 Data all follows the same path / route MP10 Better for real-time MP11 Simple method of data transfer. One mark per drawback (Max 2) MP1 A dedicated connection makes it impossible to transmit other data even if the channel is free MP2 Not very flexible MP3 No alternative route in case of failure MP4 The time required to establish the physical link between the two stations can be too long MP5 The need to establish a dedicated path for each connection can have cost implications MP6 Dedicated channels require the whole bandwidth / bandwidth can’t be shared

6 Several syntax diagrams are shown. operator digit + 0 – 1 * 2 / 3 symbol 4 $ 5 % 6 & 7 @ 8 # letter 9 A D P R Y password letter digit symbol (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]

Mark scheme: 6(a) One mark per correct valid/invalid and reason combination (Max 3) 3 DPAD99$ – Valid Reason – 4/multiple letters followed by 2/multiple digits followed by a symbol. DAD#95 – Invalid Reason – The symbol comes before the digits – it should be after. ADY123? – Invalid Reason – The ? is not a valid symbol. 6(b) <symbol> ::= $ | % | & | @ | # 1 <letter> ::= A | D | P | R | Y 6(c) One mark per mark point (Max 4) 4  begins with a letter  letter can repeat and digit present  digit can repeat or can be bypassed  correct structure – name, boxes and arrows (in and out). Example answers: identifier letter digit identifier letter letter digit

More questions on Program Design

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]

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

8 Outline the characteristics of massively parallel computers. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .................................................................................................................................................... [3]

Mark scheme: 8 One mark per mark point (Max 3) 3 MP1 A large number of computer processors / separate computers connected together MP2 … simultaneously performing a set of coordinated computations // collaborative processing MP3 network infrastructure MP4 communicate using a message interface / by sending messages.

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]

Mark scheme: 9(a) One mark per mark point (Max 2) 2 MP1 To provide better security MP2 … by using two different keys / a public key and a private key MP3 One of the keys is used to encrypt the message MP4 … the matching key is used to decrypt the message. 9(b) One mark per benefit (Max 2) 4 MP1 Provides security based on laws of physics rather than mathematical algorithms, so more secure. MP2 To protect the security of data transmitted over fibre optic cables. MP3 Virtually unhackable. MP4 The performance of quantum cryptography is continuously improved, making it suitable for most valuable government/industrial secrets. MP5 Longer keys can be used MP6 Eavesdropping can be detected One mark per drawback (Max 2) MP1 Lacks many vital features such as digital signature, certified mail, etc. MP2 High cost of purchasing / maintaining equipment required. MP3 Currently only works over relatively short distances. MP4 Error rates are relatively high as technology is still being developed. MP5 Polarisation of light can change during transmission. MP6 Allows criminals and terrorists to hide their communications.

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]

Mark scheme: 10 One mark for each correctly completed line (Max 5) 5 DECLARE Account : STRING OPENFILE "ActiveFile.txt" FOR READ OPENFILE "ArchiveFile.txt" FOR WRITE WHILE NOT EOF("ActiveFile.txt") READFILE "ActiveFile.txt", Account IF Account = "" THEN WRITEFILE "ArchiveFile.txt", "Account not present" ELSE WRITEFILE "ArchiveFile.txt", Account ENDIF ENDWHILE CLOSEFILE "ActiveFile.txt" CLOSEFILE "ArchiveFile.txt"

More questions on Files

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

Mark scheme: 11(a) One mark per mark point (Max 3) 3  correctly defined constant  correctly defined array  three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER 11(b) One mark for each correctly completed line (Max 4) 4 FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length > 0 THEN Item  Queue[FrontPointer] FrontPointer  FrontPointer + 1 Length  Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer  1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error" Item  "" ENDIF RETURN Item ENDFUNCTION 11(c) One mark per mark point (Max 4) 4 MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1.

More questions on Introduction to Abstract Data Types (ADT)

12 (a) Describe what is meant by recursion. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (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]

Mark scheme: 12(a) One mark per mark point (Max 2) 2  A process using a function or procedure defined in terms of itself / calls itself.  A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described  There must (also) be a general case where the recursive call takes place. 12(b) One mark per mark point (Max 5) 5  Call number column correct  Function call and Number columns correct  Result column down to base case (Winding) rows 1–6 correct  Result column down from base case (Unwinding) rows 7–10 correct  Return value column correct Call Function call Number Result Return number value 1 Fib(5) 5 Fib(4) + Fib(3) 2 Fib(4) 4 Fib(3) + Fib(2) 3 Fib(3) 3 Fib(2) + Fib(1) 4 Fib(2) 2 Fib(1) + Fib(0) 5 Fib(1) 1 1 1 6 Fib(0) 0 0 0 (4) Fib(2) 2 1 + 0 1 (3) Fib(3) 3 1 + 1 2 (2) Fib(4) 4 2 + 1 3 (1) Fib(5) 5 3 + 2 5

More questions on Recursion