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

This document consists of 11 printed pages and 1 blank page. DC (ST) 95544/3 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 6 5 5 0 0 8 5 9 6 3 * COMPUTER SCIENCE 9608/32 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/32/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 • 4 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 12-bit binary pattern: 0 1 1 0 1 0 0 0 0 0 1 1 Calculate the denary value of this number. Show your working. … … … … … …[3] (ii) Give the normalised binary pattern for +3.5. Show your working. … … … … … …[3] (iii) Give the normalised binary pattern for –3.5. Show your working. … … … … … …[3]

3 9608/32/O/N/15 © UCLES 2015 [Turn over The number of bits available to represent a real number is increased to 16. (b) (i) If the system were to use the extra 4 bits for the mantissa, state what the effect would be on the numbers that can be represented. … …[1] (ii) If the system were to use the extra 4 bits for the exponent instead, state what the effect would be on the numbers that can be represented. … …[1] (c) A student enters the following expression into an interpreter: OUTPUT (0.1 + 0.2) The student is surprised to see the following output: 0.3000000000000001 Explain why this output has occurred. … … … … … …[3]

4 9608/32/O/N/15 © UCLES 2015 2 In this question, you are shown pseudocode in place of a real high-level language. 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 to 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: Start 0.1 // Output values in loop FOR Counter Start TO 10 OUTPUT Counter + Start ENDFOR (a) Complete the symbol table below to show its contents after the lexical analysis stage. Symbol Token Value Type Start 60 Variable 0.1 61 Constant [3]

5 9608/32/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) The compilation process has a number of stages. The output of the lexical analysis stage forms the input to the next stage. (i) Name this stage. …[1] (ii) State two tasks that occur at this stage. … … … …[2] (d) The final stage of compilation is optimisation. There are a number of reasons for performing optimisation. One reason is to produce code that minimises the amount of memory used. (i) State another reason for the optimisation of code. …[1] (ii) What could a compiler do to optimise the following expression? A B + 2 * 6 … … …[1]

6 9608/32/O/N/15 © UCLES 2015 (iii) These lines of code are to be compiled: X A + B Y A + B + C Following the syntax analysis stage, object code is generated. The equivalent code, in assembly language, is shown below: LDD 436 //loads value A ADD 437 //adds value B STO 612 //stores result in X LDD 436 //loads value A ADD 437 //adds value B ADD 438 //adds value C STO 613 //stores result in Y (iv) Rewrite the equivalent code, given above, following optimisation. … … … … … …[3]

