Cambridge A Level Computer Science 9608 — 2019 Oct/Nov Paper 3 · Variant 3

1 Real numbers are stored using floating-point representation in a computer system. This representation uses: • 8 bits for the mantissa, followed by • 4 bits for the exponent. Two’s complement form is used for both the mantissa and the exponent. (a) (i) A real number is stored as a 12-bit normalised binary number as follows: Mantissa Exponent 0 1 0 1 0 0 1 0 0 0 1 0 Calculate the denary value for this binary number. Show your working. Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... Denary value ..................................................................................................................... [3] (ii) Calculate the normalised binary number for −3.75. Show your working. Mantissa Exponent Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... [3] (b) The number of bits available to represent a real number is increased to 16. State the effect of increasing the size of the exponent by 4 bits. ................................................................................................................................................... ............................................................................................................................................. [1] (c) State why some binary representations can lead to rounding errors. ................................................................................................................................................... ............................................................................................................................................. [1] (d) Complete the following descriptions by inserting the two missing terms. ................................................ can occur in the exponent of a floating-point number, when the exponent has become too large to be represented using the number of bits available. A calculation results in a number so small that it cannot be represented by the number of bits available. This is called ................................................ . [2]

Mark scheme: Question Answer Marks 1(a)(i) 1 mark per bullet point 3 • Exponent 0010 = 2 41 1 1 • Mantissa 0.1010010 becomes 010.10010 // // 2 + + 64 2 16 9 • Answer 216 // 2.5625 1(a)(ii) 1 mark per bullet point 3 1 • − 3.75 = 100.01000 // – 4 + / 0.25 4 • 100.01000 becomes 1.0001000 Exponent = + 2 • Answer: Mantissa = 10001000 Exponent = 0010 1(b) Only the range is increased (no effect on precision) 1 1(c) 1 mark per bullet point to max 1 1 • There is no exact binary conversion for some numbers • More bits are needed to store the number than are available 1(d) First term: Overflow 2 Second term: Underflow

2 The following syntax diagrams for a programming language show the syntax of: • a condition • a variable • a number • a letter • a digit • an operator condition variable operator number variable variable letter number digit digit letter a b c digit operator 1 == 2 > 3 < 4 5 (a) The following conditions are invalid. Give the reason in each case. (i) 35 > 24 Reason .............................................................................................................................. ..................................................................................................................................... [1] (ii) abc := cba Reason .............................................................................................................................. ..................................................................................................................................... [1] (iii) bc < 49 Reason .............................................................................................................................. ..................................................................................................................................... [1] (b) Complete the Backus-Naur Form (BNF) for the syntax diagram. <operator> ::= ................................................................................................................... ................................................................................................................................................... <number> ::= ........................................................................................................................ ................................................................................................................................................... <variable> ::= ................................................................................................................... ................................................................................................................................................... <condition> ::= ................................................................................................................. ................................................................................................................................................... [6]

Mark scheme: 2(a)(i) 35 is not a variable 1 2(a)(ii) := is not an operator 1 2(a)(iii) 9 is not a digit 1 2(b) 1 mark for each bullet point 6 <operator>::= • == | > | < <number>::= • <digit><digit> <variable>::= • <letter> • |<letter><variable> <condition>::= • <variable><operator><number> • |<variable><operator><variable>

3 Protocols are essential for communication between computers. (a) Explain why protocols are essential for communication between computers. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) A protocol used in bus networks is CSMA/CD. Explain what is meant by CSMA/CD. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 3(a) 1 mark per bullet point to max 2 2 • Provide a set of standards for transmission of data • « that gives a known/accepted set of rules for transmitting and receiving data • This enables communication/compatibility between devices from different manufacturers/platforms etc. 3(b) 1 mark per bullet point to max 3 4 • Carrier Sense Multiple Access (with) Collision Detection • Before transmitting a device checks if the channel is busy • If it is busy the device waits // if channel free data is sent • When transmission begins the device listens for other devices also beginning transmission • If there is a collision, transmission is aborted / transmitting a jam signal • Both devices wait a (different) random time, then try again

