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

1 Normalised floating-point numbers are stored in a computer system using two’s complement for both the mantissa and the exponent with: • 11 bits for the mantissa • 5 bits for the exponent. (a) Write the largest positive two’s complement binary number that can be stored in this system. Mantissa Exponent [1] (b) Calculate the denary value of the given binary floating-point number. Show your working. Mantissa Exponent 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Answer ...................................................................................................................................... [3] (c) State when underflow occurs in a binary floating-point system. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: Question Answer Marks 1(a) Mantissa Exponent 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1(b) Two marks for working 3 • correct calculation of exponent seen • correct application of exponent to mantissa seen One mark for correct answer Working: = 1.0110010011  29 //exponent = 9 = 1011001001.1 (moving bp 9 places to right) // evaluate two’s complement For example: –512 + 128 + 64 + 8 + 1 + 0.5 Answer: –310.5 // –3101/2 1(c) One mark per point 2 • Following an arithmetic/logical operation • … the result is too small to be precisely represented in the available system // When the number of bits is not enough / too small for the computer’s allocated word size / to represent the binary number

More questions on Floating-point numbers, representation and manipulation

2 Lexical analysis and syntax analysis are stages in the compilation of a program. (a) Identify two other stages that take place during the compilation of a program. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... [2] (b) Outline the purpose of syntax analysis. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: 2(a) One mark per point 2 • Code generation • Optimisation 2(b) One mark per point (Max 2) 2 • It checks that the code matches the grammar of the language // It checks that the tokens conform with the rules of the programming language • Syntax errors are reported • A parse tree is produced.

3 (a) Explain why a protocol is used in communication between computers. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) The TCP/IP protocol implementation can be viewed as a stack. Complete the diagram for the TCP/IP protocol stack. Transport Link [2] (c) Describe the purpose of the IMAP protocol. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: 3(a) One mark per point (Max 2) 2 • Protocols set a standard for communication • Protocols enable communication/compatibility between devices from different manufacturers/platforms • If two devices were sending messages to each other but using different protocols, they would not be able to communicate properly 3(b) One mark for each correct answer 2 Application (Layer) Transport Internet/Network (Layer) Link 3(c) One mark per point (Max 2) 2 • used by email clients to retrieve email messages // a pull protocol • from a mail server (over a TCP/IP connection) • keeps the server and client in sync (by not deleting the original email). // allows a copy of the email to be downloaded from the mail server.

4 A program to manage regular flight details at an airport requires some user-defined data types. (a) Write pseudocode statements to declare the enumerated data type Aircraft to hold data about the types of aircraft used for a flight. These types of aircraft are: C300, C350, D242, E757, X380. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Write pseudocode statements to declare the composite data type Flight to hold data about flights to a specific destination. These include: • flight number, which could be any combination of letters and numbers • destination • date of departure • type of aircraft used. Use the enumerated data type you created in part (a). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4] (c) (i) Write the pseudocode statement to set up a variable for one record of the composite data type Flight. ........................................................................................................................................... ..................................................................................................................................... [1] (ii) Write pseudocode to store the details of the following flight in the variable you set up in part (c)(i). Field Data flight number XA782 destination Cambridge date of departure 12/12/2022 type of aircraft used C350 Use the field names you created in part (b). ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [3]

Mark scheme: 4(a) Marks as shown in the square brackets: 2 TYPE Aircraft = (C300, C350, D242, E757, X380) TYPE Aircraft = [1] (C300, C350, D242, E757, X380) [1] 4(b) One mark for each point (Max 4) 4 • TYPE Flight and ENDTYPE correct • DECLARE FlightNumber and DECLARE Destination as STRING • DECLARE DepartureDate as DATE • DECLARE AircraftType as Aircraft (correct data type from part 4(a)) Example answer: TYPE Flight DECLARE FlightNumber : STRING DECLARE Destination : STRING DECLARE DepartureDate : DATE DECLARE AircraftType : Aircraft ENDTYPE 4(c)(i) Example answer: 1 DECLARE Flight1 : Flight 4(c)(ii) One mark for each point (Max 3) 3 • Correct assignments of both string data values • Correct assignments of date data value • Correct assignments of enumerated data value Example answer: Flight1.FlightNumber  "XA782" Flight1.Destination  "Cambridge" Flight1.DepartureDate  12/12/2022 Flight1.AircraftType  C350

More questions on Data Types and Records

5 Describe what is meant by a virtual machine. Include in your answer two benefits and two drawbacks of using a virtual machine. Description ....................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... Benefit 1 ........................................................................................................................................... .......................................................................................................................................................... Benefit 2 ........................................................................................................................................... .......................................................................................................................................................... Drawback 1 ...................................................................................................................................... .......................................................................................................................................................... Drawback 2 ...................................................................................................................................... .......................................................................................................................................................... [6]

