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

1 Consider the following user‑defined data type. TYPE Book DECLARE ISBN : INTEGER DECLARE Author : STRING DECLARE Title : STRING DECLARE Supplier : (Amazone, Stones, Smiths, Blackwalls, Greens, Coals, Boarders) ENDTYPE (a) Name the data type of Book. ...............................................................................................................................................[1] (b) Name the non‑composite data type used in the Supplier declaration. ...............................................................................................................................................[1] (c) (i) Write a pseudocode statement to declare a variable, BestSeller, of type Book. .......................................................................................................................................[1] (ii) Write a pseudocode statement to assign “John Williams” to the author of BestSeller. .......................................................................................................................................[1]

Mark scheme: Question Answer Marks 1 (a) Record 1 (b) Enumerated 1 (c) DECLARE BestSeller : Book 1 (d) BestSeller.Author ← "John Williams" 1

2 (a) A computer system stores real numbers using floating‑point representation. The floating‑point numbers have: • eight bits for the mantissa • four bits for the exponent. The mantissa and exponent are both in two’s complement form. (i) Calculate the denary value of the following floating‑point number. Mantissa Exponent 0 0 1 1 1 0 0 0 0 1 1 1 Show your working. Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... Answer .............................................................................................................................. [3] (ii) State how you know the floating‑point number in part (a)(i) is not normalised. ........................................................................................................................................... .......................................................................................................................................[1] (iii) Normalise the floating‑point number in part (a)(i). Mantissa Exponent [2] (b) (i) Write the largest positive number that this system can represent as a normalised floating‑point number in this format. Mantissa Exponent [2] (ii) Write the smallest positive number that can be stored as a normalised floating‑point number in this format. Mantissa Exponent [2] (c) The number of bits available to represent a real number is increased to 16. State the effect this has on the numbers that can be represented, if the additional four bits are used in the: (i) mantissa ............................................................................................................................ .......................................................................................................................................[1] (ii) exponent ........................................................................................................................... .......................................................................................................................................[1] (d) A student enters the following code into an interpreter. X = 0.1 Y = 0.2 Z = 0.3 OUTPUT (X + Y + Z) The student is surprised to see the output: 0.6000000000000001 Explain why this is output. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ...............................................................................................................................................[3]

Mark scheme: 2(a)(i) 1 mark per bullet point: 3 • Correct value for exponent identified e.g. (0.0111 × 2^)7 • Used to give correct value e.g. 111 000 (1/4 + 1/8 +1/16) × 128, 0.4375 • Correct answer i.e. 56 2(a)(ii) The two most significant bits are 0 in the mantissa 1 // In mantissa, 2nd bit is not the inverse of 1st bit 2(a)(iii) 1 mark per bullet point: 2 • Mantissa = 01110000 • Exponent = 0110 2(b)(i) 1 mark per bullet point: 2 • Mantissa = 01111111 • Exponent = 0111 2(b)(ii) 1 mark per bullet point: 2 • Mantissa = 01000000 • Exponent = 1000 2(c)(i) Precision of numbers represented will increase 1 2(c)(ii) Range of numbers represented will increase 1 2(d) 1 mark per bullet point to max 3: 3 • 0.1/0.2/0.3 cannot be represented exactly in binary / rounding errors • adding two or more inaccurate representations together increases the probability of inaccuracy • giving an answer where the difference is significant enough to be seen

3 A local college has CSMA/CD in operation on its Local Area Network (LAN). (a) One function of CSMA/CD is to monitor traffic on the network. State two other tasks performed by CSMA/CD. 1 ................................................................................................................................................ 2 ................................................................................................................................................ [2] (b) The network uses the TCP/IP protocol to transfer files across the network. (i) State three functions of the TCP part of this protocol. 1 ........................................................................................................................................ ........................................................................................................................................... 2 ........................................................................................................................................ ........................................................................................................................................... 3 ........................................................................................................................................ ........................................................................................................................................... [3] (ii) State two functions of the IP part of this protocol. 1 ........................................................................................................................................ 2 ........................................................................................................................................ [2] (iii) Identify one other common protocol that could be used to transfer files across the college network. .......................................................................................................................................[1] (c) Protocols are essential for successful transmission of data over a network. The TCP/IP protocol suite operates on many layers. Give an appropriate protocol for each layer in the table. Layer Protocol Application Transport Internet [3] (d) The TCP/IP protocol is used to send an email message from one node on a LAN to a node on a different LAN. State the steps that take place when the email message is sent and received. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ...............................................................................................................................................[4]

