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

1 Real numbers are stored in a computer system using floating-point representation with: • 8 bits for the mantissa • 8 bits for the exponent • two’s complement form for both mantissa and exponent. (a) Write the normalised floating-point representation of +202 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (b) Write the normalised floating-point representation of –202 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (c) A binary number is stored in the computer system. Mantissa Exponent 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 (i) State why the number is not normalised. ........................................................................................................................................... ..................................................................................................................................... [1] (ii) Write the normalised floating-point representation of the number. Mantissa Exponent [2]

Mark scheme: Question Answer Marks 1(a) Two marks for working 3 One mark for correct answer Working: Conversion to binary + 202 = 11001010 // repeated division by 2 // 128 + 64 + 8 + 2 Appropriate shifting of binary point for + 202 = 0.1100101  28 // exponent = 8 Answer: = 01100101 00001000 (stored as mantissa and exponent) 1(b) Two marks for working 3 One mark for correct answer Working: • Appropriate method of conversion e.g. = 10011010 (one’s complement of 8-bit mantissa) = 10011011 (two’s complement of 8-bit mantissa) –256 + 32 + 16 + 4 +2 • Realisation that the exponent doesn’t change // value of exponent = 8 // appropriate shifting of binary point Answer: = 10011011 00001000 (stored as mantissa and exponent) 1(c)(i) The mantissa does not begin with 01/10 (as its most significant bits) 1 // the mantissa begins with 00 // first two digits are the same. 1(c)(ii) One mark for each point: 2 • Correct mantissa • Correct exponent Mantissa Exponent 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0

More questions on Floating-point numbers, representation and manipulation

2 Outline the functions of the Transport and Internet layers of the TCP/IP protocol suite. Transport layer ................................................................................................................................. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... Internet layer .................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... [5]

Mark scheme: 2 One mark for each point (Max 3) 5 MP1 The Transport Layer breaks data into manageable packets / performs segmentation MP2 It sequences the packets // adds data to the packet header // adds a packet header MP3 It sends the packets to the Internet / Network Layer // It receives data from the Application Layer MP4 It controls the flow of packets MP5 It handles packet loss/corruption // Acknowledges receipt of complete error free packets One mark for each point (Max 3) MP6 The Internet Layer identifies the intended network and host MP7 It transmits packets to the (Data) Link / Physical Layer MP8 It routes the packets independently through the optimum route MP9 It addresses packets with their source and destination IP addresses MP10 It then uses an IP address and port number to form a socket.

3 (a) State what is meant by the term enumerated data type. ................................................................................................................................................... ............................................................................................................................................. [1] (b) State what is meant by the term pointer data type. ................................................................................................................................................... ............................................................................................................................................. [1] (c) The months of the year are: January, February, March, April, May, June, July, August, September, October, November and December. Write the pseudocode statement to define the data type Quarter1, to hold the names of the first three months of a year. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (d) The composite data type Pet is used to store data about the various pets of a group of students. It uses these fields: Field name Data type PetName String AnimalType String PetAge Integer PetGender Char OwnerName String (i) Write the pseudocode statement to set up a variable for one record of the composite data type Pet. ........................................................................................................................................... ..................................................................................................................................... [1] (ii) Write pseudocode to store the details of the following pet, in the variable you set up in part (d)(i). PetName AnimalType PetAge PetGender OwnerName Tibbles Cat 8 M Jasmine Smith ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [3]

Mark scheme: 3(a) A (user-defined non-composite) data type with an ordered list of possible values. 1 3(b) A user-defined non-composite data type used to reference a memory location. 1 3(c) Marks as shown in the square brackets: 2 TYPE Quarter1 = (January, February, March) TYPE Quarter1 = [1] (January, February, March) [1] 3(d)(i) DECLARE Pet1 : Pet 1 3(d)(ii) One mark for each point: 3 • Correct assignment of all string data values • Correct assignment of char data value • Correct assignment of integer data value Example answer: Pet1.PetName  "Tibbles" Pet1.AnimalType  "Cat" Pet1.PetAge  8 Pet1.PetGender  'M' Pet1.OwnerName  "Jasmine Smith"

More questions on Data Types and Records

4 Draw one line to connect each stage of compilation to its most appropriate description. Stage of compilation Description minimising a program’s execution time and memory requirement Lexical analysis converting an intermediate representation of source code into an executable form Syntax analysis converting a sequence of characters into a sequence of tokens Code generation directly executing instructions written in a scripting language Optimisation using parsing algorithms to interpret the meaning of a sequence of tokens [4]

