Cambridge A Level Computer Science 9618 — 2021 Oct/Nov Paper 3 · Variant 1

1 (a) Numbers are stored in a computer using floating-point representation with: • 12 bits for the mantissa • 4 bits for the exponent • two’s complement form for both the mantissa and exponent. (i) Write the normalised floating-point representation of the following unsigned binary number using this system. 1011100.011001 Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... Mantissa Exponent [2] (ii) State the consequence of storing the binary number in part (a)(i) as a floating-point number in this system. Justify your answer. Consequence .................................................................................................................... ........................................................................................................................................... Justification ....................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... [2] (b) Explain the reason why binary numbers are stored in normalised form. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: Question Answer Marks 1(a)(i) One mark for each correct marking point (Max 2) 2 • 010111000110 (correct mantissa) • 0111 (correct exponent) 1(a)(ii) One mark for each correct consequence 2 One mark for each correct justification Consequence • The precision/accuracy of the number would be reduced Justification • … because the least significant bits of the original number have been truncated/lost // the original number had 13 bits / 14 bits with sign but the mantissa can only store 12 bits 1(b) One mark for each correct marking point (Max 3) 3 • To store the maximum range of numbers in the minimum number of bytes / bits • Normalisation minimises the number of leading zeros/ones represented • Maximising the number of significant bits // maximising the (potential) precision / accuracy of the number for the given number of bits • … enables very large / small numbers to be stored with accuracy. • Avoids the possibility of many numbers having multiple representations.

More questions on Floating-point numbers, representation and manipulation

2 Draw one line from each programming paradigm to its most appropriate description. Programming paradigm Description Programs using the instruction set of a processor Declarative Programs based on events such as user actions or sensor outputs Imperative Programs using the concepts of class, inheritance, encapsulation and polymorphism Low-level Programs with an explicit sequence of commands that update the program state, Object-oriented with or without procedure calls Programs that specify the desired result rather than how to get to it [4]

Mark scheme: 2 One mark for each single correct line from Programming Paradigm to 4 Description Programming Paradigm Description Programs using the instruction set of a processor Declarative Programs based on events such as user actions or sensor outputs Imperative Programs using the concepts of class, inheritance, encapsulation and Low-level polymorphism Programs with an explicit sequence of commands that update the program Object oriented state, with or without procedure calls Programs that specify the desired result rather than how to get to it

More questions on Programming Paradigms

3 Enumerated and pointer are two non-composite data types. (a) Write pseudocode to create an enumerated type called Parts to include these parts sold in a computer shop: Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Write pseudocode to create a pointer type called SelectParts that will reference the memory location in which the current part name is stored. ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: 3(a) One mark for each marking point (Max 2) 2 • TYPE Parts = • (Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse) Complete answer TYPE Parts = (Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse) 3(b) One mark for each marking point (Max 2) 2 • TYPE SelectParts = ^ • correct data type chosen Parts Complete answer TYPE SelectParts = ^Parts

More questions on User-defined data types

4 The following syntax diagrams for a particular programming language show the syntax of: • a digit • a capital letter • a character. digit capital letter 0 A 1 E 2 I 3 O 4 U 5 character $ 6 % 7 & 8 * 9 # (a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character. ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) A password must begin with a character and be followed by one or more digits or capital letters. (i) State an example of a valid password. ..................................................................................................................................... [1] (ii) A valid password is represented by the syntax diagram: password character digit capital letter Write the BNF notation of the syntax diagram for password. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [4]

Mark scheme: 4(a) One mark for each marking point (Max 2) 2 • <character>::= • $|%|&|*|# Complete answer <character>::= $|%|&|*|# 4(b)(i) For example: $A9E3 1 4(b)(ii) One mark for each marking point (Max 4) 4 • <password>::=<character> … • … <code> • <code>::= … • … <digit>|<capital_letter> • … |<digit><code>|<capital_letter><code> Complete answer <password>::=<character><code> <code>::=<digit>|<capital_letter>|<digit><code>|<capital_ letter><code>

More questions on Program Design

5 (a) Compare sequential and serial methods of file organisation. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4] (b) State the most suitable method of file access when a record is referenced by a unique address on a disk-type storage medium. ............................................................................................................................................. [1] (c) State the most suitable method of file access when a bank stores its data records in ascending order of account number. ............................................................................................................................................. [1]

Mark scheme: 5(a) One mark for each correct marking point (Max 4) 4 • In both serial and sequential files records are stored one after the other … • … and need to be accessed one after the other • Serial files are stored in chronological order • Sequential files are stored with ordered records • … and stored in the order of the key field • In serial files, new records are added in the next available space / records are appended to the file • In sequential files, new records are inserted in the correct position. 5(b) Direct (access) 1 5(c) Sequential (access) 1

More questions on File organisation and access

6 (a) Explain how packet switching is used to transfer messages across the internet. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [5] (b) Outline the function of a router in packet switching. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 6(a) One mark for each correct marking point (Max 5) 5 • A large message is divided up into a group of smaller chunks of the same size called packets • The packet has a header and a payload • The header contains a source IP address, destination IP address (and sequence number) • Each packet is dispatched independently • … and may travel along different routes / paths • The packets may arrive out of order • … and are reassembled into the original message at the destination • If packets are missing / corrupted a re-transmission request is sent. 6(b) One mark for each correct marking point (Max 3) 3 • The router examines the packet’s header • It reads the IP address of the destination (from the packet header) • A router has access to a routing table • …containing information about, e.g., available hops / netmask / gateway used • … and the status of the routes along the route • … the router decides on the next hop / best route • … and sends the packet on its next hop.

