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

This document consists of 12 printed pages. DC (ST) 95543/3 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 5 7 4 7 7 4 1 4 5 9 * COMPUTER SCIENCE 9608/31 Paper 3 Advanced Theory October/November 2015 1 hour 30 minutes Candidates answer on the Question Paper. No Additional Materials are required. No calculators allowed. READ THESE INSTRUCTIONS FIRST Write your Centre number, candidate number and name in the spaces at the top of this page. Write in dark blue or black pen. You may use an HB pencil for any diagrams, graphs or rough working. Do not use staples, paper clips, glue or correction fluid. DO NOT WRITE IN ANY BARCODES. Answer all questions. No marks will be awarded for using brand names of software packages or hardware. At the end of the examination, fasten all your work securely together. The number of marks is given in brackets [ ] at the end of each question or part question. The maximum number of marks is 75.

2 9608/31/O/N/15 © UCLES 2015 1 In a particular computer system, real numbers are stored using floating-point representation with: • 8 bits for the mantissa, followed by • 8 bits for the exponent Two’s complement form is used for both mantissa and exponent. (a) (i) A real number is stored as the following two bytes: Mantissa Exponent 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 Calculate the denary value of this number. Show your working. … … … … … …[3] (ii) Explain why the floating-point number in part (a)(i) is not normalised. … …[2] (iii) Normalise the floating-point number in part (a)(i). Mantissa Exponent [2]