Mark scheme: 4 One mark for each correct line connecting one stage of compilation to a description 4

5 (a) Write the infix expression in Reverse Polish Notation (RPN). a * b + b - d + 15 ................................................................................................................................................... ............................................................................................................................................. [1] (b) (i) Write the RPN expression in infix form. a b - c d + * a / ........................................................................................................................................... ..................................................................................................................................... [1] (ii) Evaluate your infix expression from part (b)(i) when a = 5, b = 10, c = 27 and d = 12. ........................................................................................................................................... ..................................................................................................................................... [1]

Mark scheme: 5(a) a b * b + d - 15 + 1 5(b)(i) (a - b) * (c + d) / a 1 5(b)(ii) –39 1

More questions on Introduction to Abstract Data Types (ADT)

6 A message is encrypted using a private key and sent to an individual using asymmetric encryption. (a) State what is meant by a private key. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Describe the process of asymmetric encryption. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (c) Explain how a digital signature is used to verify a message when it is received. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 6(a) One mark for each correct point (Max 2) 2 • A private key is the unpublished/secret key/never transmitted anywhere. • It has a matching public key • It is used to decrypt data that was encrypted with its matching public key. 6(b) One mark for each correct point (Max 2) 2 • The message to be sent is encrypted using the recipient’s public key. // The message to be sent is encrypted using the sender’s private key. • The message is decrypted using the recipient’s private key. // The message is decrypted using the sender’s public key. 6(c) One mark for each correct point (Max 4) 4 • The message together with the digital signature is decrypted using the receiver’s private key • The digital signature received is decrypted with the sender’s public key to recover the message digest sent • The decrypted message received is hashed with the agreed hashing algorithm to reproduce the message digest of the message received • The two message digests are compared • … if both digests are the same the message has not been altered // if they are different the message has been altered.

7 (a) Complete the Karnaugh map (K-map) for the 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 00 01 11 10 CD 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 expression from your answer to part (b) as a simplified sum-of-products. Use Boolean algebra to give your answer in its simplest form. Simplified sum-of-products Z = ............................................................................................................................................ Simplest form Z = ............................................................................................................................................ [3]

Mark scheme: 7(a) Two marks if no errors present 2 One mark if one error present AB 00 01 11 10 CD 00 0 1 1 1 01 0 1 1 1 11 0 0 0 0 10 0 0 0 0 7(b) One mark for correct loop (Max 2) 2 7(c) One mark for each point 3 • Any correct Boolean term • Boolean terms and operator correct and no other terms present _ _ (Z =) BC + AC One mark for simplest form _ (Z =) C (A + B)

8 Virtual memory, paging and segmentation are used in memory management. (a) Explain what is meant by virtual memory. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (b) State one difference between paging and segmentation in the way memory is divided. ................................................................................................................................................... ............................................................................................................................................. [1]

Mark scheme: 8(a) One mark for each correct point (Max 3) 3 • Disk / secondary storage is used to extend the RAM / memory available • … so the CPU appears to be able to access more memory space than the available RAM • Only the data in use needs to be in main memory so data can be swapped between RAM and virtual memory as necessary • Virtual memory is created temporarily. 8(b) One mark for a correct statement about the difference between paging and segmentation e.g. 1 • Paging allows the memory to be divided into fixed size blocks and Segmentation divides the memory into variable sized blocks. • The operating system divides the memory into pages, the compiler is responsible for calculating the segment size. • Access times for paging is faster than for segmentation.

9 Deep learning is used in Artificial Intelligence (AI). (a) Describe what is meant by deep learning. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Outline the reasons for using deep learning. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: 9(a) One mark for each correct point (Max 2) 2 • Uses artificial neural network(s) • … that contain(s) a high number of hidden layers • … modelled on the human brain. • Deep learning uses many layers to progressively extract higher level features from the (raw) input. • Deep learning is a specialised form of machine learning. 9(b) One mark for each correct point (Max 2) 2 • Deep learning makes good use of unstructured data. • Deep learning outperforms other methods if the data size is large. • Deep learning systems enable machines to process data with a nonlinear approach. • Deep learning is effective at identifying (hidden) patterns / patterns that humans might not be able to see / patterns that are too complex / time consuming for humans to carry out. • It can provide a more accurate outcome with higher numbers of hidden layers.

