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

* 5 7 7 9 3 7 8 7 4 6 * This document consists of 16 printed pages. DC (LEG) 173052 © UCLES 2018 [Turn over COMPUTER SCIENCE 9608/43 Paper 4 Further Problem-solving and Programming Skills October/November 2018 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/43/O/N/18 © UCLES 2018 1 A declarative language is used to represent the following facts and rules about animals. 01 feature(dog, drinks_milk). 02 feature(dog, has_lungs). 03 feature(horse, has_lungs). 04 feature(tuna, lives_in_water). 05 feature(tuna, has_gills). 06 feature(crab, lives_in_water). 07 mammal(drinks_milk). 08 mammal(has_lungs). 09 fish(lives_in_water). 10 fish(has_gills). 11 is_a_mammal(X) IF (feature(X, Y) AND mammal(Y)) AND (feature(X, Z) AND mammal(Z)). These clauses are explained in the following table. Clause Explanation 01 A dog has the feature, drinks milk 07 A mammal drinks milk 11 X is a mammal, if: • X has the feature Y and a mammal has a feature Y, and • X has the feature Z and a mammal has the feature Z (a) More facts are to be included. (i) A bird has wings, and a bird lays eggs. Write the additional clauses to record these facts. 12 … 13 … [2] (ii) An eagle has all the features of a bird. Write the additional clauses to record this fact. 14 … 15 … [2]

3 9608/43/O/N/18 © UCLES 2018 [Turn over (b) (i) Using the variable B, the goal feature(B, drinks_milk) returns B = dog Write the result returned by the goal feature(B, lives_in_water) B = … [2] (ii) Write a goal, using the variable C, to find the feature(s) of tuna. … [2] (c) An animal is a bird if it lays eggs and it has wings. Complete the following rule. is_a_bird(X) IF … … [3] (d) Declarative programming and object-oriented programming are two examples of programming paradigms. (i) Define the term programming paradigm. … … [1] (ii) Give two examples of programming paradigms, other than declarative and object-oriented programming. 1 … 2 … [2]

4 9608/43/O/N/18 © UCLES 2018 2 Kendra collects books. She is writing a program to store and analyse information about her books. Her program stores information about each book as a record. The following table shows the information that will be stored about each book. Field name Description Title The title of the book Author The first listed author of the book ISBN A 13-digit code that uniquely identifies the book, for example: "0081107546738" Fiction If the book is fiction (TRUE) or non-fiction (FALSE) LastRead The date when Kendra last read the book (a) Write pseudocode to declare an Abstract Data Type (ADT) named Book, to store the information in the table. … … … … … … … … … [4]

5 9608/43/O/N/18 © UCLES 2018 [Turn over (b) The records are stored in a random access file. The function, Hash(), takes as a parameter the ISBN and returns the hash value. The disk address of the record in the hash table is calculated as: ISBN modulus 2000 plus 1. Write program code for the function Hash(). Programming language … Program code … … … … … … … … [4]

6 9608/43/O/N/18 © UCLES 2018 (c) The random access file, MyBooks.dat, stores the data about the books in the format: <Title> <Author> <ISBN> <Fiction> <LastRead> A procedure, FindBook(): • prompts the user to input the ISBN of a book until the ISBN contains 13 numeric digits • uses the function Hash() to calculate the disk address of the record • reads the record for that book from MyBooks.dat into a variable of type Book • outputs all the data about the book. Use pseudocode to write the procedure FindBook(). You can assume that the record exists at the disk address generated. … … … … … … … … … … … … … … … … … … …

7 9608/43/O/N/18 © UCLES 2018 [Turn over … … … … … … … … … … … … … … … …[8]

8 9608/43/O/N/18 © UCLES 2018 3 Joseph is taking a toy apart. Each time he removes an item from the toy, he writes the name of the item at the bottom of a paper list. When he rebuilds the toy, he puts the items back together working from the bottom of the list. Joseph writes a computer program to create the list using a stack, Parts. (a) Describe a stack structure. … … [1] (b) The stack is represented as an array in the program, the first element in the array is [0]. The current contents of the stack, Parts, and its pointer, StackPointer are shown. StackPointer 5 StackContents 0 "Screw 1" 1 "Screw 2" 2 "Back case" 3 "Screw 3" 4 "Engine outer" 5 6 7 (i) Describe the purpose of the variable StackPointer. … … [1]

9 9608/43/O/N/18 © UCLES 2018 [Turn over (ii) The procedure POP() removes an item from the stack. The procedure PUSH(<identifier>) adds an item to the stack. The current contents of the stack, Parts, and its pointer, StackPointer are shown. StackPointer 5 StackContents 0 "Screw 1" 1 "Screw 2" 2 "Back case" 3 "Screw 3" 4 "Engine outer" 5 6 7 Use the table below to show the contents of the stack, Parts, and its pointer after the following code is run. POP() POP() PUSH("Light 1") PUSH("Light 2") PUSH("Wheel 1") POP() POP() StackPointer StackContents 0 1 2 3 4 5 6 7 [2]

10 9608/43/O/N/18 © UCLES 2018 (c) A 1D array, Parts, is used to implement the stack. Parts is declared as: DECLARE Parts : ARRAY[0 : 19] OF STRING (i) The procedure POP outputs the last element that has been pushed onto the stack and replaces it with a '*'. Complete the pseudocode for the procedure POP. PROCEDURE POP IF ………………………………. = ………………………………. THEN OUTPUT "The stack is empty" ELSE StackPointer ………………………………………… OUTPUT ……………………………….………………………………. Parts[StackPointer] ………………………………. ENDIF ENDPROCEDURE [5] (ii) The procedure PUSH() puts the parameter onto the stack. Complete the pseudocode for the procedure PUSH(). PROCEDURE PUSH(BYVALUE Value : String) IF StackPointer > ……………………………….… THEN OUTPUT "Stack full" ELSE ……………………….………..……… …………….………………….….. StackPointer ………………………….….……………………………. ENDIF ENDPROCEDURE [4]

11 9608/43/O/N/18 © UCLES 2018 [Turn over 4 The recursive algorithm for the Calculate() function is defined as follows: 01 FUNCTION Calculate(BYVALUE Number : INTEGER) RETURNS INTEGER 02 IF Number = 0 03 THEN 04 Calculate −10 05 ELSE 06 Calculate Number * Calculate(Number − 1) 07 ENDIF 08 ENDFUNCTION (a) (i) State what is meant by a recursive algorithm. … … [1] (ii) State the line number in Calculate() where the recursive call takes place. … [1] Question 4(b) begins on the next page.

12 9608/43/O/N/18 © UCLES 2018 (b) The function is called with Calculate(3). Dry run the function and complete the trace table below. State the final value returned. Show your working. 01 FUNCTION Calculate(BYVALUE Number : INTEGER) RETURNS INTEGER 02 IF Number = 0 03 THEN 04 Calculate −10 05 ELSE 06 Calculate Number * Calculate(Number − 1) 07 ENDIF 08 ENDFUNCTION Working … … … … Trace table: Call number Function call Number = 0 ? Return value Final return value … [6]

13 9608/43/O/N/18 © UCLES 2018 [Turn over (c) A recursive algorithm within a subroutine can be replaced with an iterative algorithm. (i) Describe one problem that can occur when running a subroutine that has a recursive algorithm. … … … … [2] (ii) Rewrite the Calculate() function in pseudocode, using an iterative algorithm. … … … … … … … … … … … … … … [5]

14 9608/43/O/N/18 © UCLES 2018 5 A game uses a set of cards. Each card has a number (between 0 and 9 inclusive) and a shape ("square", "triangle" or "circle"). The game is written using object-oriented programming. The class, Cards, has the private properties: • Number • Shape and the methods: • Constructor() • GetNumber() • GetShape() The purpose of each method in the class Cards is given in the following table. Method Purpose Constructor() Takes a number and a shape as parameters Checks that the number and the shape are valid and: • either assigns the parameters to Number and Shape • or reports an error. GetNumber() A public method that returns the number for that card. GetShape() A public method that returns the shape for that card. (a) Explain why the properties are private. … … … … … [2]

15 9608/43/O/N/18 © UCLES 2018 [Turn over (b) Write program code for the Constructor() method. Programming language … Program code … … … … … … … … … … … [5] (c) Write program code for the GetNumber() method. Programming language … Program code … … … … … [2] (d) A card, OneS, has the value 1 for Number and the value "square" for Shape. Write program code to instantiate an instance of Cards for OneS. Programming language … Program code … … … [2]

16 9608/43/O/N/18 © UCLES 2018 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. (e) The game has a function, Compare() that takes two cards as parameters and compares them. If the cards are identical, the function outputs "SNAP" and returns −1. If they are not identical, and the card numbers are different, it returns the Number of the card with the higher value or the Number for the cards if they are the same. Write program code for the Compare() function. Programming language … Program code … … … … … … … … … … … … … … … … … … [6]

This document consists of 18 printed pages. © UCLES 2018 [Turn over Cambridge Assessment International Education Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/43 Paper 4 Written Paper October/November 2018 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 2018 series for most Cambridge IGCSE™, Cambridge International A and AS Level components and some Cambridge O Level components.

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 2 of 18 Generic Marking Principles These general marking principles must be applied by all examiners when marking candidate answers. They should be applied alongside the specific content of the mark scheme or generic level descriptors for a question. Each question paper and mark scheme will also comply with these marking principles. GENERIC MARKING PRINCIPLE 1: Marks must be awarded in line with: • the specific content of the mark scheme or the generic level descriptors for the question • the specific skills defined in the mark scheme or in the generic level descriptors for the question • the standard of response required by a candidate as exemplified by the standardisation scripts. GENERIC MARKING PRINCIPLE 2: Marks awarded are always whole marks (not half marks, or other fractions). GENERIC MARKING PRINCIPLE 3: Marks must be awarded positively: • marks are awarded for correct/valid answers, as defined in the mark scheme. However, credit is given for valid answers which go beyond the scope of the syllabus and mark scheme, referring to your Team Leader as appropriate • marks are awarded when candidates clearly demonstrate what they know and can do • marks are not deducted for errors • marks are not deducted for omissions • answers should only be judged on the quality of spelling, punctuation and grammar when these features are specifically assessed by the question as indicated by the mark scheme. The meaning, however, should be unambiguous. GENERIC MARKING PRINCIPLE 4: Rules must be applied consistently e.g. in situations where candidates have not followed instructions or in the application of generic level descriptors.

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 3 of 18 GENERIC MARKING PRINCIPLE 5: Marks should be awarded using the full range of marks defined in the mark scheme for the question (however; the use of the full mark range may be limited according to the quality of the candidate responses seen). GENERIC MARKING PRINCIPLE 6: Marks awarded are based solely on the requirements as defined in the mark scheme. Marks should not be awarded with grade thresholds or grade descriptors in mind.

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 4 of 18 Question Answer Marks 1(a)(i) 1 mark for each correct statement: • bird(lays_egg). • bird(has_wings). 2 1(a)(ii) 1 mark for each correct line: • feature(eagle, lays_eggs). • feature(eagle, has_wings). 2 1(b)(i) 1 mark for each animal: tuna, crab 2 1(b)(ii) 1 mark per bullet point: • feature() • tuna, C feature(tuna, C) 2 1(c) 1 mark per bullet point to max 3: • feature(X,Y) AND bird(Y) // feature(X, has_wings) • AND • feature(X,Z) AND bird(Z) // feature(X, lays_eggs) (feature(X, Y) AND bird(Y)) AND (feature(X, Z) AND bird(Z)) 3 1(d)(i) A programming style/classification // characteristics/features that programming language has/uses 1 1(d)(ii) 1 mark for each: • Low-level • Imperative // Procedural 2

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 5 of 18 Question Answer Marks 2(a) 1 mark per bullet point to max 4: • declaration of type Book • Title, Author and ISBN as String • Fiction as Boolean • LastRead as Date For example: TYPE Book DECLARE Title : String DECLARE Author : String DECLARE ISBN : String DECLARE Fiction : Boolean DECLARE LastRead : Date ENDTYPE 4

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 6 of 18 Question Answer Marks 2(b) 1 mark per bullet point to max 4: • Function header • « taking ISBN as parameter • Converting ISBN to integer • Calculating Hash (ISBN mod 2000 + 1) • Returning the calculated Hash Examples: Python: def Hash(ISBN): ISBNint = int(ISBN) Hash = (ISBNint % 2000) + 1 VB.NET: Function Hash (ISBN As String) As Integer ISBNint = convert.toInt32(ISBN) Hash = (ISBNint MOD 2000) + 1 End Function Pascal: function Hash(ISBN : String) : Integer begin ISBNint = StrToInt(ISBN) Hash = (ISBNint MOD 2000) + 1 end; 4

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 7 of 18 Question Answer Marks 2(c) 1 mark per bullet point to max 8: • Procedure FindBook declaration and prompt and input ISBN • Validate data input has 13 characters • « and are all numeric • ..loop until valid • Call Hash() with input data and store return data • Open MyBooks.dat for reading as random file and close • Finding the record using return value Hash() • Get the data for the record • «store in variable of type Book • «output all the data for the record 8

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 8 of 18 Question Answer Marks 2(c) Example: PROCEDURE FindBook() DECLARE BookInfo : Book REPEAT ISBN ← input("Enter the ISBN number") Valid ← TRUE Size ← LENGTH(ISBN) IF size <> 13 THEN Valid ← FALSE ELSE FOR i ← 1 to 13 IF NOT( MID(ISBN,i,1) >= '0' AND MID(ISBN,i,1)<= '9' ) THEN Valid ← FALSE ENDIF ENDFOR ENDIF UNTIL Valid Filename ← "myBooks.dat" OPENFILE Filename FOR RANDOM RecordLocation ← Hash(ISBN) SEEK FileName, RecordLocation GETRECORD Filename, BookInfo CLOSEFILE Filename OUTPUT (BookInfo.Title & " " & BookInfo.Author & " " & BookInfo.ISBN & " " & BookInfo.Fiction & " " & BookInfo.LastRead) ENDPROCEDURE

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 9 of 18 Question Answer Marks 3(a) • LIFO / last in first out 1 3(b)(i) Points to the next free space on the stack 1 3(b)(ii) 1 mark per bullet to max 3 • Correct stack contents • StackPointer = 4 StackPointer 4 StackContents 0 "Screw 1" 1 "Screw 2" 2 "Back case" 3 "Light 1" 4 5 6 7 2

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 10 of 18 Question Answer Marks 3(c)(i) 1 mark for each correct statement: PROCEDURE POP IF StackPointer = 0 THEN OUTPUT ("The stack is empty") ELSE StackPointer ← StackPointer - 1 OUTPUT Parts[StackPointer] Parts(StackPointer) ← "*" ENDIF ENDPROCEDURE 5 3(c)(ii) 1 mark for each completed statement: PROCEDURE PUSH (BYVALUE Value : String) IF StackPointer > 19 THEN OUTPUT "Stack full" ELSE Parts[StackPointer] ← Value StackPointer ← StackPointer + 1 ENDIF ENDPROCEDURE 4

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 11 of 18 Question Answer Marks 4(a)(i) A function/subroutine defined in terms of itself // a function/subroutine that calls itself 1 4(a)(ii) 06 1 4(b) 1 mark for each bullet point: • –60 as final return value • 3*2*1*–10 1 mark for each row in table Call Number Function call Number = 0 ? Return value 1 Calculate(3) False 3*Calculate(2) 2 Calculate(2) False 2*Calculate(1) 3 Calculate(1) False 1*Calculate(0) 4 Calculate(0) TRUE –10 6 4(c)(i) 1 mark per bullet point: • Each time it calls itself the variables are put onto the stack // The function call itself too many times • « it runs out of stack space // stack overflow 2

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 12 of 18 Question Answer Marks 4(c)(ii) 1 mark per bullet point to max 5: • Function header with parameter and Returning calculated value • Loop parameter times (up to number, or down from number)« • «Multiplying by loop counter • Multiplying by –10 • Dealing with starting value correctly For example: FUNCTION Calculate(Number : INTEGER) RETURNS INTEGER DECLARE Count : INTEGER DECLARE Value : INTEGER Value ← −10 FOR Count ← 1 to Number Value ← Value * Count ENDFOR RETURN Value ENDFUNCTION 5 Question Answer Marks 5(a) 1 mark per bullet point to max 2: • To restrict direct access to the property to the class // keep the properties secure // So the data can only be accessed by its methods // makes the program more robust • To make the program easier to debug • To ensure data going in is valid // to stop invalid changes // stop accidental changes 2

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 13 of 18 Question Answer Marks 5(b) 1 mark per bullet point: • Constructor method header taking 2 parameters (with correct data types if given) • Checking if Number > = 0 and < = 9 • Checking theShape is ‘square’ or ‘triangle’ or ‘circle’ • « if both valid assigning Number and Shape the parameters • « if either invalid report error (output/returning value/catching error) 5

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 14 of 18 Question Answer Marks 5(b) Examples: Python def __init__(self, Num, theShape): if (Num >= 0 and Num <= 9) and (theShape = "square" or theShape = "triangle" or theShape = "circle”) : self. __Number = Num self.__Shape = TheShape else print("Error") endif VB.NET Public Sub New(Num As Integer, theShape As String) IF (Num >= 0 and Num <= 9) and (theShape = "square" or theShape = "triangle" or theShape = "circle") THEN Number = Num Shape = theShape ELSE Console.WriteLine("Error") ENDIF End Sub Pascal constructor Cards.Create(Num : Integer, theShape : String); begin If (Num >= 0 and Num <= 9) and (theShape = "square" or theShape = "triangle" or theShape = "circle") Number := Num; Shape := theShape; Else Writeln("Error") ; end;

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 15 of 18 Question Answer Marks 5(c) 1 mark per bullet point to max 2: • Function declaration for GetNumber • Returning Number Examples: Python def GetNumber(): return(self.__Number) VB.NET Public Function GetNumber() As Integer Return(Number) End Function Pascal function Cards.GetNumber() : Integer; begin GetNumber := Number; end; 2

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 16 of 18 Question Answer Marks 5(d) 1 mark per bullet point to max 2: • Assigning to OneS and correct instantiation • Correct parameter values Examples: Python OneS = Cards(1, "square") VB.NET Dim OneS As New Cards(1, "square") or Dim OneS As Cards = New Cards(1, "square") or OneS = New Cards(1, "square") Pascal var OneS : Cards; OneS := Cards.Create(1, "square") 2 5(e) 1 mark per bullet point: • function declaration (returning integer) and taking 2 cards as parameter • comparison of Number and Shape « • « if the same output ‘SNAP’ and return –1 • Compare Number of each to find highest and return the highest number • return either number if the same • correct use of .GetNumber() and .GetShape()throughout 6

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 17 of 18 Question Answer Marks 5(e) Examples: Python def Compare(P1Card, P2Card): if P1Card.GetNumber() = P2Card.GetNumber() AND P1Card.GetShape() = P2Card.GetShape(): Print("SNAP") return -1 elif P2Card.GetNumber() > P1Card.GetNumber(): return P2Card.GetNumber() else: return P1Card.GetNumber() VB.NET Function Compare(P1Card As Cards, P2Card As Cards) As Integer IF P1Card.GetNumber() = P2Card.GetNumber()AND P1Card.GetShape() = P2Card.GetShape()THEN Console.writeline("SNAP") Return -1 ELSEIF P2Card.GetNumber() > P1Card.GetNumber() THEN P2Card.GetNumber() ELSE Return P1Card.GetNumber() ENDIF End Function

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2018 © UCLES 2018 Page 18 of 18 Question Answer Marks 5(e) Pascal function Compare(P1Card : Cards, P2Card : Cards) : Integer; begin if P1Card.GetNumber() = P2Card.GetNumber()AND P1Card.GetShape() = P2Card.GetShape() then writeline("SNAP"); return −1; else if P2Card.GetNumber() > P1Card.GetNumber() then return P2Card.GetNumber(); else return P1Card.GetNumber(); end;