Cambridge A Level Computer Science 9608 — 2017 Oct/Nov Paper 4 · Variant 1

This document consists of 16 printed pages. DC (NH/JG) 129977/4 © UCLES 2017 [Turn over * 4 1 3 5 4 4 4 9 1 5 * COMPUTER SCIENCE 9608/41 Paper 4 Further Problem-solving and Programming Skills October/November 2017 2 hours 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. Cambridge International Examinations Cambridge International Advanced Subsidiary and Advanced Level

2 9608/41/O/N/17 © UCLES 2017 1 A greenhouse has a window that automatically opens and closes depending on the internal temperature. If the temperature rises above 20 °C, the window half opens. If the temperature rises above 30 °C, the window fully opens. If the temperature drops below 25 °C, the window returns to being half open. If the temperature drops below 15 °C, the window fully closes. The window has three possible states: Closed, Half Open and Fully Open. Current state Event Next state Closed Temperature rises above 20 °C Half Open Half Open Temperature drops below 15 °C Closed Half Open Temperature rises above 30 °C Fully Open Fully Open Temperature drops below 25 °C Half Open Complete the state-transition diagram for the window: … … … … … … … … … … … … … … [7]

3 9608/41/O/N/17 © UCLES 2017 [Turn over 2 (a) (i) State how repetition is shown in a Jackson Structured Programming (JSP) structure diagram. … …[1] (ii) State how selection is shown in a JSP structure diagram. … …[1] (b) A simple calculator is to be created. The calculator is to be used as follows: • User inputs 2 numbers (x and y). • User inputs an operator (+, –, * or /). • The calculator computes the answer. • The calculator displays the answer. Draw a JSP diagram for the calculator. The first element is provided. Calculator [5]

4 9608/41/O/N/17 © UCLES 2017 3 A declarative programming language is used to represent the following knowledge base: 01 person(jane). 02 person(ahmed). 03 person(caroline). 04 person(stuart). 05 food(chocolate). 06 food(sushi). 07 food(pizza). 08 food(chilli). 09 likes(jane, pizza). 10 likes(ahmed, chocolate). 11 likes(ahmed, pizza). 12 likes(jane, chilli). 13 likes(stuart, sushi). 14 dislikes(stuart, chocolate). 15 dislikes(jane, sushi). 16 dislikes(caroline, pizza). These clauses have the following meanings: Clause Explanation 01 Jane is a person 05 Chocolate is a food 09 Jane likes pizza 14 Stuart dislikes (does not like) chocolate (a) Mimi is a person who likes chocolate but does not like sushi or lettuce. Write additional clauses to represent this information. 17 … 18 … 19 … 20 … 21 … [5]

5 9608/41/O/N/17 © UCLES 2017 [Turn over (b) Using the variable PersonName, the goal: likes(PersonName, pizza). returns: PersonName = jane, ahmed . Write the result that is returned by the goal: likes(ahmed, FoodItem). FoodItem = … …[2] (c) B might like A, if B is a person, A is a food and B does not dislike A. Write this as a rule. might_like(… , …) IF … … …[6]

6 9608/41/O/N/17 © UCLES 2017 4 The following table shows part of the instruction set for a processor. The processor has one general purpose register, the Accumulator (ACC), and an Index Register (IX). Instruction Explanation Op code Operand LDM #n Immediate addressing. Load the number n to ACC. LDD <address> Direct addressing. Load the contents of the location at the given address to ACC. LDI <address> Indirect addressing. The address to be used is at the given address. Load the contents of this second address to ACC. LDX <address> Indexed addressing. Form the address from <address> + the contents of the index register. Copy the contents of this calculated address to ACC. LDR #n Immediate addressing. Load the number n to IX. STO <address> Store the contents of ACC at the given address. STX <address> Indexed addressing. Form the address from <address> + the contents of the index register. Copy the contents from ACC to this calculated address. ADD <address> Add the contents of the given address to the ACC. INC <register> Add 1 to the contents of the register (ACC or IX). DEC <register> Subtract 1 from the contents of the register (ACC or IX). JMP <address> Jump to the given address. CMP <address> Compare the contents of ACC with the contents of <address>. CMP #n Compare the contents of ACC with number n. JPE <address> Following a compare instruction, jump to <address> if the compare was True. JPN <address> Following a compare instruction, jump to <address> if the compare was False. LSL #n Bits in ACC are shifted n places to the left. Zeros are introduced on the right hand end. LSR #n Bits in ACC are shifted n places to the right. Zeros are introduced on the left hand end. IN Key in a character and store its ASCII value in ACC. OUT Output to the screen the character whose ASCII value is stored in ACC. END Return control to the operating system.

7 9608/41/O/N/17 © UCLES 2017 [Turn over (a) A program stores a letter. The user is allowed nine attempts to guess the stored letter. The program outputs “?” and the user guesses a letter. If the user guesses the letter, the program outputs “*”. The following is pseudocode for this program. REPEAT OUTPUT '?' INPUT GUESS IF GUESS = LETTERTOGUESS THEN OUTPUT '*' BREAK ELSE ATTEMPTS ATTEMPTS + 1 ENDIF UNTIL ATTEMPTS = 9 Write this program. Use the op codes from the instruction set provided. Label Op code Operand Comment START: LDM #63 // load ASCII value for '?' // OUTPUT '?' // input GUESS // compare with stored letter // if correct guess, go to GUESSED // increment ATTEMPTS // is ATTEMPTS = 9 ? // if out of guesses, go to ENDP // go back to beginning of loop GUESSED: LDM #42 // load ASCII for '*' // OUTPUT '*' ENDP: END // end program ATTEMPTS: 0 LETTERTOGUESS: 'a' [11]

8 9608/41/O/N/17 © UCLES 2017 (b) Five numbers are stored, starting in the location labelled NUMBERS. A program is needed to multiply each of the numbers by 4 and store them back in their original location. Write this program. Use the op codes from the instruction set on the opposite page. Label Op code Operand Comment START: // initialise the Index Register // load the value from NUMBERS // multiply by 4 // store the new value in NUMBERS // increment the Index Register // increment COUNT // is COUNT = 5 ? // repeat for next number ENDP: END COUNT: 0 NUMBERS: 22 13 5 46 12 [10]

9 9608/41/O/N/17 © UCLES 2017 [Turn over Instruction Explanation Op code Operand LDM #n Immediate addressing. Load the number n to ACC. LDD <address> Direct addressing. Load the contents of the location at the given address to ACC. LDI <address> Indirect addressing. The address to be used is at the given address. Load the contents of this second address to ACC. LDX <address> Indexed addressing. Form the address from <address> + the contents of the index register. Copy the contents of this calculated address to ACC. LDR #n Immediate addressing. Load the number n to IX. STO <address> Store the contents of ACC at the given address. STX <address> Indexed addressing. Form the address from <address> + the contents of the index register. Copy the contents from ACC to this calculated address. ADD <address> Add the contents of the given address to the ACC. INC <register> Add 1 to the contents of the register (ACC or IX). DEC <register> Subtract 1 from the contents of the register (ACC or IX). JMP <address> Jump to the given address. CMP <address> Compare the contents of ACC with the contents of <address>. CMP #n Compare the contents of ACC with number n. JPE <address> Following a compare instruction, jump to <address> if the compare was True. JPN <address> Following a compare instruction, jump to <address> if the compare was False. LSL #n Bits in ACC are shifted n places to the left. Zeros are introduced on the right hand end. LSR #n Bits in ACC are shifted n places to the right. Zeros are introduced on the left hand end. IN Key in a character and store its ASCII value in ACC. OUT Output to the screen the character whose ASCII value is stored in ACC. END Return control to the operating system.

10 9608/41/O/N/17 © UCLES 2017 5 Large development projects require careful resource management. (a) (i) Name an appropriate project management tool that helps the manager to work out the estimated length of time it takes for the project to complete. … …[1] (ii) Explain how, during the planning stage of the project, the manager would use the tool you named in part (a)(i). … … … … … …[3] (b) (i) Different programmers have been writing independent modules. The modules now need to be combined to create the final system. Name the type of testing required at this stage. … …[1] (ii) Name the final testing stage required before the system becomes operational. … …[1]

11 9608/41/O/N/17 © UCLES 2017 [Turn over 6 A programmer wants to create a computer simulation of animals searching for food in a desert. The desert is represented by a 40 by 40 grid. Each position in the grid is represented by a pair of coordinates. 'A' represents an animal and 'F' represents food. At the start of the simulation, the grid contains 5 animals and 1 food source. The following is an example of part of the grid. 0 1 2 3 4 ... 37 38 39 0 A .. 1 F .. 2 .. A 3 A .. ... .. .. .. .. .. .. .. .. .. 38 A .. A 39 .. A timer is used. In each time interval, each animal randomly moves 0 or 1 position in a random direction. The program generates this movement by computing two random numbers, each of which can be –1, 0 or 1. The program adds the first random number to the across number and the second random number to the down number representing the animal’s position. For example: • if 0 and 1 are generated, the across value does not change, the down value increases by 1 • if –1 and 1 are generated, the across value decreases by 1, and the down value increases by 1. Each animal has an individual score. If the animal moves to a position in the grid with food ('F'): • the animal’s score increases by 1 • the food disappears • one new animal ('A') is randomly generated and added to the grid (to a maximum of 20 animals) • one new food ('F') is randomly generated and added to the grid. The simulation is to be implemented using object-oriented programming. The programmer has designed two classes, Desert and Animal. The Desert class consists of: • attributes • Grid • StepCounter • AnimalList • NumberOfAnimals • methods • Constructor • IncrementStepCounter • GenerateFood • DisplayGrid Each attribute consists of a value and a get and set method that allow access to the attributes.

12 9608/41/O/N/17 © UCLES 2017 The following table describes the attributes and methods for the Animal class. Identifier Data type Description Constructor() Instantiate an object of the Animal class • Generate a pair of random numbers between 0 and 39. • Place animal at that random position. • Initialise the animal’s score to 0. EatFood() • Delete the food. • Increase the score of the animal that called the method. • Call the GenerateFood method of the Desert class. • Call the Constructor method of the Animal class. Move() • Call the GenerateChangeInCoordinate method for each coordinate (across or down number) of the animal’s position. • Moves the animal to the new space. • If there is food in the new position, call the EatFood method. Score INTEGER Initialised to 0 Across INTEGER The across value, between 0 and 39 Down INTEGER The down value, between 0 and 39

13 9608/41/O/N/17 © UCLES 2017 [Turn over (a) Write program code to declare the attributes and constructor for the Animal class. You only need to write the set and get methods for the attribute Across. You should also write: • the constructor for the class • set and get methods for the Across attribute only. Programming language … Program code … … … … … … … … … … … … … … … … … … … … … … … …[6]

14 9608/41/O/N/17 © UCLES 2017 (b) The Constructor method of the Desert class: • initialises an empty grid • creates 5 animal objects which are added to the AnimalList (an array of animal objects currently on the grid) • generates one food • sets the StepCounter to 0. Write program code for the Constructor method. Programming language … Program code … … … … … … … … … … … … … … … … …[5]

15 9608/41/O/N/17 © UCLES 2017 [Turn over (c) (i) The function GenerateChangeInCoordinate: • receives a coordinate (across or down number) as a parameter • checks whether the coordinate’s value is at a boundary of the grid • returns a random change (–1, 0 or 1) that will keep the animal’s position within the grid. Write program code for the GenerateChangeInCoordinate function. Programming language … Program code … … … … … … … … … … … … …[4]

16 9608/41/O/N/17 © UCLES 2017 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. (ii) The Move method uses the GenerateChangeInCoordinate function to calculate the new Across and Down values for an animal. If there is food in the new position in the grid, the animal eats the food. Write program code for the Move method. Programming language … Program code … … … … … … … … … … … … …[4] (d) The programmer plans to add a graphic display to the program. The programmer will make use of a program library. Explain what is meant by a program library. … … … …[2]

® IGCSE is a registered trademark. This document consists of 15 printed pages. © UCLES 2017 [Turn over Cambridge Assessment International Education Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/41 Paper 4 Written Paper October/November 2017 MARK SCHEME Maximum Mark: 75 Published 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 International will not enter into discussions about these mark schemes. Cambridge International is publishing the mark schemes for the October/November 2017 series for most Cambridge IGCSE®, Cambridge International A and AS Level components and some Cambridge O Level components.

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 2 of 15 Question Answer Marks 1 1 mark for each completed statement 7 Question Answer Marks 2(a)(i) • Asterisk (*) in the corner/top of the box(es) 1 2(a)(ii) • Circle (o) in the corner/top of box(es) 1 Window closed Window half open Temperature > 20° C Temperature < 15 °C Temperature > 30°C Temperature < 25° C

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 3 of 15 Question Answer Marks 2(b) 1 mark per bullet • Inputting 2 numbers, stored in x and y • Inputting sign Selection used for all four calculations • .. underneath an appropriate box at level 1 • Displaying the answer For example: 5 Calculator Input x y Input sign Calcula
on Display answer answer = x+y answer = x–y answer = x*y answer = x/y

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 4 of 15 Question Answer Marks 3(a) 1 mark per clause • person(mimi). • food(lettuce). • likes(mimi, chocolate). • dislikes(mimi, sushi). • dislikes(mimi, lettuce). 5 3(b) 1 mark per answer chocolate, pizza 2 3(c) 1 mark per bullet • might_like(B,A) • Person(B) • Food(A) • AND • AND NOT • Dislikes predicate For example: might_like(B, A). IF person(B) AND food(A) AND NOT(dislikes(B, A)). 6

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 5 of 15 Question Answer Marks 4(a) Label Op code Operand Comment Marks START: LDM #63 // load ASCII value for '?' OUT // OUTPUT '?' 1 IN // input GUESS 1 CMP LETTERTOGUESS // compare with stored letter 1 JPE GUESSED // if correct guess, go to GUESSED 1 LDD ATTEMPTS // increment ATTEMPTS 1 INC ACC 1 STO ATTEMPTS 1 CMP #9 // is ATTEMPTS = 9 ? 1 JPE ENDP // if out of guesses, go to ENDP 1 JMP START // go back to beginning of loop 1 GUESSED: LDM #42 // load ASCII for '*' OUT // OUTPUT '*' 1 ENDP: END // end program ATTEMPTS: 0 LETTERTOGUESS: 'a' 11

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 6 of 15 Question Answer Marks 4(b) Label Opcode Operand Comment Mark START: LDR #0 // initialise the Index Register 1 LOOP: LDX NUMBERS // load the value from NUMBERS 1 (LOOP) + 1(LDX NUMBERS) LSL #2 // multiply by 4 1 (LSL) + 1 (#2) STX NUMBERS // store the new value in NUMBERS 1 INC IX // increment the Index Register 1 LDD COUNT // increment COUNT 1 INC ACC STO COUNT CMP #5 // is COUNT = 5 ? 1 JPN LOOP // repeat for next number 1 ENDP: END COUNT: 0 NUMBERS: 22 13 5 46 12 10

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 7 of 15 Question Answer Marks 5(a)(i) PERT / GANTT 1 5(a)(ii) 1 mark per bullet to max 3 For example: • Calculate total minimum time required for project • Identify milestones • Task dependencies • Provides the critical path analysis • Identify which tasks need to be prioritised • Determine when to begin specific tasks/stages • Identify slack time • Identify when resources need allocating • Identify tasks that can be completed in parallel 3 5(b)(i) Integration 1 5(b)(ii) Beta / acceptance 1 Question Answer Marks 6(a) 1 mark per bullet to max 6 • Declaring a class with the name animal • Declaring variables for across, down and score (all Integers) • «as private/protected • Correct constructor header and ending • Randomly generating an across between 0–39 inc. in constructor • Randomly generating a down between 0–39 inc. in constructor • Initialising Score to zero in constructor • Correct get for Across • Correct set for Across 6

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 8 of 15 Question Answer Marks 6(a) Example: VB Class Animal Private Across As Integer Private Down As Integer Private Score As Integer Function GetAcross() Return Across End Function Sub SetAcross(Value As Integer) Across = Value End Sub Sub New() Randomize() Across = randomnumber.Next(0, 40) Down = randomnumber.Next(0, 40) Score = 0 End Sub End Class

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 9 of 15 Question Answer Marks 6(a) or Class Animal Private Across As Integer Property _Across As Integer Get Return _Across End Get Set(Value As Integer) Across = Value End Set End Property Private Down As Integer Private _Score As Integer Sub New() Randomize() Across = randomnumber.Next(0, 40) Down = randomnumber.Next(0, 40) _Score = 0 End Sub End Class Example: Python class Animal : def __init__ (self) : x = random.randint(0,39) y = random.randint(0,39) self.Across = x self.Down = y self.Score = 0 def SetAcross(A) : self.Across = A def GetAcross() : return self.Across

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 10 of 15 Question Answer Marks 6(a) Example: Pascal type Animal = class private Across: integer; Down: integer; score: integer; public constructor init; procedure SetAcross(AcrossV: integer); function GetAcross(): integer; end; constructor Animal.init(); SetAcross(random(40)); SetDown (random(40)); SetScore (0); end; procedure Animal.SetAcross(AcrossV: integer); begin Across := AcrossV; end; function Animal.GetAcross(): integer; begin GetAcross := Across; end;

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 11 of 15 Question Answer Marks 6(b) 1 mark per bullet to max 5 • constructor method heading and ending • Initialise all 40 by 40 elements of Grid as '' or equivalent • Loop 5 times« • «Creates a new instance of animal inside loop... • ...and adds it to array AnimalList • Call generate food and initialise StepCounter to 0 Example Python def __init__ (self) : self.grid = [[' ' for i in range(40)] for j in range(40)] self.AnimalList = [] self.StepCounter = 0 for i in range(5) : newAnimal = Animal () self.AnimalList.append(newAnimal) self.GenerateFood() Example VB Sub New() For x = 0 To 39 For y = 0 To 39 grid(x, y) = "" Next Next For z = 0 To 4 AnimalList(z) = New Animal Next Call GenerateFood() End Sub 5

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 12 of 15 Question Answer Marks 6(b) Example Pascal constructor Desert.init(); for x := 0 to 39 do begin for y := 0 to 39 do begin grid(x,y) = ""; end end for x := 0 to 4 do begin AnimalList(x) = object (Animal); end GenerateFood(); end; 6(c)(i) 1 mark per bullet: • Function header and ending taking one value as parameter • Check if coordinate = 0 (on lower bound) • «generate random number (0 or 1) • Check if coordinate = 39 (on upper bound) • «generate random number (–1 or 0) • Generate random number (e.g. –1, 0, 1) • Return the generated value max 4

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 13 of 15 Question Answer Marks 6(c)(i) Example VB Function GenerateDirection(ByRef coord As Integer) Dim lowerbound As Integer = -1 Dim upperbound As Integer = 1 If coord = 0 Then lowerbound = 0 ElseIf coord = 39 Then upperbound = 0 End If GenerateDirection = randomnumber.Next(lowerbound, upperbound) End Function Example Python def GenerateDirection(Coord) : lowerBound = -1 upperBound = 1 if Coord == 0 : lowerBound = 0 elif Coord == 39 : upperBound = 0 return random.randint(lowerBound, upperBound)

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 14 of 15 Question Answer Marks 6(c)(i) Example Pascal function GenerateDirection(coord : Integer): Integer; begin lowerbound = -1; upperbound = 1; if coord = 0 then lowerbound = 0; else if coord = 39 then upperbound = 0; GenerateDirection = random(39); end; 6(c)(ii) 1 mark per bullet to max 4 • Procedure move header, no parameters • Calling GenerateDirection twice sending across and down as separate parameters • Add return value to Across • Add return value to Down • Check if the grid, at the (new) coordinates == “F” • ..if true, Call EatFood Example python def Move(self) : self.Across += GenerateChangeInCoordinate(self.Across) self.Down += GenerateChangeInCoordinate(self.Down) if grid[self.Across][self.Down] == 'F' : self.EatFood() return 4

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 15 of 15 Question Answer Marks 6(c)(ii) Example VB Sub Move(ByRef thisAnimal As Animal) thisAnimal.across += GenerateChangeInCoordinate (thisAnimal.across) thisAnimal.down += GenerateChangeInCoordinate (thisAnimal.down) If thegrid._grid(thisAnimal.across, thisAnimal.down) = "F" Then Call EatFood() End If End Sub Example Pascal procedure Move(thisAnimal : Animal); begin thisAnimal.across = this.Animal.across + GenerateChangeInCoordinate (thisAnimal.across); thisAnimal.down = thisAnimal.down + GenerateChangeInCoordinate (thisAnimal.down); if (thisgrid.grid(thisAnimal.across, thisAnimal.down) = "F") then EatFood(); End; 6(d) 1 mark per bullet to max 3 • Pre-compiled • Collection of Code/modules/routines • Each module performs a specific purpose/task • Each module can be linked/imported into the program 2