4 A Boolean expression produces the following truth table. INPUT OUTPUT A B C X 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 (a) Write the Boolean expression for the truth table as a sum-of-products. X = ...................................................................................................................................... [2] (b) Complete the Karnaugh Map (K-map) for the truth table above. AB 00 01 11 10 0 C 1 [1] The K-map can be used to simplify the expression in part (a). (c) Draw loops around appropriate groups in the K-map in part (b) to produce an optimal sum-of- products. [2] (d) Write, using your answer to part (c), a simplified sum-of-products expression for the truth table. X = ...................................................................................................................................... [2]

Mark scheme: 4(a) 1 mark for 3 or 4 correct products 2 2 marks for all 5 correct products X = ABC. . + ABC. . + ABC. . + ABC. . + ABC. . 4(b) 1 mark for correct answer 1 AB 00 01 11 10 0 1 0 0 0 C 1 1 1 1 1 4(c) 1 mark per correct loop 2 AB 00 01 11 10 0 1 0 0 0 C 1 1 1 1 1 4(d) 1 mark per bullet point. 2 • A.B • +C X = AB. + C // X = C + A.B

5 (a) Explain why user-defined data types are necessary. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) An organisation stores data about its employees. • Employee ID is a five-digit number, for example, 01234. • Employee name is a string, for example, ‘Kiri Moana’. • Department is one of three values: Sales, Technical, Customer services. • Salary is an integer value in the range 25 000 to 150 000. (i) Complete the following pseudocode definition of a user-defined data type to store the employee data. TYPE Employee DECLARE EmployeeID : .................................................................................... DECLARE EmployeeName : STRING DECLARE Department : ( ................................................................................. ..................................................................................) DECLARE Salary : 25000..150000 ........................................................................................................................................... [4] (ii) Write a pseudocode statement to declare a variable, NewEmployee of data type Employee. ........................................................................................................................................... ..................................................................................................................................... [1] (iii) Write a pseudocode statement that assigns 02244 to the EmployeeID of NewEmployee. ........................................................................................................................................... ..................................................................................................................................... [1] (iv) Employee is an example of a record that is a composite data type. State two other composite data types. 1 ........................................................................................................................................ 2 ........................................................................................................................................ [2]

Mark scheme: 5(a) 1 mark per bullet point to max 2 2 • No suitable data type is provided by the language used • The programmer needs specify a new data type • « that meets the requirements of the application / program 5(b)(i) 1 mark per bullet point 4 • EmployeeID declared as STRING • Sales, Technical and CustomerServices « • … with commas in-between • ENDTYPE TYPE Employee DECLARE EmployeeID : STRING DECLARE EmployeeName : STRING DECLARE Department : (Sales, Technical, CustomerServices) DECLARE Salary : 25000..150000 ENDTYPE 5(b)(ii) DECLARE NewEmployee : Employee 1 5(b)(iii) NewEmployee.EmployeeID ← "02244" 1 5(b)(iv) 1 mark per bullet point to max 2 2 • Array • List • Set • Collection • Class • Stack • Queue • Linked list • Dictionary

6 (a) An operating system (OS) uses a memory management technique called paging. Explain what is meant by the following terms. Page ......................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Page frame ............................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Page table ................................................................................................................................ ................................................................................................................................................... ................................................................................................................................................... [3] (b) Explain why an operating system needs to use scheduling algorithms. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (c) State what is meant by an interrupt. ................................................................................................................................................... ............................................................................................................................................. [1] (d) For a computer system using multi-programming, the low-level scheduler decides which process will get next use of the processor. One algorithm could be a round-robin, which means every process gets use of the processor in sequence for a fixed amount of time (time-slice). For a round-robin algorithm, five processes are currently loaded and get the use of the processor in the sequence: JOB21 – JOBSS – JOBPT – JOB32 – JOB42, then return to JOB21 Process JOB32 has just completed its time-slice. The following paragraph describes what happens next. Complete the paragraph by inserting the missing processes. Interrupt received from the low-level scheduler. Save all register contents for ................................................ . Copy the saved registers for ................................................ to the CPU. The processor will now process ................................................ . [3]

