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

1 (a) A computer system uses floating-point representation to store real numbers. The floating-point numbers have: • 8 bits for the mantissa • 8 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. It is not in normalised form. Mantissa Exponent 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 Show your working. Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... Answer .............................................................................................................................. [3] (ii) Convert the denary number + 7.5 into a normalised floating-point number. Show your working. Mantissa Exponent Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... [3] (iii) Convert the denary number − 7.5 into a normalised floating-point number. Show your working. Mantissa Exponent Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... [3] (b) A normalised floating-point number is shown. Mantissa Exponent 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 (i) State the significance of this binary number. ........................................................................................................................................... .......................................................................................................................................[1] (ii) State what will happen if a positive number is added to this number. ........................................................................................................................................... .......................................................................................................................................[1]

Mark scheme: 1(a)(i) 1 mark per bullet point: • Correct value for exponent identified e.g. (0.010101 × 2^)5 • Used to give correct value e.g. 1010.1 or 21/64 x 32 • Correct answer i.e. 10.5 // 10½ 3 1(a)(ii) 1 mark per bullet point: • Correct binary value i.e. 111.1 • Value for exponent identified e.g. (0.1111 × 2^)3 • Correct answer i.e. 01111000 00000011 3 1(a)(iii) 1 mark per bullet point: • Any working method for conversion • Applied accurately • Correct answer i.e. 10001000 00000011 3 1(b)(i) Largest (positive) number (in this format) 1 1(b)(ii) Overflow // too large to represent // would become negative 1

2 (a) A network can be set up using a star topology. Give three features of a star topology. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... 3 ................................................................................................................................................ ................................................................................................................................................... [3] (b) (i) Describe what is meant by circuit switching. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[2] (ii) The table shows statements that relate to circuit switching, packet switching or both. Tick (✓) one or more boxes in each row to show whether the statement applies to circuit switching, packet switching or both. Statements Circuit switching Packet switching Shares bandwidth Data may arrive out of order Data can be corrupted Data are less likely to get lost [4]

Mark scheme: 2(a) 1 mark per bullet point to max 3: • Must have a central device • Each node is connected to the central device • Each node has a dedicated connection • Each connection must be bidirectional • Nodes may operate under different protocols 3 2(b)(i) 1 mark per bullet point to max 2: • dedicated circuit/channel/(physical) path • connection established before/at the start of the communication • which lasts for duration of connection // circuit released at end of the communication • all data is transmitted along the same route 2 Question Answer Marks 2(b)(ii) 1 mark for each row: Statements Circuit switching Packet switching Shares bandwidth 9 Data may arrive out of order 9 Data can be corrupted 9 9 Data are less likely to get lost either9 or9 4

3 (a) Consider the following Boolean expression. A . B . C + A . B . C + A . B . C Use Boolean algebra to simplify the expression. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ...............................................................................................................................................[4] (b) (i) Complete the truth table for the following logic circuit. A B C X Working space A B C X 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 [2] (ii) Complete the Karnaugh Map (K-map) for the truth table in part (b)(i). AB 00 01 11 10 0 C 1 [1] (iii) Draw loops around appropriate groups of 1s in the table in part (b)(ii) to produce an optimal sum-of-products. [2] (iv) Using your answer to part (b)(iii), write a simplified sum-of-products Boolean expression. X = .................................................................................................................................[2] (c) The truth table for a logic circuit with four inputs is shown. 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 for the truth table in part (c). AB CD [4] (ii) Draw loops around appropriate groups of 1s in the table in part (c)(i) to produce an optimal sum-of-products. [2] (iii) Using your answer to part (c)(ii), write a simplified sum-of-products Boolean expression. X = .................................................................................................................................[2]