3 9608/31/O/N/15 © UCLES 2015 [Turn over (b) (i) Write the largest positive number that can be written as a normalised floating-point number in this format. Mantissa Exponent [2] (ii) Write the smallest positive number that can be written as a normalised floating-point number in this format. Mantissa Exponent [2] (iii) If a positive number is added to the number in part (b)(i) explain what will happen. … … … …[2] (c) A student writes a program to output numbers using the following code: X 0.0 FOR i 0 TO 1000 X X + 0.1 OUTPUT X ENDFOR The student is surprised to see that the program outputs the following sequence: 0.0 0.1 0.2 0.2999999 0.3999999 …… Explain why this output has occurred. … … … … … …[3]

4 9608/31/O/N/15 © UCLES 2015 2 A compiler uses a keyword table and a symbol table. Part of the keyword table is shown below. • Tokens for keywords are shown in hexadecimal. • All 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 piece of code: Counter 1.5 INPUT Num1 // Check values IF Counter = Num1 THEN Num1 Num1 + 5.0 ENDIF (a) Complete the symbol table below to show its contents after the lexical analysis stage. Symbol Token Value Type Counter 60 Variable 1.5 61 Constant [3]

5 9608/31/O/N/15 © UCLES 2015 [Turn over (b) Each cell below represents one byte of the output from the lexical analysis stage. Using the keyword table and your answer to part (a) complete the output from the lexical analysis. 60 01 [2] (c) This line of code is to be compiled: A B + C + D After the syntax analysis stage, the compiler generates object code. The equivalent code, in assembly language, is shown below: LDD 234 //loads value B ADD 235 //adds value C STO 567 //stores result in temporary location LDD 567 //loads value from temporary location ADD 236 //adds value D STO 233 //stores result in A (i) Name the final stage in the compilation process that follows this code generation stage. …[1] (ii) Rewrite the equivalent code given above to show the effect of it being processed through this final stage. … … … … … …[2] (iii) State two benefits of the compilation process performing this final stage. Benefit 1 … … Benefit 2 … …[2]

6 9608/31/O/N/15 © UCLES 2015 3 An email is sent from one email server to another using packet switching. (a) State two items that are contained in an email packet apart from the data. 1 … 2 …[2] (b) Explain the role of routers in sending an email from one email server to another. … … … … … …[3] (c) Sending an email message is an appropriate use of packet switching. Explain why this is the case. … … … … … …[2] (d) Packet switching is not always an appropriate solution. Name an alternative communication method of transferring data in a digital network. …[1]

7 9608/31/O/N/15 © UCLES 2015 [Turn over (e) Name an application for which the method identified in part (d) is an appropriate solution. Justify your choice. Application … Justification … … … … …[3]

8 9608/31/O/N/15 © UCLES 2015 4 (a) Three descriptions and two types of processor are shown below. Draw a line to connect each description to the appropriate type of processor. Description Type of processor Makes extensive use of general purpose registers RISC Many addressing modes are available CISC Has a simplified set of instructions [3] (b) In a RISC processor three instructions (A followed by B, followed by C) are processed using pipelining. The following table shows the five stages that occur when instructions are fetched and executed. (i) The ‘A’ in the table indicates that instruction A has been fetched in time interval 1. Complete the table to show the time interval in which each stage of each instruction (A, B, C) is carried out. 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) The completed table 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 the use of pipelining in the above example. Show your working. … … … … … …[3]

9 9608/31/O/N/15 © UCLES 2015 [Turn over 5 (a) (i) Complete the Boolean function that 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 0 1 1 0 1 1 1 1 1 X = A . B . C + …[3] The part to the right of the equals sign is known as the sum-of-products. (ii) For the truth table above complete the Karnaugh Map (K-map). AB 00 01 11 10 C 0 1 [1] The K-map can be used to simplify the function in part(a)(i). (iii) Draw loop(s) around appropriate groups of 1’s to produce an optimal sum-of-products. [2] (iv) Using your answer to part (a)(iii), write the simplified sum-of-products Boolean function. X = …[2]

10 9608/31/O/N/15 © UCLES 2015 (b) The truth table for a logic circuit with four inputs is given below: 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 1 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 0 1 1 1 0 1 1 1 1 1 1 (i) Complete the K-map corresponding to the truth table above. AB CD [4] (ii) Draw loop(s) around appropriate groups of 1’s to produce an optimal sum-of-products. [2] (iii) Using your answer to part (b)(ii), write the simplified sum-of-products Boolean function. X = …[2]

11 9608/31/O/N/15 © UCLES 2015 [Turn over 6 A number of processes are being executed in a computer. (a) Explain the difference between a program and a process. … … … …[2] A process can be in one of three states: running, ready or blocked. (b) For each of the following, the process is moved from the first state to the second state. Describe the conditions that cause each of the following changes of the state of a process: From running to ready … … … … From ready to running … … … … From running to blocked … … … …[6]

12 9608/31/O/N/15 © UCLES 2015 Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge International Examinations Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cie.org.uk after the live examination series. Cambridge International Examinations is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge. (c) Explain why a process cannot be moved from the blocked state to the running state. … … … … … …[3] (d) Explain the role of the high-level scheduler in a multiprogramming operating system. … … … …[2]

® IGCSE is the registered trademark of Cambridge International Examinations. CAMBRIDGE INTERNATIONAL EXAMINATIONS Cambridge International Advanced Level MARK SCHEME for the October/November 2015 series 9608 COMPUTER SCIENCE 9608/31 Paper 3 (Written Paper), maximum raw mark 75 This mark scheme is published as an aid to teachers and candidates, to indicate the requirements of the examination. It shows the basis on which Examiners were instructed to award marks. It does not indicate the details of the discussions that took place at an Examiners’ meeting before marking began, which would have considered the acceptability of alternative answers. Mark schemes should be read in conjunction with the question paper and the Principal Examiner Report for Teachers. Cambridge will not enter into discussions about these mark schemes. Cambridge is publishing the mark schemes for the October/November 2015 series for most Cambridge IGCSE®, Cambridge International A and AS Level components and some Cambridge O Level components.

Page 2 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 1 (a) (i) 00101000 00000011 =0.0101 × 2 ↑3 [1] =10.1 [1] =2.5 [1] (ii) For a positive number (mantissa starts with a zero) [1] bit after binary point (second bit from left) should be a one [1] (iii) 00101000 00000011 = 01010000 00000010 [1+1] (b) (i) 01111111 0111111 [1+1] (ii) 01000000 1000000 [1+1] (iii) number will become too large to represent [1] which will result in overflow [1] (c) Any point 1 mark 0.1 cannot be represented exactly in binary 0.1 represented here by a value just less than 0.1 the loop keeps adding this approximate value to counter until all accumulated small differences become significant enough to be seen [max 3] 2 (a) Symbol Token Value Type Counter 60 variable 1.5 61 constant Num1 62 variable [1] 5.0 63 constant [1+1] (b) 6 0 0 1 6 1 5 1 6 2 4 A 6 0 0 3 6 2 4 B 6 2 0 1 6 2 0 2 6 3 4 C [1+1]

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 (c) (i) Code optimisation [1] (ii) LDD 234 ADD 235 [1] ADD 236 STO 233 [1] 1 mark for first 2 lines, 1 mark for last 2 lines, with no other lines added (iii) Code has fewer instructions / occupies less space in memory when executed [1] minimises execution time of code // code will execute faster [1] 3 (a) Any point 1 mark sender’s IP address receiver’s IP address packet sequence number checksum [Max 2] (b) Any point 1 mark email has been split up into packets packet has destination address packets pass through many different routers in journey packets don’t take same route routers use IP addresses packets reassembled at destination to rebuild email [Max 3] (c) Any point 1 mark email message is only read when all of it is received time delays due to lost / delayed packets not significant so sending different packets by different routes is not issue / is efficient packets arriving out of order not an issue no requirement for a continuous circuit (circuit switching) [Max 2] (d) Circuit switching [1] (e) e.g. real-time video / video conferencing [1] Any point 1 mark circuit made available is dedicated to this communication stream full bandwidth available / no sharing no lost packets guaranteed quality of service [Max 2]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 4 (a) Description Type of processor Makes extensive use of general purpose registers RISC I mark for correct arrow from each description Many addressing modes are available CISC Has a simplified instruction set [3] (b) (i) Time Interval stage 1 2 3 4 5 6 7 8 9 Fetch instruction A B C Decode instruction A B C Execute instruction A B C Completing the As (1 Mark) Access operand in memory A B C B in column 2, Row 1 (1 Mark) Write result to register A B C Remainder completed (1 Mark) [3] (ii) With pipelining no of cycles = 7 [1] Without pipelining no of cycles = 3 * 5 = 15 [1] No of cycles saved = 8 [1]

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 5 (a) (i) A .B.C + [1] A.B. C [1] + A.B.C [1] (ii) AB 00 01 11 10 C 0 0 0 1 0 1 0 1 1 0 [1] (iii) AB 00 01 11 10 C 0 0 0 1 0 1 mark for each loop 1 0 1 1 0 Allow f.t. from (ii) [2] (iv) X = A.B [1] + B.C [1] Allow f.t. from (iii)

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 (b) (i) AB 00 01 11 10 1 mark row headings 1 mark column headings 1 mark per 2 correct rows (based on headings) CD 00 0 1 1 0 01 0 0 0 0 11 0 0 1 0 10 0 1 1 0 [4] (ii) AB 00 01 11 10 CD 00 0 1 1 0 1 mark for loop with two 1s 1 mark for looping the four 1s 01 0 0 0 0 11 0 0 1 0 10 0 1 1 0 [2] (iii) X = B.D [1] + A.B.C [1]

Page 7 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 31 © Cambridge International Examinations 2015 6 (a) A program is the written code (“static”) [1] A process is the executing code (“dynamic”) [1] (b) running, ready: when process is executing it is allocated a time slice (running state) // process is allocated time on processor [1] when time slice completed process / interrupt occurs can no longer use processor even though it is capable of further processing (ready state) [1] ready, running: process is capable of using processor (ready state) [1] OS allocates processor to process so that process can execute (running state) [1] running, blocked: process is executing (running state) when it needs to perform I / O operation [1] placed in blocked state – until I / O operation completed [1] (c) when I / O operation completed for process in blocked state [1] process put in ready state [1] OS decides which process to allocate to processor from the ready queue [1] (d) high-level scheduler: decides which processes are to be loaded from backing store [1] into memory / ready queue [1]