Mark scheme: 3(a) 1 mark per bullet point to max 2: 2 • to only allow data to be sent when the line is idle • to detect a collision on the network • to halt transmissions when a collision occurs • calculates random wait time • allow retransmission after a random amount of time 3(b)(i) 1 mark per bullet point to max 3: 3 • allows applications to exchange data • establishes and maintains a connection « • « until exchange of data is complete • determines how to break application data into packets • adds sequence / packet number to (TCP) header • sends packets to and accepts packets from the network / Internet layer • manages flow control // manages congestion avoidance • acknowledges all packets that arrive • detects when a packet has not arrived at destination • handles retransmission of dropped packets • reassembles packets into the correct order 3(b)(ii) 1 mark per bullet point to max 2 2 • routes the packets around the network • adds to the IP header a source/destination address for each packet • encapsulates data into datagram • passes datagram to the network access layer (for transmission on the LAN)// passes datagram to the transport layer (on arrival at destination) • Defines the addressing method e.g. subnetting, NAT 3(b)(iii) HTTP(S) // FTP // POP3 // SMTP // UDP // etc... 1 3(c) 1 mark for appropriate protocol in each layer 3 Layer Protocol Application HTTP(S) // FTP // POP3 // SMTP // UDP etc... Transport TCP Internet IP 3(d) 1 mark per bullet point to max 4: 4 • Message is split into packets • Each packet is a fixed size • Each packet is given a header«. • «including destination IP address, sequence number etc. • Packets are forwarded from one LAN to the other LAN • Packets may take different routes • Missing packets are requested to be resent • Packets re-assembled into order at destination

4 (a) A Boolean expression corresponds to the following truth table. INPUT OUTPUT A B C X 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 (i) Write the Boolean expression for the truth table by applying the sum‑of‑products. X = .................................................................................................................................[2] (ii) Complete the Karnaugh Map (K‑map) for the truth table. AB 00 01 11 10 0 C 1 [1] (iii) The K‑map can be used to simplify the expression in part (a)(i). Draw loop(s) around appropriate groups of 1s in the table in part (a)(ii) to produce an optimal sum‑of‑products. [3] (iv) Write the simplified sum‑of‑products expression for your answer to part (a)(iii). X = .................................................................................................................................[3] (b) A logic circuit with four inputs produces the following truth table. INPUT OUTPUT A B C D X 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 (i) Complete the K‑map that corresponds to the truth table. AB CD [4] (ii) Draw loop(s) around appropriate groups of 1s in the table in part (b)(i) to produce an optimal sum‑of‑products. [2] (iii) Write the simplified sum‑of‑products expression for your answer to part (b)(ii). X = .................................................................................................................................[2]

Mark scheme: 4(a)(i) 1 mark for 2 or 3 correct, 2 marks for 4 correct 2 X = A.B.C + A.B.C + A.B.C + A.B.C 4(a)(ii) 1 mark for the correct K-map 1 AB 00 01 11 10 0 0 0 1 0 C 1 0 1 1 1 4(a)(iii) 1 mark for each loop max 3 3 AB 00 01 11 10 0 0 0 1 0 C 1 0 1 1 1 4(a)(iv) 1 mark for each pair. Allow follow through from (iii) 3 • A.B • + B.C • + A.C X = A.B + B.C + A.C 4(b)(i) 1 mark per bullet point max 2: 4 • Correct column headings and row headings – values only • Correct column headings and row headings – order 1 mark for 2 correct rows or columns, 2 marks for 4 correct rows or columns (based on headings) AB 00 01 11 10 00 0 1 1 0 01 0 0 1 0 CD 11 0 0 1 0 10 0 0 1 0 4(b)(ii) 1 mark per loop 2 AB 00 01 11 10 00 0 1 1 0 01 0 0 1 0 CD 11 0 0 1 0 10 0 0 1 0 4(b)(iii) 1 mark per bullet point: 2 • A.B • + B.C.D X = A.B + B.C.D