7 9608/32/O/N/15 © UCLES 2015 [Turn over 3 (a) Explain what is meant by circuit switching. … … … …[2] (b) There are many applications in which digital data are transferred across a network. Video conferencing is one of these. For this application, circuit switching is preferable to the use of packet switching. Explain why this is so. … … … … … … … … … … … … …[6] (c) A web page is transferred from a web server to a home computer using the Internet. Explain how the web page is transferred using packet switching. … … … … … …[3]

8 9608/32/O/N/15 © UCLES 2015 4 (a) Four descriptions and four types of computer architecture are shown below. Draw a line to connect each description to the appropriate type of computer architecture. Description Computer architecture A computer that does not have the ability for parallel processing. SIMD The processor has several ALUs. Each ALU executes the same instruction but on different data. MISD There are several processors. Each processor executes different instructions drawn from a common pool. Each processor operates on different data drawn from a common pool. SISD There is only one processor executing one set of instructions on a single set of data. MIMD [4] (b) In a massively parallel computer explain what is meant by: (i) Massive … … …[1] (ii) Parallel … … …[1] (c) There are both hardware and software issues that have to be considered for parallel processing to succeed. Describe one hardware and one software issue. Hardware … … … … Software … … … …[4]

9 9608/32/O/N/15 © UCLES 2015 [Turn over 5 (a) (i) Complete the Boolean function that corresponds to the following truth table. INPUT OUTPUT P Q R Z 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Z = P . Q . R + …[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). PQ 00 01 11 10 R 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. Z = …[1]

10 9608/32/O/N/15 © UCLES 2015 (b) The truth table for a logic circuit with four inputs is given below: INPUT OUTPUT P Q R S Z 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 (i) Complete the K-map corresponding to the truth table above. PQ RS [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. Z = …[2]

11 9608/32/O/N/15 © UCLES 2015 6 A number of processes are being executed in a computer. A process can be in one of three states: running, ready or blocked. (a) 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 state of a process: From blocked to ready … … … … From running to ready … … … …[4] (b) Explain why a process cannot move directly from the ready state to the blocked state. … … … … … …[3] (c) A process in the running state can change its state to something which is neither the ready state nor the blocked state. (i) Name this state. …[1] (ii) Identify when a process would enter this state. …[1] (d) Explain the role of the low-level scheduler in a multiprogramming operating system. … … … …[2]

12 9608/32/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. BLANK PAGE

® 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/32 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 32 © Cambridge International Examinations 2015 1 (a) (i) 01101000 0011 = 0.1101 (or 1/2 + 1/4 + 1/16) × 2
3 [1+1] = 110.1 = 6.5 [1] (ii) +3.5 = 11.1 [1] = 0.111 × 2
2 (or indication of moving binary point correctly) [1] = 01110000 0010 [1] (iii) 01110000 Allow f.t. from (ii) 10001111 One’s complement on mantissa [1] 10001111 +1 Two’s complement [1] = 10010000 0010 [1] (b) (i) Precision/accuracy of numbers represented will increase [1] (ii) Range of numbers represented will increase [1] (c) Any point, 1 mark (max. 3) 0.1/0.2 cannot be represented exactly in binary // rounding error [1] 0.1 represented by a value just greater than 0.1 // 0.2 represented by a value just greater than 0.2 [1] adding two representations together adds the two differences [1] summed difference significant enough to be seen [1] [max. 3] [Total: 14] 2 (a) [1] [1+1] Symbol Token Value Type Start 60 Variable 0.1 61 Constant Counter 62 Variable 10 63 Constant

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 32 © Cambridge International Examinations 2015 (b) 60 01 61 4E 62 01 60 50 63 52 62 02 60 53 [1+1] (c) (i) syntax analysis [1] (ii) any two points from: construct parse tree // parsing checking syntax/grammar produce error report [max. 2] (d) (i) Minimise the execution time // code runs faster [1] (ii) Compiler could calculate 2*6 and replace it with the value 12. [1] (iii) LDD 436 } ADD 437 } [1] STO 612 } ADD 438 [1] STO 613 [1] –1 for each additional instruction; 0 for copy of original code [Total: 13] 3 (a) dedicated circuit/channel/physical path [1] which lasts for duration of connection [1] (b) e.g. cs: gives dedicated circuit [1] ps: split into packets/chunks [1] ps: sends packets on individual routes [1] cs: whole bandwidth available // ps: shares bandwidth [1] cs: faster data transfer [1] cs: packets arrive in order they are sent [1] cs: packets cannot get lost [1] cs: better for a real-time application [1] ps: packets may arrive out of order so delay until packet order restored [1] ps: packets may get lost so retransmission causes delays [1] [max. 6] (c) web page divided into packets/chunks [1] each packet has destination address [1] router looks at IP address… [1] and decides where to send packet next for most efficient path [1] packets can take different routes [1] home computer reassembles packets to rebuild web page [1] [max. 3]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 32 © Cambridge International Examinations 2015 [Total: 11] 4 (a) 1 mark for correct arrow from each description Description Computer Architecture A computer that does not have the ability for parallel processing SIMD The processor has several ALUs. Each ALU executes the same instruction but on different data. MISD There are several processors. Each processor executes different instructions drawn from a common pool. Each processor operates on different data drawn from a common pool. SISD There is only one processor executing one set of instructions on a single set of data. MIMD [4] (b) (i) Massive: many/large number of processors // hundreds/thousands of processors [1] (ii) Parallel: to perform a set of coordinated computations in parallel/simultaneously [1] (c) processors need to be able to communicate … [1] so that processed data can be transferred from one processor to another [1] suitable algorithm/program/software/design // appropriate programming language [1] which allows data to be processed by multiple processors simultaneously [1] [Total: 10]

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 32 © Cambridge International Examinations 2015 5 (a) (i) + R . Q P. = Z [1] + .R Q . P [1] P.Q.R [1] (ii) PQ 00 01 11 10 R 0 0 0 0 1 1 0 0 1 1 [1] (iii) 1 mark each loop PQ 00 01 11 10 R 0 0 0 0 1 1 0 0 1 1 Allow f.t. from (ii) [2] (iv) = Z Q . P [1] P.R + [1] Allow f.t. from (iii) (b) (i) 1 mark row headings. 1 mark column headings. 1 mark per 2 correct rows (based on headings) PQ 00 01 11 10 RS 00 0 0 0 0 01 0 1 1 1 11 0 1 1 0 10 0 0 0 0 [4]

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 32 © Cambridge International Examinations 2015 (ii) 1 mark for loop with two 1s; 1 mark for loop with four 1s PQ 00 01 11 10 RS 00 0 0 0 0 01 0 1 1 1 11 0 1 1 0 10 0 0 0 0 Allow f.t. from (i –1 for each incorrect grouping, max. 2 errors [2] (iii) = Z Q.S [1] S P.R. + [1] Allow f.t. from (ii). –1 error if more than 2 terms [Total: 16] 6 (a) blocked
ready: process is waiting for resource/ I/O operation to complete (blocked state) [1] when I/O operation completed process goes into ready queue (ready state) [1] 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/interrupt occurs process can no longer use processor even though it is capable of further processing (ready state) [1] (b) to be in blocked state process must initiate some I/O operation [1] to initiate operation process must be executing [1] if process in ready state cannot be executing/must be in running state [1] (c) (i) exit/termination/completion [1] (ii) when the process has finished execution [1] (d) low-level scheduler: decides which of the processes in ready state [1] should get use of processor/be put in running state [1] based on position/priority [1] invoked after interrupt/OS call [1] [max. 2] [Total: 11]