Mark scheme: 5 One mark for each description (Max 2) 6 • The emulation of a computer system / hardware and/or software • … using a host computer system. • Using guest operating system(s) for emulation. One mark for each correct benefit (Max 2) • Multiple guest operating systems / VMs can be used on the same computer. • Different instruction set architectures can be emulated on a single computer. • A virtual machine can crash without affecting the host machine. • There are security benefits // Trying a piece of suspicious software and if it is / has a virus, it will only infect the virtual machine. • Cost savings due to not needing to purchase extra hardware. • Can run legacy applications that are currently incompatible. One mark for each correct drawback (Max 2) • A virtual machine is less efficient / has poorer performance than real machines because of extra load on the host computer • Performance of the guest system cannot be adequately measured. • A virtual machine may be affected by any weaknesses of the host machine. • Costly and/or complex to maintain / implement / manage. • Cannot emulate some hardware.

6 (a) State two differences between symmetric and asymmetric encryption. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Explain the process by which an organisation may acquire its digital certificate. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 6(a) One mark for each point 2 • Symmetric encryption uses a single key and asymmetric encryption uses a pair of keys. • The symmetric single key is used by all, whereas only one of the keys for asymmetric encryption is available to everyone / one of the asymmetric encryption keys needs to be kept secret. 6(b) One mark for each point (Max 4) 4 • The organisation requests a certificate from a Certificate Authority (CA) • The organisation may send their public key to CA • The organisation gathers all the information required by the CA in order to obtain their certificate, which includes information to prove their identity • The CA verifies the organisation’s identity • The CA generates / issues the certificate including the organisation’s public key (and other information).

7 Supervised and unsupervised learning are two categories of machine learning. Describe supervised learning and unsupervised learning. Supervised learning ......................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... Unsupervised learning ..................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... [4]

Mark scheme: 7 One mark for each point 4 Supervised learning (Max 3 of 4) • Supervised learning allows data to be collected, or a data output produced, from the previous experience. • In supervised learning, known input and associated outputs are given // uses sample data with known outputs (in training) // uses labelled input data. • Able to predict future outcomes based on past data. Unsupervised learning (Max 3 of 4) • Unsupervised machine learning helps all kinds of unknown patterns in data to be found. • Unsupervised learning only requires input data to be given. • Uses any data // not trained on the right output // uses unlabelled input data.

8 (a) Draw a logic circuit for an SR flip-flop and label the inputs. ................. Q Q¯ ................. [4] (b) State the purpose of a flip-flop. ................................................................................................................................................... ............................................................................................................................................. [1] (c) Simplify the following expression using Boolean algebra, including De Morgan’s laws. Show your working. (A.B).(A.C).(B.D) Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Answer ...................................................................................................................................... [3]

Mark scheme: 8(a) One mark for each point (Max 4) 4 • One correct NAND or NOR gate with two separate inputs and one output • Second correct logic gate of same type as first with two separate inputs and one output • Correct connections between logic gates • Correctly labelled inputs Example answers: S/Set R/Reset 8(a) Or R/Reset S/Set 8(b) To store a binary digit / (single) bit. 1 8(c) One mark for each point (Max 3) 3 • Correct application of De Morgan’s Law • Correct application of Double Negation Law or Distributive Law • Correct answer (A.B).(A.C).(B.D) (A.B) + (A.C) + (B.D) [1] _ _ _ (A.B) + (A.C) + (B.D) [1] _ _ A. (B + C) + B.D [1]

9 (a) Explain the need for scheduling in process management. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (b) Describe these scheduling routines and identify a benefit for each one. Shortest job first ........................................................................................................................ ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Round robin .............................................................................................................................. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... First come first served .............................................................................................................. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [6]

Mark scheme: 9(a) One mark for each point (Max 3) 3 • Process scheduling allows more than one program/task to appear to be executed at the same time / enables multi- tasking / multiprogramming. • To allow high priority jobs to be completed first. • To keep the CPU busy all the time • … to ensure that all processes execute efficiently • … and to have reduced wait times for all processes / to ensure all processes have fair access to the CPU / prevent starvation of some processes. 9(b) One mark for each point (Max 2) for Shortest job first: 6 • Process are executed in ascending order of the amount of CPU time required // Short processes are executed first and followed by longer processes. • …which leads to an increased throughput (because more processes can be executed in a smaller amount of time). One mark for each point (Max 2) for Round robin: • Each process is served by the CPU for a fixed time/time slice (so all processes are given the same priority). • Starvation doesn’t occur (because for each round robin cycle, every process is given a fixed time/time slice to execute). One mark for each point (Max 2) for First come first served: • No complex logic, each process request is queued as it is received and executed one by one. • Starvation doesn’t occur (because every process will eventually get a chance to run) // less processor overhead.