10 Reduced Instruction Set Computers (RISC) and Complex Instruction Set Computers (CISC) are two types of processor. (a) Tick (3) one box in each row to show if the statement applies to RISC or CISC processors. Statement RISC CISC uses a smaller instruction set uses single-cycle instructions and limited addressing modes uses fewer general-purpose registers uses both hardwired and micro-coded control unit uses a system where cache is split between data and instructions [2] (b) Describe the process of pipelining during the fetch-execute cycle in RISC processors. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 10(a) Two marks for all five rows correct 2 One mark for four rows correct Statement RISC CISC uses a smaller instruction set ✓ uses single-cycle instructions and limited addressing modes ✓ uses fewer general-purpose registers ✓ uses both hardwired and micro coded control unit ✓ uses a system where cache is split between data and ✓ instructions 10(b) One mark for each correct point (Max 4) 4 • Instructions are divided into subtasks / 5 stages • … Instruction fetch / IF, Instruction decode / ID, operand fetch / OF, opcode/instruction execute IE, result store / write back result / WB • Each subtask is completed during one clock cycle • No two instructions can execute their same stage at the same clock cycle • The second instruction begins in the second clock cycle, while the first instruction has moved on to its second subtask. • The third instruction begins in the third clock cycle while the first and second instructions move on to their second and third subtasks, respectively, etc.

11 (a) Define these Object-Oriented Programming (OOP) terms: Instance .................................................................................................................................... ................................................................................................................................................... Inheritance ................................................................................................................................ ................................................................................................................................................... Polymorphism ........................................................................................................................... ................................................................................................................................................... [3] (b) In OOP, a class contains attributes and methods. Complete the pseudocode for the class Car to enable objects to be created. The class needs to include: • string attributes to store the make, model, body type and fuel type • an integer attribute to store the number of cars of that type built. The attributes must be available only through the methods of the class. CLASS ..................................... PRIVATE Make : STRING PRIVATE ................................................................ ................................................................................ ................................................................................ ................................................................................ PUBLIC PROCEDURE New(CarMake : STRING, ................................................... , .....................................................) Make ...................................... ← Model ...................................... ← BodyType CarBodyType ← Fuel "" ← NumberBuilt 0 ← ENDPROCEDURE GetFuel() GetNumberBuilt() ..................................... [5]

Mark scheme: 11(a) One mark for each correct OOP term definition: 3 • Instance – an occurrence of an object // a specific object based on the class // an instantiation of a class. • Inheritance – the capability of defining a new class of objects that has all the attributes and methods from a parent class. • Polymorphism – allows the same method to take on different behaviours depending on which class is instantiated // methods can be redefined for derived classes. 11(b) One mark for each point: 5 • Car and ENDCLASS • Four declarations – must use the identifiers used in the assignments • Constructor header – must use CarBodyType • Two assignments – must use CarMake • Constructor identifier for the car model and the identifier in the Model assignment statement match CLASS Car PRIVATE Make : STRING PRIVATE Model : STRING PRIVATE BodyType : STRING PRIVATE Fuel : STRING PRIVATE NumberBuilt : INTEGER PUBLIC PROCEDURE NEW (CarMake : STRING, CarModel : STRING, CarBodyType : STRING) Make  CarMake Model  CarModel BodyType  CarBodyType Fuel  "" NumberBuilt  0 ENDPROCEDURE getFuel() getNumberBuilt() ENDCLASS

More questions on Programming Paradigms

12 (a) The array Names[0:99] is in alphabetical order. Complete this pseudocode binary search algorithm. Lower 0 ← ...................................................................................................... Mid 0 ← Exit FALSE ← OUTPUT "Enter the name to be found " INPUT Target REPEAT ....................................................................................................... THEN OUTPUT Target, " does not exist" Exit TRUE ← ENDIF Mid Lower + (Upper – Lower + 1) DIV 2 ← IF Names[Mid] < Target THEN Lower ..................................................................................................... ← ENDIF IF Names[Mid] > Target THEN ..................................................................................................... ENDIF ...................................................................................................... THEN OUTPUT Target, " was found at location ", Mid Exit TRUE ← ENDIF ...................................................................................................... [6] (b) Big O notation is used to classify efficiency of algorithms. The Big O notation for time complexity in a binary search is O(log n). (i) State the Big O notation for time complexity of a linear search. ..................................................................................................................................... [1] (ii) Describe the meaning of O(log n) as it applies to a binary search algorithm. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2]

Mark scheme: 12(a) One mark for each point (Max 6) 6 • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower  0 Upper  99 Mid  0 Exit  FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit  TRUE ENDIF Mid  Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower  Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper  Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit  TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE 12(b)(i) O(n) 1 12(b)(ii) One mark for each point (Max 2) 2 • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search).

More questions on Algorithms