7 (a) Write the Boolean expression that corresponds to the given truth table as a sum-of-products. INPUT OUTPUT A B C D Z 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 Z = ............................................................................................................................................ ............................................................................................................................................. [3] (b) (i) Complete the Karnaugh map (K-map) for the given truth table. AB CD 00 01 11 10 00 01 11 10 [2] (ii) Draw loop(s) around appropriate group(s) of 1s in the K-map to produce an optimal sum-of-products. [2] (iii) Write the Boolean expression from your answer to part b(ii) as a simplified sum-of-products. Z = ..................................................................................................................................... ..................................................................................................................................... [2] (iv) Write the simplified Boolean expression for your answer to part b(iii). Z = ..................................................................................................................................... ..................................................................................................................................... [1]

Mark scheme: 7(a) One mark per two correct products (Max 3) 3 _ _ _ _ _ _ (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 7(b)(i) One mark for every two correct rows or columns (Max 2) 2 AB 00 01 11 10 00 0 0 1 0 01 0 0 1 1 CD 11 0 0 1 1 10 0 0 1 0 7(b)(ii) One mark for correct loop (Max 2) 2 AB 00 01 11 10 0 1 00 0 0 01 0 0 1 1 CD 11 0 0 1 1 01 0 0 1 0 7(b)(iii) One mark per correct marking point (Max 2) 2 • A B // A D • + A D // + A B (Z =) A B + A D // A D + A B 7(b)(iv) (Z =) A (B + D) // A (D + B) 1

8 (a) Describe the purpose of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Explain how SSL/TLS protocols are used when a client-server communication is initiated. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 8(a) One mark for each correct marking point (Max 2) 2 • The SSL and TLS protocols provide communications security over the internet / network • … they provide encryption • They enable two parties to identify and authenticate each other • … and communicate with confidentiality and integrity. 8(b) One mark for each correct marking point (Max 4) 4 • An SSL/TLS connection is initiated by an application • … which becomes the client • The application which receives the connection becomes the server • Every new session begins with a handshake (as defined by the (SSL/TLS) protocols) • The client requests the digital certificate from the server // the server sends the digital certificate to the client • The client verifies the server’s digital certificate • …and obtains the server’s public key • The encryption algorithms are agreed • The symmetric • … session keys are generated / defined

9 (a) The diagram shown represents an artificial neural network. Output Layer Input Layer Hidden Hidden Layer 1 Hidden Layer 3 Layer 2 (i) State the reason for having multiple hidden layers in an artificial neural network. ........................................................................................................................................... ..................................................................................................................................... [1] (ii) Explain how artificial neural networks enable machine learning. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [4] (b) Find the shortest path between the Home and School nodes using the A* algorithm. Show your working in the table provided. The first two rows in the table have been completed. 14 Home h = 10 g = 1 4 9 A 5 C 3 7 B 6 2 6 D 6 3 7 F 1 2 3 E 3 5 School Node Cost from Home node (g) Heuristic (h) Total (f = g + h) Home 0 14 14 A 1 10 11 Final path [5]

Mark scheme: 9(a)(i) One mark for correct statement (Max 1) 1 • Enables deep learning to take place • Where the problem you are trying to solve has a higher level of complexity it requires more layers to solve • To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. 9(a)(ii) One mark for each correct marking point (Max 4) 4 • Artificial neural networks are intended to replicate the way human brains work • Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where characteristics are extracted / outputs are calculated • … this process of training / learning is repeated many times to achieve optimum outputs // reinforcement learning takes place • Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have been made. 9(b) One mark for each correct calculation as follows (Max 4) 5 • Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) One mark for correct path (Max 1): • Home  A  E  F  School Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home  A  E  F  School

10 (a) State three essential features of recursion. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... 3 ................................................................................................................................................ ................................................................................................................................................... [3] (b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (c) Identify two ADTs other than a stack. 1 ................................................................................................................................................ 2 ................................................................................................................................................ [2] (d) The function StackFull() checks whether a stack is full. The function uses the variable TopOfStack to represent the pointer to the most recent position used on the stack, and the variable Max to represent the maximum size of the stack. Assume TopOfStack and Max are global variables. FUNCTION StackFull() RETURNS BOOLEAN IF TopOfStack = Max THEN RETURN TRUE ELSE RETURN FALSE ENDIF ENDFUNCTION An algorithm AddInteger is required to add a new integer data element to a stack. The stack is implemented as an array ArrayStack. The function AddInteger() calls StackFull() and returns an appropriate message. Complete the pseudocode for the function AddInteger(). FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ENDFUNCTION [5]

Mark scheme: 10(a) One mark for each correct marking point (Max 3) 3 • Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case Unwinding can occur once the base case is reached. 10(b) One mark for each correct marking point (Max 3) 3 • A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding … to maintain the required order. 10(c) One mark for each marking point (Max 2) 2 • Linked List • Queue Binary Tree 10(d) One mark for each marking point (Max 5) 5 • Checking if stack is full / empty using IF … THEN … (ELSE) … ENDIF • … correctly using StackFull() function • RETURN suitable message if stack is full • RETURN message if space available on stack • Incrementing TopOfStack pointer if space available • Assigning new data using correct NewInteger variable • … to correct the array element in ArrayStack[] array. Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE TopOfStack ← TopOfStack + 1 ArrayStack[TopOfStack] ← NewInteger RETURN "Item added" ENDIF ENDFUNCTION

More questions on Introduction to Abstract Data Types (ADT)