Cambridge A Level Computer Science 9608 — 2019 May/June Paper 4 · Variant 1

This document consists of 18 printed pages and 2 blank pages. DC (PQ) 180360 © UCLES 2019 [Turn over Cambridge Assessment International Education Cambridge International Advanced Subsidiary and Advanced Level * 4 6 5 8 9 5 0 5 8 1 * COMPUTER SCIENCE 9608/41 Paper 4 Further Problem-solving and Programming Skills May/June 2019 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/41/M/J/19 © UCLES 2019 1 (a) A stack contains the values 'red', 'blue', 'green' and 'yellow'. yellow green blue red (i) Show the contents of the stack in part(a) after the following operations. POP() PUSH('purple') PUSH('orange') [1] Top of stack

3 9608/41/M/J/19 © UCLES 2019 [Turn over (ii) Show the contents of the stack from part(a)(i) after these further operations. POP() POP() PUSH('brown') POP() PUSH('black') [1] (b) A queue is an alternative Abstract Data Type (ADT). Describe a queue. … … … … … … [3]

4 9608/41/M/J/19 © UCLES 2019 2 A computer games club wants to run a competition. The club needs a system to store the scores achieved in the competition. A selection of score data is as follows: 99, 125, 121, 97, 109, 95, 135, 149 (a) A linked list of nodes will be used to store the data. Each node consists of the data, a left pointer and a right pointer. The linked list will be organised as a binary tree. (i) Complete the binary tree to show how the score data above will be organised. RootPointer RightPointer 99 LeftPointer 97 125 121 ∅ The symbol ∅ represents a null pointer. [5]

5 9608/41/M/J/19 © UCLES 2019 [Turn over (ii) The following diagram shows a 2D array that stores the nodes of the binary tree’s linked list. Add the correct pointer values to complete the diagram, using your answer from part (a)(i). RootPointer 0 FreePointer Index LeftPointer Data RightPointer 0 99 1 125 2 121 3 97 4 109 5 95 6 135 7 149 8 [6]

6 9608/41/M/J/19 © UCLES 2019 (b) The club also considers storing the data in the order in which it receives the scores as a linked list in a 1D array of records. The following pseudocode algorithm searches for an element in the linked list. Complete the six missing sections in the algorithm. FUNCTION FindElement(Item : INTEGER) RETURNS ………………………………………… …………………………………………… ← RootPointer WHILE CurrentPointer …………………………………………… NullPointer IF List[CurrentPointer].Data <> …………………………………………… THEN CurrentPointer ← List[……………………………………………].Pointer ELSE RETURN CurrentPointer ENDIF ENDWHILE CurrentPointer ← NullPointer ………………………………………… CurrentPointer ENDFUNCTION [6]

7 9608/41/M/J/19 © UCLES 2019 [Turn over (c) The games club is looking at two programming paradigms: imperative and object-oriented programming paradigms. Describe what is meant by the imperative programming paradigm and the object-oriented programming paradigm. (i) Imperative … … … … … … [3] (ii) Object-oriented … … … … … … [3]

8 9608/41/M/J/19 © UCLES 2019 (d) Players complete one game to place them into a category for the competition. The games club wants to implement a program to place players into the correct category. The programmer has decided to use object-oriented programming (OOP). The highest score that can be achieved in the game is 150. Any score less than 50 will not qualify for the competition. Players will be placed in a category based on their score. The following diagram shows the design for the class Player. This includes the properties and methods. Player Score : INTEGER // initialised to 0 Category : STRING // "Beginner", "Intermediate", // "Advanced" or "Not Qualified", initialised // to "Not Qualified" PlayerID : STRING // initialised with the parameter InputPlayerID Create() // method to create and initialise an object using // language-appropriate constructor SetScore() // checks that the Score parameter has a valid value // if so, assigns it to Score SetCategory() // sets Category based on player’s Score SetPlayerID() // allows a player to change their PlayerID // validates the new PlayerID GetScore() // returns Score GetCategory() // returns Category GetPlayerID() // returns PlayerID

9 9608/41/M/J/19 © UCLES 2019 [Turn over (i) The constructor receives the parameter InputPlayerID to create the PlayerID. Other properties are initialised as instructed in the class diagram. Write program code for the Create() constructor method. Programming language … Program code … … … … … … … … … … [5]

10 9608/41/M/J/19 © UCLES 2019 (ii) Write program code for the following three get methods. Programming language … GetScore() Program code … … … … GetCategory() Program code … … … … GetPlayerID() Program code … … … … [4]

11 9608/41/M/J/19 © UCLES 2019 [Turn over (iii) The method SetPlayerID()asks the user to input the new player ID and reads in this value. It checks that the length of the PlayerID is less than or equal to 15 characters and greater than or equal to 4 characters. If the input is valid, it sets this as the PlayerID, otherwise it loops until the player inputs a valid PlayerID. Use suitable input and output messages. Write program code for SetPlayerID(). Programming language … Program code … … … … … … … … … … … … [4]

12 9608/41/M/J/19 © UCLES 2019 (iv) The method SetScore()checks that its INTEGER parameter ScoreInput is valid. If it is valid, it is then set as Score. A valid ScoreInput is greater than or equal to 0 and less than or equal to 150. If the ScoreInput is valid, the method sets Score and returns TRUE. If the ScoreInput is not valid, the method does not set Score, displays an error message, and it returns FALSE. Write program code for SetScore(ScoreInput : INTEGER). Programming language … Program code … … … … … … … … … … … … … … … [5]

13 9608/41/M/J/19 © UCLES 2019 [Turn over (v) Write program code for the method SetCategory(). Use the properties and methods in the original class definition. Players will be placed in one of the following categories. Category Criteria Advanced Score is greater than 120 Intermediate Score is greater than 80 and less than or equal to 120 Beginner Score is greater than or equal to 50 and less than or equal to 80 Not Qualified Score is less than 50 Programming language … Program code … … … … … … … … … … … … … … … [4]

14 9608/41/M/J/19 © UCLES 2019 (vi) Joanne has played the first game to place her in a category for the competition. The procedure CreatePlayer()performs the following tasks. • allows the player ID and score to be input with suitable prompts • creates an instance of Player with the identifier JoannePlayer • sets the score for the object • sets the category for the object • outputs the category for the object Write program code for the CreatePlayer()procedure. Programming language … Program code … … … … … … … … … … … … … … … [8]

15 9608/41/M/J/19 © UCLES 2019 [Turn over (e) The programmer wants to test that the correct category is set for a player’s score. As stated in part (d)(v), players will be placed in one of the following categories. Category Criteria Advanced Score is greater than 120 Intermediate Score is greater than 80 and less than or equal to 120 Beginner Score is greater than or equal to 50 and less than or equal to 80 Not Qualified Score is less than 50 Complete the table to provide test data for each category. Category Type of test data Example test data Beginner Normal Abnormal Boundary Intermediate Normal Abnormal Boundary Advanced Normal Abnormal Boundary [3]

16 9608/41/M/J/19 © UCLES 2019 (f) In part (b), the club stored scores in a 1D array. This allows the club to sort the scores. The following is a sorting algorithm in pseudocode. NumberOfScores ← 5 FOR Item ← 1 TO NumberOfScores – 1 InsertScore ← ArrayData[Item] Index ← Item – 1 WHILE (ArrayData[Index] > InsertScore) AND (Index >= 0) ArrayData[Index + 1] ← ArrayData[Index] Index ← Index – 1 ENDWHILE ArrayData[Index + 1] ← InsertScore ENDFOR (i) Give the name of this algorithm. … [1] (ii) State the name of one other sorting algorithm. … [1]

17 9608/41/M/J/19 © UCLES 2019 [Turn over (iii) Complete a dry run of the algorithm using the following trace table. Item NumberOfScores InsertScore Index ArrayData 0 1 2 3 4 99 125 121 109 115 [7]

18 9608/41/M/J/19 © UCLES 2019 3 Some algorithms can be written using recursion. (a) State two features of recursion. Feature 1 … Feature 2 … [2] (b) Explain what a compiler has to do to implement recursion. … … … … … … [3]

19 9608/41/M/J/19 © UCLES 2019 BLANK PAGE

20 9608/41/M/J/19 © UCLES 2019 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 Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series. Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge. BLANK PAGE

This document consists of 13 printed pages. © UCLES 2019 [Turn over Cambridge Assessment International Education Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/41 Paper 4 Written Paper May/June 2019 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 2019 series for most Cambridge IGCSE™, Cambridge International A and AS Level and Cambridge Pre-U components, and some Cambridge O Level components.

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 2 of 13 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. 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/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 3 of 13 Question Answer Marks 1(a)(i) 1 mark for correct stack orange purple green blue red 1 1(a)(ii) 1 mark for correct stack black green blue red 1 1(b) 1 mark per bullet point to max 3 • (Linear) data structure • First in First out // FIFO // An item is added to the end of the queue and an item is removed from the front • All items are kept in the order they are entered • It has a head pointer and a tail pointer • Can be static or dynamic • A queue can be circular « • «when the (tail) pointer reaches the last position it returns to the first 3

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 4 of 13 Question Answer Marks 2(a)(i) 1 mark per bullet point • 95 to left of 97 • 109 to left of 121 • 135 to right of 125 • 149 to right of 135 • Null points in all places and no inappropriate pointers 5 RootPointer LeftPointer RightPointer 99 97 121 Ø 135 Ø 95 Ø Ø 125 Ø 109 149 Ø Ø Ø Ø

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 5 of 13 Question Answer Marks 2(a)(ii) 1 mark per bullet point • FreePointer as 8 • 99 • 125 • 121 and 97 • 109 and 95 • 135 and 149 RootPointer Index LeftPointer Data RightPointer 0 [0] 3 99 1 [1] 2 125 6 FreePointer [2] 4 121 null 8 [3] 5 97 null [4] null 109 null [5] null 95 null [6] null 135 7 [7] null 149 null [8] 6 2(b) 1 mark for each completed section FUNCTION FindElement(Item : INTEGER) RETURNS INTEGER CurrentPointer ← RootPointer WHILE CurrentPointer <> NullPointer IF List[CurrentPointer].Data <> Item THEN CurrentPointer ← List[CurrentPointer].Pointer ELSE RETURN CurrentPointer ENDIF ENDWHILE CurrentPointer ← NullPointer RETURN CurrentPointer ENDFUNCTION 6 2(c)(i) 1 mark per bullet point to max 3 e.g. • A sequence of steps that change the state of the program • The steps are in the order they should be carried out • e.g. procedural programming/language • Groups code into self-contained blocks // split the program into modules • « which are subroutines // by example 3

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 6 of 13 Question Answer Marks 2(c)(ii) 1 mark per bullet point to max 3 e.g. • Creates classes • «as a blueprint for an object // objects are instances of classes • «that have properties/attributes and methods • « that can be private to the class // properties can only be accessed by the class's methods // encapsulation • Subclasses can inherit from superclasses (child and parent) • A subclass can inherit the methods and properties from the superclass • A subclass can change the methods from the superclass // subclass can use polymorphism • Objects can interact with each other 3 2(d)(i) 1 mark per bullet point • Method header and close (where appropriate) • «with InputPlayerID parameter • Initialise Score to 0 • Initialise Category to "Not Qualified" • Initialise PlayerID to parameter PYTHON def__init__(self, InputPlayerID): self.__Score = 0 self.__Category = "Not Qualified" self.__PlayerID = InputPlayerID PASCAL Constructor Player.Create(InputPlayerID); begin Score := 0 ; Category := 'Not Qualified' ; PlayerID := InputPlayerID; end; VB Public Sub New (InputPlayerID) Score = 0 Category = "Not Qualified" PlayerID = InputPlayerID End Sub 5

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 7 of 13 Question Answer Marks 2(d)(ii) 1 mark per bullet point • 1 get Method header without parameter (returning correct data type if given) • «returning the property • A second working Get • A third working Get PYTHON def GetScore(): return (Score) def GetCategory(): return (Category) def GetPlayerID(): return (PlayerID) PASCAL function GetScore():Integer; begin GetScore:= Score; end; function GetCategory():String; begin GetCategory:= Category; end; function GetPlayerID():String; begin GetPlayerID:= PlayerID; end; VB Public Function GetScore() As Integer Return Score End Function Public Function GetCategory() As String Return Category End Function Public Function GetPlayerID() As String Return PlayerID End Function 4

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 8 of 13 Question Answer Marks 2(d)(iii) 1 mark per bullet point • Set method header and close (where appropriate) • Input value • Looping until input value is correct length « • « storing valid input value in PlayerID PYTHON def SetPlayerID(self) PlayerID = input("Enter your player ID") while len(PlayerID) > 15 and len(PlayerId) < 4 PlayerID = input("Must be <=15 AND >=4 characters long. Enter your player ID") PASCAL Procedure SetPlayerID () WriteLn ('Enter your player ID'); ReadLn(PlayerID); while length(PlayerID) > 15 and length(PlayerID) < 4 do begin WriteLn('Must be <=15 AND >=4 characters long. Enter your player ID'); ReadLn(PlayerID); end; VB Public Sub SetPlayerID() Console.WriteLine ("Enter your player ID") PlayerID = Console.ReadLine() While Len(PlayerID) > 15 and Len(PlayerID) < 4 Console.WriteLine ("Must be <=15 AND >=4 characters long. Enter your player ID") PlayerID = Console.ReadLine() End While End Sub 4

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 9 of 13 Question Answer Marks 2(d)(iv) 1 mark per bullet point • Function header and close (where appropriate) and takes ScoreInput as parameter • Check if 0 <= ScoreInput <= 150 • «if valid, set Score to parameter • «if not valid, output error • Returns TRUE if valid and returns FALSE if not valid PYTHON def __SetScore(ScoreInput): if ScoreInput >=0 and ScoreInput <=150: IsValid = True self__Score = ScoreInput else: print("Error") IsValid = False Return(IsValid) PASCAL function Player.SetScore(ScoreInput: Integer) : Boolean; begin If (ScoreInput >=0) AND (ScoreInput <=150) Then IsValid := True; result := ScoreInput; Else WriteLn('Error') result := False; end; VB Public Function SetScore(ByVal ScoreInput As Integer) As Boolean If (ScoreInput >=0) And (ScoreInput <=150) Then Return True Score = ScoreInput Else Console.Writeline("Error") Return False End If End Function 5

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 10 of 13 Question Answer Marks 2(d)(v) 1 mark per bullet point • Procedure header and close (where appropriate) • Accessing Score attribute • Correct selection to assign each category • « storing in Category attribute PYTHON def SetCategory() if self.__Score >120: self.__Category = "Advanced" elif self.__Score >80: self.__Category = "Intermediate" elif self.__Score>=50: self.__Category = "Beginner" else: self.__Category = "Not Qualified" PASCAL procedure player.SetCategory() begin If Score >120 Then Category := "Advanced"; Else If Score >80 Then Category := "Intermediate"; Else If Score >= 50 Then Category := "Beginner"; Else Category := "Not Qualified"; end; VB Public Sub SetCategory() If Score >120 Then Category = "Advanced" ElseIf Score >80 Then Category = "Intermediate" ElseIf Score >=50 Then Category = "Beginner" Else Category = "Not Qualified" End If End Sub 4

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 11 of 13 Question Answer Marks 2(d)(vi) 1 mark per bullet point • CreatePlayer() header and close (where appropriate) • Input of score and PlayerID with suitable prompts • Create instance of Player named JoannePlayer « • «with PlayerID as parameter • Call method SetScore for JoannePlayer with parameter Score • «storing return value • «outputting appropriate message for not valid • Call SetCategory for JoannePlayer • Output Category for JoannePlayer « • « using GetCategory for object Joanne PYTHON def CreatePlayer(): InputPlayerID = input("Enter your chosen ID") Score = int(input("Please enter the score")) JoannePlayer = Player(InputPlayerID) if JoannePlayer.SetScore(Score) == false: print("Invalid score") else: JoannePlayer.SetCategory() print(JoannePlayer.GetCategory) PASCAL procedure CreatePlayer(); var playerID : String; isValid : boolean; JoannePlayer : Player; score : integer; begin Writeln(Enter Player ID: '); Readln(playerID); Writeln('Enter score: '); Readln(score); JoannePlayer := Player.Create(PlayerID); isValid := JoannePlayer.SetScore(Score); if isValid = true: JoannePlayer.SetCategory(); Writeln(JoannePlayer.GetCategory()); else: Writeln("Invalid score") end; 8

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 12 of 13 Question Answer Marks 2(d)(vi) VB Sub CreatePlayer() Dim Score As Integer, InputPlayerID As String Console.WriteLine("Please enter your chosen ID") InputPlayerID = Console.ReadLine() Console.WriteLine("Please enter the score") Score = Console.ReadLine() Dim JoannePlayer As New Player(InputPlayerID) if JoannePlayer.SetScore(Score) = True then JoannePlayer.SetCategory() Console.WriteLine(JoannePlayer.GetCategory()) else Console.Writeline("Invalid score") endif End Sub 2(e) 1 mark per bullet point • 3 correct Normal test data • 3 correct Abnormal test data • 3 correct Boundary test data Category Type of test data Example test data Beginner Normal e.g. 75 Abnormal e.g. 85 / bob Boundary 80, 50 Intermediate Normal e.g. 95 Abnormal e.g. 70 / bob Boundary 81, 120 Advanced Normal e.g. 125 Abnormal e.g. 115 / bob Boundary 121, 150 3 2(f)(i) Insertion sort 1 2(f)(ii) One from: • Bubble sort • Merge sort 1

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2019 © UCLES 2019 Page 13 of 13 Question Answer Marks 2(f)(iii) 1 mark per shaded section Item NumberOfScores InsertScore Index ArrayData 0 1 2 3 4 99 125 121 109 115 1 5 125 0 (125) 2 121 1 125 0 121 3 109 2 125 1 121 0 109 4 115 3 125 2 121 1 115 7 Question Answer Marks 3(a) 1 mark per bullet point to max 2 • It is defined in terms of itself // it calls itself • It has a stopping condition // base case • It is a self-contained subroutine • It can return data to its previous call 2 3(b) 1 mark per bullet point to max 3 • (When the recursive call is made) all values/data are put on « • « the stack • When the stopping condition/base case is met • «the algorithm unwinds • «the last set of values are taken off the stack (in reverse order) 3