10 (a) Define these Object-Oriented Programming (OOP) terms: Encapsulation ........................................................................................................................... ................................................................................................................................................... Getter ........................................................................................................................................ ................................................................................................................................................... Setter ........................................................................................................................................ ................................................................................................................................................... [3] (b) A school has a program written using OOP to maintain its staff and student records. The object SubstituteTeacher allows the details of the school’s substitute teachers to be stored. This includes their full name, telephone number and whether or not they are in school today. For example: SubName Sarah Jones Telephone 01223658721 InSchool TRUE Complete the diagram for the object SubstituteTeacher, including appropriate properties and their getters and setters. SubstituteTeacher SubName : STRING .................................................................................................... InSchool : BOOLEAN .................................................................................................... SetTelephone(Tel : STRING) .................................................................................................... GetSubName() .................................................................................................... .................................................................................................... [3]

Mark scheme: 10(a) One mark for each correct OOP term definition 3 • Encapsulation – putting properties and methods inside a class // ensures sensitive data is hidden from users by hiding values of a structured data object inside a class. • Getter – method that is used to return the value of a property. • Setter – method that is used to update the value of a property. 10(b) One mark for each point 3 • properties correct • setters correct • getters correct SubstituteTeacher SubName : STRING Telephone : STRING InSchool : BOOLEAN SetSubName(StaffName : STRING) SetTelephone(Tel : STRING) SetInSchool(Present : BOOLEAN) GetSubName() GetTelephone() GetInSchool()

More questions on Programming Paradigms

11 A simplified linked list is used to store the names of flowers in alphabetical order. It is implemented using two 1D arrays: • Flower stores the names of the flowers. • NextPointer stores the pointer to the next flower name in the list. HeadPointer indicates the index of the first flower name in the linked list. HeadPointer 6 When the end of the linked list is reached, the next pointer has the value of 0. The following table shows the initial content of the arrays. Index Flower NextPointer 1 Rose 7 2 Marigold 1 3 Foxglove 10 4 Iris 9 5 Daisy 3 6 Dahlia 5 7 Saxifrage 0 8 Lupin 2 9 Lily 8 10 Hydrangea 4 (a) Several flower names have been deleted from the linked list. These are crossed out in the following table. Complete the table to show the new values of HeadPointer and NextPointer to keep the remaining flower names in alphabetical order. HeadPointer Index Flower NextPointer 1 Rose 2 Marigold 3 Foxglove 4 Iris 5 Daisy 6 Dahlia 7 Saxifrage 8 Lupin 9 Lily 10 Hydrangea [3] (b) Complete the pseudocode algorithm so that it achieves the following when applied to the arrays: • The flower name is input. • The linked list is searched, in order, for the flower name. • If the flower name is found, an appropriate message is output to indicate it has been found. • If the flower name is not found, an appropriate message is output to indicate it has not been found. • The algorithm terminates when the next pointer value is 0. Pointer HeadPointer Found 0 OUTPUT "Enter a flower name " IF Flower[Pointer] = FlowerName THEN Found Pointer Pointer 0 ELSE ENDWHILE ELSE [5] (c) Explain how you could improve the simplified linked list structure. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

Mark scheme: 11(a) One mark for each point 3 • Correct HeadPointer • Any three correct NextPointer • All six NextPointer correct HeadPointer 5 Index Flower NextPointer 1 Rose 0 2 Marigold 3 Foxglove 4 4 Iris 9 5 Daisy 3 6 Dahlia 7 Saxifrage 8 Lupin 1 9 Lily 8 10 Hydrangea 11(b) One mark for each correct line 5 Pointer  HeadPointer Found  0 OUTPUT "Enter a flower name " INPUT FlowerName WHILE Pointer <> 0 IF Flower[Pointer] = FlowerName THEN Found  Pointer Pointer  0 ELSE Pointer  NextPointer[Pointer] ENDIF ENDWHILE IF Pointer = 0 THEN // IF Found <> 0 THEN OUTPUT Flower[Found], " is found" ELSE OUTPUT "The flower you wanted is not in the list" ENDIF 11(c) One mark for each point (Max 2) 2 • Include a free list pointer • …to reuse the unused space • …as a linked list of free space.

More questions on Introduction to Abstract Data Types (ADT)