Cambridge A Level Computer Science 9608 — 2018 May/June Paper 4 · Variant 3

* 0 5 9 4 8 9 4 3 1 2 * This document consists of 17 printed pages and 3 blank pages. DC (CE/SW) 147487/3 © UCLES 2018 [Turn over Cambridge International Examinations Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/43 Paper 4 Further Problem-solving and Programming Skills May/June 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.

2 9608/43/M/J/18 © UCLES 2018 1 A declarative language is used to represent facts and rules about flights. 01 direct(edinburgh, paris). 02 direct(palma, rome). 03 direct(glasgow, palma). 04 direct(glasgow, vienna). 05 direct(glasgow, salzburg). 06 07 flies(paris, fly_jet). 08 flies(mumbai, british_air). 09 flies(palma, ciebe). 10 flies(vienna, fly_jet). 11 flies(salzburg, ciebe). 12 13 can_fly(X, Y) IF direct(X, Z) AND direct(Z, Y). These clauses have the following meaning: Clause Explanation 01 There is a direct route from Edinburgh to Paris. 07 Fly Jet operates flights to Paris. 13 It is possible to fly from X to Y if there is a direct flight from X to Z and a direct flight from Z to Y. (a) More facts need to be included. There is a direct flight from London to Rome and British Air flies to Rome. 14 … 15 … [2] (b) Using the variable Q, the goal flies(Q, fly_jet). returns Q = paris, vienna Write the result returned by the goal flies(K, ciebe). K = …[2]

3 9608/43/M/J/18 © UCLES 2018 [Turn over (c) Use the variable M to write the goal to find where you can fly direct from Glasgow. …[2] (d) If an airline flies to an airport, that airline also flies every direct route out of that airport. Write a rule to represent this condition. flies(Y, X) IF … …[3] (e) State what the following goal returns. can_fly(glasgow, rome). …[1]

4 9608/43/M/J/18 © UCLES 2018 2 The array ItemList[1:20] stores data. A bubble sort sorts these data. (a) Complete the pseudocode algorithm for a bubble sort. 01 MaxIndex 20 02 NumberItems … 03 FOR Outer 1 TO … 04 FOR Inner 1 to NumberItems 05 IF ItemList[Inner] > … 06 THEN 07 Temp ItemList[ …] 08 ItemList[Inner] ItemList[ …] 09 ItemList[Inner + 1] … 10 ENDIF 11 ENDFOR 12 NumberItems … 13 ENDFOR [7] (b) The algorithm in part (a) is inefficient. (i) Explain why the algorithm in part (a) is inefficient. … … … …[2] (ii) Explain how you would improve the efficiency of this algorithm. … … … … …[3]

5 9608/43/M/J/18 © UCLES 2018 [Turn over (c) An insertion sort is another sorting algorithm. State two situations when an insertion sort is more efficient than a bubble sort. Give a reason for each. Situation 1 … … Reason … … … Situation 2 … … Reason … … … [4]

6 9608/43/M/J/18 © UCLES 2018 3 An internet based music streaming service provides access to an unlimited number of songs for members to play. The following pseudocode represents the operation of the service. CALL OpenAccount() CALL OperateAccount() CALL CloseAccount() PROCEDURE OperateAccount() WHILE RequestCloseAccount() = FALSE IF SubscriptionDue() = TRUE THEN CALL MakePayment() ELSE CALL PlaySong() ENDIF ENDWHILE ENDPROCEDURE (a) Complete the JSP structure diagram for this music service from the pseudocode given. Music Service [5]

7 9608/43/M/J/18 © UCLES 2018 [Turn over (b) The service needs extending so that members can download songs to play offline. • When a member selects a song, the service checks if the song has already been downloaded. • If the member has already downloaded the song, the member has the option to delete or play it. • If the member has not already downloaded the song they have the option to download or stream it. Complete the following JSP structure diagram to represent these new requirements. Select Song [4]

8 9608/43/M/J/18 © UCLES 2018 4 A software company is developing a new application. The project manager has created a work breakdown structure, as shown in the following table. Activity Days to complete Predecessor A Gather user requirements 6 B Design work 8 A C Develop server code 4 B D Develop application code 5 B E User interface development 6 B F Test server code 2 C G Test application 2 D,E H Test application/server integration 5 F,G I Roll out mobile application 3 H (a) Use the data in the table to complete the following Program Evaluation Review Technique (PERT) chart. 1 2 A 6 B 8 … … … … … … … … … … … … … … 3 5 6 7 9 4 8 [5] (b) Calculate the critical path (CP). State the: activities that form the CP … duration of the CP … [2] (c) For activity F, state the: earliest start time … latest finish time … [2]

9 9608/43/M/J/18 © UCLES 2018 [Turn over Question 5 begins on the next page.

10 9608/43/M/J/18 © UCLES 2018 5 A computer game is being developed using object-oriented programming. The following image is a screenshot from the game. There are scenery elements and animated elements. The player’s character is one of the animated elements. Each game element has the attributes: Attribute Description Example value PositionX The x coordinate of the game element. 92 PositionY The y coordinate of the game element. 106 Width The width of the game element. 150 Height The height of the game element. 200 ImageFilename The filename of the image file for the game element. GameElementFrame1.png Each game element has a method, GetDetails() that returns a string containing all the element’s attributes. The player’s character is one of a number of animated elements. All animated elements have the attributes: Attribute Description Example value AnimationFrames An array of GameElement Direction A string giving the direction the object is travelling in. "Left" Strength A value for the strength that indicates the power of the object. 2000 Health A value for the health that indicates the health of the object. 100 The player’s character can either move left or right, or jump.

11 9608/43/M/J/18 © UCLES 2018 [Turn over (a) Complete the following class diagram for the game. You do not need to include any additional get or set methods. GameElement AnimatedElement PositionX: INTEGER PositionY: INTEGER Width: INTEGER Height: INTEGER ImageFilename: STRING AnimationFrames: ARRAY OF GameElement … … … Constructor() GetDetails() Constructor() AdjustHealth() AdjustStrength() DisplayAnimation() Scenery Player CauseDamage: BOOLEAN DamagePoints: INTEGER Constructor() GiveDamagePoints() … … … … [3]

12 9608/43/M/J/18 © UCLES 2018 (b) Write program code to define the GameElement class. Programming language … Program code … … … … … … … … … … … … … … … … … … … … … … … … …[6]

13 9608/43/M/J/18 © UCLES 2018 [Turn over (c) The Scenery() class has two attributes, CauseDamage and DamagePoints. If the attribute CauseDamage is TRUE, then the scenery element can cause damage. The method GiveDamagePoints() checks whether the object can cause damage. If the object can cause damage, the method returns the integer value of the DamagePoints attribute. Write program code for the Scenery class. Programming language … Program code … … … … … … … … … … … … … … … … … … … … … …[6]

14 9608/43/M/J/18 © UCLES 2018 (d) A new scenery object, GiftBox, is to be created. (i) The attributes of GiftBox are as follows: Attribute Value PositionX 150 PositionY 150 Width 50 Height 75 ImageFilename "box.png" CauseDamage TRUE DamagePoints 50 Write program code to create an instance of GiftBox. Programming language … Program code … … … … … … …[3]

15 9608/43/M/J/18 © UCLES 2018 [Turn over (ii) An additional method, GetScenery(), returns all the attributes of the Scenery class. Write program code for the GetScenery() method. You should use the GetDetails() method that the Scenery class inherits from the GameElement class. Programming language … Program code … … … … … … … … … … … … … …[3]

16 9608/43/M/J/18 © UCLES 2018 6 An Abstract Data Type (ADT) is used to create a linked list. The linked list is created as an array of records. The records are of type ListNode. An example of a record of ListNode is shown in the following table. Data Field Value Player "Alvaro" Pointer 1 (a) (i) Use pseudocode to write a definition for the record type, ListNode. … … … … …[3] (ii) An array, Scorers, will hold 10 nodes of type ListNode. Use pseudocode to write an array declaration for this array. The lower bound subscript is 0. …[2] (b) The linked list stores ListNode records in alphabetical order of player. The last node in the linked list always has a Pointer value of –1. The position of the first node in the linked list is held in the variable ListHead. After some processing, the array and variables are in the state as follows: Scorers ListHead Player Pointer 0 0 "Alvaro" 1 1 "Antoine" 3 2 "Dimitri" 7 3 "Cristiano" 2 4 "Gareth" 5 5 "Graziano" 6 6 "Olivier" 8 7 "Erik" 4 8 "Yaya" 9 9 "Zoto" -1 A recursive function traverses the linked list to search for a player. An example of calling the function, using pseudocode, is: Position SearchList("Gareth", ListHead)

17 9608/43/M/J/18 © UCLES 2018 Complete the following pseudocode to implement the function SearchList(). The function will return a value of 99 when a player is not found. FUNCTION SearchList(Find : STRING, Position : INTEGER) RETURNS INTEGER IF Scorer[Position].Player = … THEN RETURN … ELSE IF Scorer[Position].Pointer <> –1 THEN Position SearchList(Find, …) RETURN … ELSE RETURN … ENDIF ENDIF ENDFUNCTION [5]

18 9608/43/M/J/18 © UCLES 2018 BLANK PAGE

19 9608/43/M/J/18 © UCLES 2018 BLANK PAGE

20 9608/43/M/J/18 © UCLES 2018 BLANK PAGE 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.

IGCSE™ is a registered trademark. This document consists of 19 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 May/June 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 May/June 2018 series for most Cambridge IGCSE™, Cambridge International A and AS Level and Cambridge Pre-U components, and some Cambridge O Level components.

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 2 of 19 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 May/June 2018 © UCLES 2018 Page 3 of 19 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 May/June 2018 © UCLES 2018 Page 4 of 19 Question Answer Marks 1(a) 1 mark per fact 14 direct(london, rome). 15 flies(rome, british_air). 2 1(b) 1 mark per bullet: • palma • salzburg K = palma, salzburg 2 1(c) 1 mark per bullet: • direct • glasgow, M direct(glasgow, M). 2 1(d) 1 mark per bullet: • flies(Z,X) • AND • direct(Z, Y) flies(Z, X) AND direct(Z, Y) 3 1(e) YES 1

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 5 of 19 Question Answer Marks 2(a) 1 mark for each completed statement 01 MaxIndex ← 20 02 NumberItems ← MaxIndex – 1 // 19 03 FOR Outer ← 1 TO MaxIndex – 1 // 19 04 FOR Inner ← 1 to NumberItems 05 IF ItemList[Inner] > ItemList[Inner + 1] 06 THEN 07 Temp ← ItemList[Inner] 08 ItemList[Inner] ← ItemList[Inner + 1] 09 ItemList[Inner + 1] ← Temp 10 ENDIF 11 ENDFOR 12 NumberItems ← NumberItems - 1 13 ENDFOR 7 2(b)(i) 1 mark per bullet • Iterations continue // it continues doing comparisons • «after the array is sorted 2 2(b)(ii) 1 mark per bullet to max 3 • Use of a flag to indicate if any swaps have taken place • If the inner loop has made all comparisons with no changes • «flag/value set accordingly • A comparison checks the flag/value at the end of each inner loop • «if it is sorted it breaks out/stops 3

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 6 of 19 Question Answer Marks 2(c) 1 mark per bullet to max 4 e.g. • When the list is almost sorted « • «because it will stop as soon as it is sorted • When there are a large number of data items « • «because it will perform fewer comparisons/loops 4

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 7 of 19 Question Answer Marks 3(a) 1 mark per bullet • OpenAccount, OperateAccount and Close Account on same level • RequestCloseAccount under OperateAccount • «SubscriptionDue under RequestCloseAcount • «Make Payment and PlaySong under SubscriptionDue • Correct selection and iteration throughout 5 *

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 8 of 19 Question Answer Marks 3(b) 1 mark per bullet • Downloaded? • Download and Not downloaded beneath downloaded • Delete song and play song beneath Downloaded (2) and Download song and stream song beneath not downloaded • All selections correct 4 Select Song Downloaded? Downloaded Delete Song Play Song Not Downloaded Download Song Stream Song

960 © U Q 08/43 CLES 2018 uestion 4(a) 1 ma • C • G • F • H • I 4(b) 1 ma • A • 3 4(c) 1 ma • E • L ark per bullet C, D and E all co G following D an F following C H from 6 to 7 from 7 to 8 ark per bullet AÆBÆEÆGÆH 30 days ark per bullet Earliest start tim Latest finish time Ca oming from 3 nd E HÆI e: 19 days e: 22 days ambridge International AS/A Lev PUBLISHED Page 9 of 19 Answer vel – Mark Scheme May/June 2 Mar 018 rks 5 2 2

960 © U Q 08/43 CLES 2018 uestion 5(a) 1 ma • A • P • I ark for each bulle AnimatedEleme Player methods nheritance arrow Ca et: nt attributes ws ambridge International AS/A Lev PUBLISHED Page 10 of 19 Answer vel – Mark Scheme May/June 2 Mar 018 rks 3

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 11 of 19 Question Answer Marks 5(b) 1 mark per bullet to max 6 • class declaration • private declaration of five attributes • constructor declaration • «initialisation of attributes to the parameter values • declaration of GetDetails function • appropriate concatenation of string using attributes • return of all 5 values in one string Python example code: class GameElement: def __init__(self, PositionX, PositionY, Width, Height, ImageFilename): self.__PositionX = PositionX self. __PositionY = PositionY self. __Width = Width self. __Height = Height self. __ImageFilename = String def GetDetails(self): Message = "Position_x:", self. __PositionX, "Position_y:", self. __PositionY, "width:", self. __Width, "height:", self. __Height, "ImageFilename", self. __ImageFilename) return Message 6

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 12 of 19 Question Answer Marks 5(b) Visual Basic example code: Class GameElement Private PositionX As Integer Private PositionY As Integer Private Width As Integer Private Height As Integer Private ImageFilename As String Public Sub New(ByVal X As Integer,ByVal Y As Integer, ByVal W As Integer, ByVal H As Integer, Filename As String ) PositionX = X PositionY = Y Width = W Height = H ImageFilename = Filename End Sub Public Function GetDetails() Dim Message As String Message = "PositionX: " + PositionX + "PositionY: " + PositionY + ", width: " + Width + ", height: " + Height + ", ImageFilename:" + ImageFilename Return Message End Function End Class

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 13 of 19 Question Answer Marks 5(b) Pascal example code: type GameElement = class private PositionX : Integer; PositionY : Integer; Width : Integer; Height : Integer; ImageFilename : String; public Constructor init(X, Y, W, H:Integer; Filename: String); Function GetDetails() : String; end; Constructor GameElement.init(X, Y, W, H:Integer; Filename: String); begin PositionX := X; PositionY := Y; Width := W; Height := H; ImageFilename := Filename; end; Function GameElement.GetDetails() : String; var Message:String; begin Message = "PositionX: " + PositionX + "PositionY: " + PositionY + ", width: " + Width + ", height: " + Height + ", ImageFilename:" + ImageFilename; Result = Message end;

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 14 of 19 Question Answer Marks 5(c) Max 4 from each section to max 6 overall 1 mark per bullet to max 4 • class declaration with inheritance • constructor declaration • «taking all 5 parameters and CauseDamage, DamagePoints parameters • «with inheritance constructor call • Declaring CauseDamage, DamagePoints private and assigning parameters 1 mark per bullet to max 4 • Function declaration for GiveDamagePoints « • «checking if CauseDamage = True • «returning DamagePoints if true • «else returning appropriate value e.g. -1/null/blank Python example code: class Scenery(GameElement): def __init__(self, PositionX, PositionY, Width, Height, ImageFilename, CauseDamage, DamagePoints): Object.__init__(self, PositionX, PositionY, Width, Height, ImageFilename) self.__CauseDamage = CauseDamage self.__DamagePoints = DamagePoints def GiveDamagePoints(self): if(self.__CauseDamage): return self.__DamagePoints else: return 0 6

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 15 of 19 Question Answer Marks 5(c) Visual Basic example code: Class Scenery Inherits GameElement Private CauseDamage As Boolean Private DamagePoints As Integer Public Sub New(ByVal X As Integer,ByVal Y As Integer, ByVal W As Integer, ByVal H As Integer,Filename As String, ByVal CD As Boolean, ByVal DP As Integer) MyBase.New(X, Y, W, H, Filename) CauseDamage = CD DamagePoints = DP End Sub Public Function GiveDamagePoints() As Integer If (CauseDamage) Then Return DamagePoints Else Return 0 End if End Function End Class

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 16 of 19 Question Answer Marks 5(c) Pascal example code: Scenery = class(GameElement) private CauseDamage : Boolean; DamagePoints: Integer; public Constructor init(X, Y, W, H: Integer; Filename: String; CD:Boolean; DP: Integer); override; Function GiveDamagePoints() : Integer; end; constructor Scenery.init(X, Y, W, H: Integer; Filename: String; CD: Boolean; DP: Integer); begin inherited init(X, Y, W, H, Filename); CauseDamage := CD; DamagePoints := DP; end; Function Scenery.GiveDamagePoints() : Integer; begin if (CauseDamage): Result := DamagePoints else: Result := 0; end;

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 17 of 19 Question Answer Marks 5(d)(i) 1 mark per bullet • Variable GiftBox assigned value • Call Scenery • With all 7 parameters assigned correctly Python example code: GiftBox = Scenery(150, 150, 50, 75, "box.png", True, 50) Visual Basic example code: GiftBox = Scenery(150, 150, 50, 75, "box.png", True, 50) Pascal example code: GiftBox := Scenery(150, 150, 50, 75, "box.png", True, 50) 3

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 18 of 19 Question Answer Marks 5(d)(ii) 1 mark per bullet • Function declaration with no parameters • Use inherited GetDetails method to get string • Return all values def GetScenery(self): Message = Object.GetDetails(self) Message = Message + " Causes Damage:", self.CauseDamage, “Damage Points:", self.DamagePoints return Message Visual Basic example code: Public Function GetScenery() As String Dim Message As String Message = MyBase.GetDetails() Message = Message + "CauseDamage: " + CauseDamage + " DamagePoints: " + DamagePoints Return Message End Function Pascal example code: Function Secenery.GetScenery(): String Var Message : String Begin Message := GetDetails(); Message := Message + "CauseDamage: " + CauseDamage + " DamagePoints: " + DamagePoints; Result:=Message; End; 3

9608/43 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2018 © UCLES 2018 Page 19 of 19 Question Answer Marks 6(a)(i) 1 mark per bullet: • TYPE ListNode declaration and ENDTYPE • DECLARE Player : String • DECLARE Pointer : INTEGER TYPE ListNode DECLARE Player : STRING DECLARE Pointer : INTEGER ENDTYPE 3 6(a)(ii) 1 mark per bullet: • DECLARE Scorers : ARRAY[0:9] • OF ListNode DECLARE Scorers : ARRAY[0:9] OF ListNode 2 6(b) 1 mark for each completed statement FUNCTION SearchList(Find, Position) RETURNS INTEGER IF Scorer[Position].Player = Find THEN RETURN Position ELSE IF Scorer[Position].Player <> -1 THEN Position ← SearchList(Find, Scorer[Position].Pointer) RETURN Position ELSE RETURN 99 ENDIF ENDIF ENDPROCEDURE 5