Mark scheme: 3(a) 1 mark per bullet point to max 3: • Correct use of Idempotent law Y Y.Y Y Y Y = = + • Correct use of Complement law 0 Y. 1 Y Y Y = = + • Correct use of Distributive law ( ) X Y Z X.Y X.Z + = + • Correct use of Redundancy law X. Y X Y Y + = + • Correct use of identity law X.1 X = 1 mark for the correct answer For example: X A.B.C A.B.C A.B.C = + + Idempotent law X A.B.C A.B.C A.B.C A.B.C = + + + Distributive law ( ) ( ) X A.C. B B A.B. C C = + + + Complement/Inverse law X A.C A.B = + ( ) X A. C B = + Correct answer X A.B.C A.B.C A.B.C = + + Distributive law ( ) X A.C. B B A.B.C = + + Complement/Inverse law X A.C A.B.C = + ( ) X A. C B.C = + Redundancy Law X A.(C B) = + Correct answer 4 Question Answer Marks 3(b)(i) 1 mark for first four as 0, 1 mark for 1011 A B C X 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 2 3(b)(ii) 1 mark for correct K-map AB 00 01 11 10 C 0 0 0 1 1 1 0 0 1 0 1 1 mark 1 mark Question Answer Marks 3(b)(iii) 1 mark for each correct loop to max 2 AB 00 01 11 10 C 0 0 0 1 1 1 0 0 1 0 2 3(b)(iv) 1 mark per bullet point: • A.C • + A.B X A.C A.B = + 2 3(c)(i) 1 mark per bullet point to max 2: • 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 CD 00 0 1 1 0 01 0 0 1 0 11 0 0 1 0 10 0 0 1 0 4 Question Answer Marks 3(c)(ii) 1 mark for each correct loop to max 2: AB 00 01 11 10 CD 00 0 1 1 0 01 0 0 1 0 11 0 0 1 0 10 0 0 1 0 2 3(c)(iii) 1 mark per bullet point: • A.B • + B.C.D X A.B B.C.D = + 2