5 A computer process can be in one of three states: running, ready or blocked. (a) Explain how the processes are affected when the following events take place. (i) The running process needs to read a file from a disk. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[2] (ii) The running process uses up its time slice. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[2] (b) (i) State the conditions that are necessary for a process to move from the ready to the running state. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[2] (ii) State the conditions that are necessary for a process to move from the blocked to the ready state. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[2] (c) Give three reasons why process scheduling is needed. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... 3 ................................................................................................................................................ ................................................................................................................................................... [3]

Mark scheme: 5(a)(i) 1 mark per bullet point: 2 • Running process is halted • Process moves to blocked state 5(a)(ii) 1 mark per bullet point max 2: 2 • Running process is halted // another process has use of the processor • Process moves to ready state • « Until next time slice allocated 5(b)(i) 1 mark per bullet point: 2 • Current process no longer running // processor is available • Process was at the head of the ready queue / / process has highest priority 5(b)(ii) 1 mark per bullet point: 2 • The only • Required resource becomes available // event is complete 5(c) 1 mark per bullet point to max 3: 3 • to allow multiprogramming • to give each process a fair share of the CPU time • to allow all processes to complete in a reasonable amount of time • to allow highest priority jobs to be executed first • to keep the CPU busy all the time • to service the largest possible number of jobs in a given amount of time • to minimize the amount of time users must wait for their results • to maximise the use of peripherals

6 The compilation process has a number of stages. The first stage is lexical analysis. A compiler uses a keyword table and a symbol table. Part of the keyword table is shown. • Tokens for keywords are shown in hexadecimal. • All of the keyword tokens are in the range 00 – 5F. Keyword Token 01 * 02 = 03 IF 4A THEN 4B ENDIF 4C ELSE 4D FOR 4E STEP 4F TO 50 INPUT 51 OUTPUT 52 ENDFOR 53 Entries in the symbol table are allocated tokens. These values start from 60 (hexadecimal). Study the following code. Start 1 INPUT Number // Output values in a loop FOR Counter Start TO 12 OUTPUT Number * Counter ENDFOR (a) Complete the symbol table to show its contents after the lexical analysis stage. Token Symbol Value Type Start 60 Variable 1 61 Constant [3] (b) The output from the lexical analysis stage is stored in the following table. Each cell stores one byte of the output. Complete the output from the lexical analysis stage. Use the keyword table and your answer to part (a). 60 01 [2] (c) The output of the lexical analysis stage is the input to the syntax analysis stage. Identify two tasks in syntax analysis. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... [2] (d) The final stage of compilation is optimisation. (i) Code optimisation produces code that minimises the amount of memory used. Give one additional reason why code optimisation is performed. ........................................................................................................................................... .......................................................................................................................................[1] (ii) A student uses the compiler to compile some different code. After the syntax analysis stage is complete, the compiler generates object code. The following lines of code are compiled. X A + B Y A + B + C Z A + B + C + D The compilation produces the following assembly language code. LDD 236 // loads value A to accumulator ADD 237 // adds value B to accumulator STO 512 // stores accumulator in X LDD 236 // loads value A to accumulator ADD 237 // adds value B to accumulator ADD 238 // adds value C to accumulator STO 513 // stores accumulator in Y LDD 236 // loads value A to accumulator ADD 237 // adds value B to accumulator ADD 238 // adds value C to accumulator ADD 239 // adds value D to accumulator STO 514 // stores accumulator in Z Rewrite the assembly language code after it has been optimised. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[5]

Mark scheme: 6(a) 1 mark for each correct row 3 Token Symbol Value Type Start 60 Variable 1 61 Constant Number 62 Variable Counter 63 Variable 12 64 Constant 6(b) 1 mark for each circled section 2 60 01 61 51 62 4E 63 01 60 50 64 52 62 02 63 53 6(c) 1 mark per bullet point to max 2: 2 • constructing parse tree // parsing • checking the table of tokens to ensure that the rules/syntax/grammar of the language are/is obeyed • producing an error report 6(d)(i) shortens execution time of program// time taken to execute whole program 1 decreases 6(d)(ii) 1 mark for each of the following: 5 • LDD 236 ADD 237 STO 512 ADD 238 STO 513 ADD 239 STO 514 • Remove line 4 LDD 236 correct lines 3 and 6 in original code • Remove line 5 ADD 237 correct lines 3 and 6 in original code • Remove line 8 and 9 LDD 236 and ADD 237 correct lines 7 and 11 in original code • Remove line 10 ADD 238 correct lines 7 and 11 in original code