Mark scheme: 6(a) 1 mark per bullet point 3 Page: • Virtual Memory is divided into blocks of a fixed size Page frame: • the main memory is divided into page frames of the same size as a page Page table: • the Page (Map) table shows the mapping of pages to page frames 6(b) 1 mark per bullet point to max 3 3 • To allow multiprogramming / multitasking to take place • To ensure fair usage of the processor • To ensure fair usage of peripherals • To ensure fair usage of memory • To ensure higher priority tasks are executed sooner • To ensure all processes have the opportunity to finish 6(c) A signal from a software source or hardware device seeking the attention 1 of the processer 6(d) 1 mark per bullet point in the order given 3 • JOB32 • JOB42 • JOB42

7 (a) Identify the four layers of the TCP/IP protocol suite. 1 ................................................................................................................................................ 2 ................................................................................................................................................ 3 ................................................................................................................................................ 4 ................................................................................................................................................ [4] (b) The TCP/IP protocol suite is responsible for transmitting data across the Internet using packet switching. (i) Explain why packet switching is used when sending data across the Internet. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2] (ii) Each packet requires a header. Describe the purpose of a packet header. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2] (iii) Identify three items that should be contained in a packet header. Item 1 ................................................................................................................................ ........................................................................................................................................... Item 2 ................................................................................................................................ ........................................................................................................................................... Item 3 ................................................................................................................................ ........................................................................................................................................... [3]

Mark scheme: 7(a) 1 mark per bullet point 4 • Application • Transport • Internet / Network • Data Link 7(b)(i) 1 mark per bullet point to max 2 2 • Packet switching makes best use of the available (channel) capacity • « by using alternative routes • « which is more secure / robust • « as packets to / from different sources and destinations can share the same route 7(b)(ii) 1 mark per bullet point to max 2 2 • To store data about packet • « and its routing // to ensure it reaches its destination • ... to ensure that message can be properly reconstructed 7(b)(ii) 1 mark per item to max 3 3 For example: • IP address of sender • IP address of destination • IP version • Number of packets the message consists of • ID number of that packet • Protocol used • Packet length • Time to live // max number of hops • Synchronisation data • Source port • Destination Port • Checksum

8 Digital certificates are used in internet communications. A Certificate Authority (CA) is responsible for issuing a digital certificate. (a) Identify two data items present in a digital certificate. 1 ................................................................................................................................................ 2 ................................................................................................................................................ [2] (b) The following paragraph describes how a digital signature is produced. Complete the paragraph by inserting an appropriate term in each space. A ................................................ algorithm is used to generate a message digest from the plain text message. The message digest is ................................................ with the sender’s ................................................ . [3]

Mark scheme: 8(a) 1 mark per bullet point to max 2 2 • Serial number • Identification of Certificate Authority (that issued the certificate) • Version (number) • Valid from // start date • Valid to // end date • Subject name (name of user/owner/computer/network device) • Subject's public key • Hashing algorithm • Algorithm used to create signature • Algorithm used to hash certificate • Hashed certificate 8(b) 1 mark for each correct term 3 A hashing algorithm is used to generate a message digest from the plain text message. The message digest is encrypted with the sender’s private key.

9 (a) The following incomplete table shows descriptions relating to computer architectures. Complete the table by inserting the appropriate terms. Description Term • There are several processors. A • Each processor executes different sets of instructions ......................................... on one set of data at the same time. • The processor has several ALUs. B • Each ALU executes the same set of instructions on ......................................... different sets of data at the same time. • There is only one processor. C • The processor executes one set of instructions on one ......................................... set of data. • There are several processors. D • Each processor executes a different set of instructions. ......................................... • Each processor operates on different sets of data. [4] (b) State three characteristics of massively parallel computers. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... 3 ................................................................................................................................................ ................................................................................................................................................... [3]

Mark scheme: 9(a) 1 mark for each correct term 4 Description Term • There are several processors. • Each processor executes different sets of MISD instructions on one set of data at the same time. • The processor has several ALUs. • Each ALU executes the same set of SIMD instructions on different sets of data at the same time. • There is only one processor. • The processor executes one set of instructions SISD on one set of data. • There are several processors. • Each processor executes a different set of instructions. MIMD • Each processor operates on different sets of data. 9(b) 1 mark per bullet point to max 3 3 • A large number of processors • Collaborative processing // coordinated simultaneous processing • Network infrastructure • Communicate using a message interface / by sending messages