4 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. INPUT Number1 INPUT Number2 INPUT Answer IF Answer = Number1 + Number2 THEN OUTPUT 10 ELSE OUTPUT 0 ENDIF (a) Complete the symbol table to show its contents after the lexical analysis stage. Token Symbol Value Type Number1 60 Variable Number2 61 Variable [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. Use the keyword table and your answer to part (a). 51 60 [2] (c) A student uses the compiler to compile some different code. After the syntax analysis is complete, the compiler generates object code. The following line of code is compiled: X A + B + C − D The compilation produces the following assembly language code. LDD 236 // loads value A into accumulator ADD 237 // adds value B to accumulator ADD 238 // adds value C to accumulator STO 540 // stores accumulator in temporary location LDD 540 // loads value from temporary location into accumulator SUB 239 // subtracts value D from accumulator STO 235 // stores accumulator in X (i) Identify the final stage in the compilation process that follows this code generation stage. .......................................................................................................................................[1] (ii) Rewrite the equivalent code following the final stage. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... .......................................................................................................................................[3] (iii) State two benefits of the process that is carried out in the final stage. Benefit 1 ............................................................................................................................ ........................................................................................................................................... Benefit 2 ............................................................................................................................ ........................................................................................................................................... [2] (d) An interpreter is executing a program. The program uses the variables a, b, c and d. The program contains an expression that is written in infix form. The interpreter converts the infix expression to RPN. The RPN expression is: b a c + * d + 2 − The interpreter evaluates this RPN expression using a stack. The current values are: a = 1 b = 2 c = 2 d = 3 Show the changing contents of the stack as the interpreter evaluates the expression. The first entry on the stack has been done for you. 2 [4]

Mark scheme: 4(a) 1 mark per row Symbol Token Value Type Number1 60 Variable Number2 61 Variable Answer 62 Variable 10 63 Constant//Literal 0 64 Constant//Literal 3 4(b) 1 mark for each circled section 51 60 51 61 51 62 4A 62 03 60 02 61 4B 52 63 4D 52 64 4C 2 4(c)(i) (Code) Optimisation 1 4(c)(ii) 1 mark per bullet point: • LDD 236 ADD 237 ADD 238 SUB 239 Copy the instructions STO 235 • Remove line 4 STO 540 correct lines 3 and 6 in original code • Remove line 5 LDD 540 correct lines 3 and 6 in original code 3 Question Answer Marks 4(c)(iii) 1 mark per bullet point: • Code has fewer instructions/occupies less space in memory • shortens execution time of program // time taken to execute whole program decreases 2 4(d) 2 1 1 3 3 2 2 2 2 2 6 6 9 9 7 1 mark ← 1 mark → 1 mark 1 mark no operators on the stack anywhere 4

5 (a) Most desktop or laptop computers use CISC (Complex Instruction Set Computing) architecture. Most smartphones and tablets use RISC (Reduced Instruction Set Computing). State four features that are different for the CISC and RISC architectures. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... 3 ................................................................................................................................................ ................................................................................................................................................... 4 ................................................................................................................................................ ................................................................................................................................................... [4] (b) In a RISC processor, four instructions (A, B, C, D) are processed using pipelining. The following table shows five stages that take place when instructions are fetched and executed. In time interval 1, instruction A has been fetched. (i) In the table, write the instruction labels (A, B, C, D) in the correct time interval for each stage. Each operation only takes one time interval. Time interval Stage 1 2 3 4 5 6 7 8 9 Fetch instruction A Decode instruction Execute instruction Access operand in memory Write result to register [3] (ii) When completed, the table in part (b)(i) shows how pipelining allows instructions to be carried out more rapidly. Each time interval represents one clock cycle. Calculate how many clock cycles are saved by using pipelining in the example in part (b)(i). Show your working. Working ............................................................................................................................. ........................................................................................................................................... ........................................................................................................................................... Answer .............................................................................................................................. [3] (c) The table shows four statements about computer architecture. Put a tick (✓) in each row to identify the computer architecture associated with each statement. Architecture Statement SIMD MIMD SISD Each processor executes a different instruction There is only one processor Each processor executes the same instruction input using data available in the dedicated memory Each processor typically has its own partition within a shared memory [4]

Mark scheme: 5(a) 1 mark per bullet point to max 4: • RISC has fewer instructions // CISC has more instructions • RISC has many registers // CISC has few registers • RISCs instructions are simpler // CISC’s instructions are more complex • RISC has a few instruction formats // CISC has many instruction formats • RISC usually uses single-cycle instructions // CISC uses multi-cycle instructions • RISC uses fixed-length instructions // CISC uses variable-length instructions • RISC has better pipelineability // CISC has poorer pipelineability • RISC requires less complex circuits // CISC requires more complex circuits • RISC has fewer addressing modes // CISC has more addressing modes • RISC makes more use of RAM // CISC makes more use of cache/less use of RAM • RISC has a hard-wired control unit // CISC has a programmable control unit • RISC only uses load and store instructions to address memory // CISC has many types of instructions to address memory 4 5(b)(i) 1 mark per bullet point: • Completing the As correctly • B in column 2, row 1 no other Bs in row 1 • Remainder correctly completed Stage Time interval 1 2 3 4 5 6 7 8 9 Fetch instruction A B C D Decode instruction A B C D Execute instruction A B C D Access operand in memory A B C D Write result to register A B C D 3 Question Answer Marks 5(b)(ii) 1 mark per bullet point: • Correct number of cycles for pipelining 8 • Correct number of cycles without pipelining 4 × 5 = 20 • No of cycles saved 20 – 8 = 12 3 5(c) 1 mark for each row Statement Architecture SIMD MIMD SISD Each processor executes a different instruction 9 There is only one processor 9 Each processor executes the same instruction input using data available in the dedicated memory 9 Each processor typically has its own partition within a shared memory 9 4

6 (a) The following table shows descriptions and terms relating to data transmission security. Add appropriate descriptions and terms to complete the table. Description Term The result of encryption that is transmitted to the A recipient. ................................. The type of cryptography used where different keys are B used; one for encryption and one for decryption. ................................. ......................................................................................... ......................................................................................... C Digital certificate ......................................................................................... ......................................................................................... ......................................................................................... ......................................................................................... D Private key ......................................................................................... ......................................................................................... [4] (b) The sequence of steps 1 to 7 describes what happens when setting up a secure connection using Secure Socket Layer (SSL). Four statements are missing from the sequence. If the browser trusts the certificate, it creates, encrypts and sends the server a A symmetric session key using the server’s public key. B Server sends the browser an acknowledgement, encrypted with the session key. C Server sends a copy of its SSL Certificate and its public key. D Server decrypts the symmetric session key using its private key. Write one letter (A to D) in the appropriate space to complete the sequence. 1. Browser requests that the server identifies itself. 2. …………… 3. Browser checks the certificate against a list of trusted Certificate Authorities. 4. …………… 5. …………… 6. …………… 7. Server and browser now encrypt all transmitted data with the session key. [3]

Mark scheme: 6(a) 1 mark for each term/description Description Term A The result of encryption that is transmitted to the recipient Cipher text B The type of cryptography where different keys are used, one for encryption and one for decryption. Asymmetric or Public key C Electronic document used to prove the ownership of a public key // Electronic document used to prove that the data is from a trusted source Digital certificate D Key needed to decrypt data that has been encrypted by a public key // Key needed to encrypt data so that it that can be decrypted by a public key // the key used in asymmetric encryption which is not shared Private key 4 6(b) 1 mark for C in the correct place 1 mark for A followed by D in any position 1 mark for D followed by B in any position 1 Browser requests that the server identifies itself 2 C 3 Browser checks the certificate against a list of trusted Certificate Authorities 4 A 5 D 6 B 7 Server and Browser now encrypt all transmitted data with the session key 3