Cambridge A Level Computer Science 9608 — 2020 Oct/Nov Paper 4 · Variant 2

Cambridge International AS & A Level DC (ST) 183190/4 © UCLES 2020 [Turn over This document has 20 pages. Blank pages are indicated. * 0 2 5 1 5 2 9 3 1 6 * COMPUTER SCIENCE 9608/42 Paper 4 Further Problem-solving and Programming Skills October/November 2020 2 hours You must answer on the question paper. No additional materials are needed. INSTRUCTIONS ● Answer all questions. ● Use a black or dark blue pen. ● Write your name, centre number and candidate number in the boxes at the top of the page. ● Write your answer to each question in the space provided. ● Do not use an erasable pen or correction fluid. ● Do not write on any bar codes. ● You may use an HB pencil for any diagrams, graphs or rough working. ● Calculators must not be used in this paper. INFORMATION ● The total mark for this paper is 75. ● The number of marks for each question or part question is shown in brackets [ ]. ● No marks will be awarded for using brand names of software packages or hardware.

2 9608/42/O/N/20 © UCLES 2020 1 There are several different searching and sorting algorithms. (a) Identify two sorting algorithms. 1 … 2 … [2] (b) Consider the following pseudocode algorithm. LowerBound 0 UpperBound LengthOfList – 1 ValueFound FALSE OUTPUT "Value to find: " INPUT ValueToFind WHILE ValueFound = FALSE AND UpperBound <> LowerBound MidPoint (LowerBound + UpperBound)DIV 2 IF List[MidPoint] = ValueToFind THEN ValueFound TRUE ELSE IF List[MidPoint] < ValueToFind THEN LowerBound MidPoint + 1 ELSE UpperBound MidPoint – 1 ENDIF ENDIF ENDWHILE IF ValueFound = FALSE THEN MidPoint (LowerBound + UpperBound) DIV 2 IF List[MidPoint] = ValueToFind THEN OUTPUT "Item in position " & MidPoint & " in list" ELSE OUTPUT "Not in list" ENDIF ELSE OUTPUT "Item in position " & MidPoint & " in list" ENDIF Note: DIV is an operator that performs integer division. The array List contains the following values: 2, 5, 21, 25, 36, 48, 51, 59, 65, 70

3 9608/42/O/N/20 © UCLES 2020 [Turn over (i) Complete the trace table to show a dry run of the algorithm, when the value 21 is input. LowerBound UpperBound ValueFound ValueToFind MidPoint [3] (ii) Identify this type of searching algorithm. … [1] (iii) The value 59 is input. State the number of times the while loop condition is executed. … [1] (iv) State the minimum number of times the while loop condition will be executed to search for a value. … [1] (v) MidPoint is calculated and checked again after the while loop is terminated. Explain why this additional calculation and check is necessary. … … … … [2]

4 9608/42/O/N/20 © UCLES 2020 (vi) A new data set is used as follows: 5, 9, 10, 12, 15, 13, 17, 19, 20, 2 Explain why the algorithm will not find the value 2 in this data set. … … … … [2]

5 9608/42/O/N/20 © UCLES 2020 [Turn over BLANK PAGE

6 9608/42/O/N/20 © UCLES 2020 2 A company is developing a new puzzle game application for a mobile phone. The development includes the following activities: Activity Description Time taken in weeks Predecessor A Identify requirements 2 – B Produce design 3 A C Focus group feedback on design 2 B D Program 5 levels 4 C E Graphics development 6 C F Focus group testing on 5 levels 2 D G Program remaining levels 5 D H Combine modules 2 G I White-box testing 2 H J Black-box testing 2 H K User testing 2 H L Beta release 2 K (a) Complete the GANTT chart for the given activities. A B C D E F G H I J K L Week number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [5]

7 9608/42/O/N/20 © UCLES 2020 [Turn over (b) (i) State the activities that form the critical path. … [1] (ii) Give three activities that can run in parallel. … [1] (c) Identify another project planning technique that could be used when developing the puzzle game. … [1]

8 9608/42/O/N/20 © UCLES 2020 3 A declarative programming language is used to represent the following knowledge base. 01 person(jordan). 02 person(gita). 03 person(paolo). 04 person(cassie). 05 animal(cat). 06 animal(hamster). 07 animal(gecko). 08 animal(fish). 09 has_pet(cassie, gecko). 10 has_pet(paolo, fish). 11 has_pet(cassie, cat). 12 has_pet(jordan, cat). These clauses have the following meanings: Clause Meaning 01 Jordan is a person 05 A cat is an animal 09 Cassie has a pet gecko (a) Clive is a person who has a pet guinea pig and a pet gecko. Write additional clauses to represent this information. 13 … 14 … 15 … 16 … [4]

9 9608/42/O/N/20 © UCLES 2020 [Turn over (b) Using the variable PetOwner, the goal: has_pet(PetOwner, cat) returns: PetOwner = cassie, jordan Write the result that is returned by the goal: has_pet(cassie, PetAnimals) PetAnimals = … … [1] (c) Z wants a pet Y, if Z is a person and Y is an animal and Z does not have a pet Y. Write this as a rule. wants_pet(… , …) IF … … … [5]

10 9608/42/O/N/20 © UCLES 2020 4 A programmer wants to create a mobile application to record the number of calories a person eats in a day. The programmer has designed the class, FoodItem, to store details for each item of food. The following diagram shows the design for the FoodItem class. FoodItem FoodID : STRING // initialised in constructor to parameter value Name : STRING // initialised in constructor to an empty string Calories : INTEGER // initialised in constructor to 0 Constructor() // method used to create an instance of the // FoodItem class and initialise its attributes GetFoodID() // returns FoodID GetName() // returns Name GetCalories() // returns Calories SetFoodID() // sets the FoodID to the parameter value SetName() // sets the Name to the parameter value SetCalories() // validates the parameter value to make sure // it is a positive integer less than 2000, and // then sets Calories to this value (a) Write program code for the Constructor() method. Use the appropriate constructor method for your chosen programming language. Programming language … Program code … … … … … … … … … … [3]

11 9608/42/O/N/20 © UCLES 2020 [Turn over (b) Write program code for the GetCalories() method. Programming language … Program code … … … … … … [2] (c) The method SetCalories() validates the integer parameter value that is passed to it. It checks that the value is positive and is less than 2000. The method sets Calories to the parameter value and returns TRUE if the parameter value is valid. It returns FALSE if the parameter value is not valid. Write pseudocode for the SetCalories() method. … … … … … … … … … … … … [4]

12 9608/42/O/N/20 © UCLES 2020 (d) The following is a class diagram for the application. CustomerProfile FoodItem Name : STRING Email : STRING TotalCalories : INTEGER FoodID : STRING Name : STRING Calories : INTEGER GetName() GetEmail() GetTotalCalories() SetName() SetEmail() SetTotalCalories() GetFoodID() GetName() GetCalories() SetFoodID() SetName() SetCalories() DailyCalories Date : DATE TotalCalories : INTEGER GetDate() SetDate() GetTotalCalories() SetTotalCalories() (i) The attributes of the class, CustomerProfile, are declared as private. Explain why it is good practice to declare class attributes as private. … … … … [2] (ii) Explain what is meant by inheritance, using an example from the class diagram. … … … … [2]

13 9608/42/O/N/20 © UCLES 2020 [Turn over (iii) Explain what is meant by polymorphism, using an example from the class diagram. … … … … [2] (e) Object-oriented programming is an example of a programming paradigm. Another example is imperative programming. Explain what is meant by the imperative programming paradigm. … … … … [2] (f) Testing is regularly performed during the development of software. (i) Independent modules are combined to create the final program. Testing is performed to make sure they interact correctly. Identify this type of testing. … [1] (ii) Testing is performed to prove to the customer that the system works correctly and meets the requirements specified in the design. Identify this type of testing. … [1] (iii) Test plans are used when testing data. One item that would be included in a test plan is example test data. Identify two other items that would appear in a test plan. 1 … 2 … [2]

14 9608/42/O/N/20 © UCLES 2020 5 The following table shows part of the instruction set for a processor that 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 of ACC to this calculated address. ADD <address> Add the contents of the given address to 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. 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.

15 9608/42/O/N/20 © UCLES 2020 [Turn over Consider the following pseudocode algorithm: Length 0 INPUT Character WHILE Character <> "." Message Message & Character Length Length + 1 INPUT Character ENDWHILE Complete the table by writing assembly language code for the algorithm, using the given instruction set. Label Instruction Comment Op code Operand // initialise IX to zero // initialise LENGTH LOOP: // input character // is character a FULLSTOP (.) ? // jump to ENDP if TRUE // store character in MESSAGE + contents of IX // increment IX // increment LENGTH // jump to LOOP ENDP: END // end program LENGTH: FULLSTOP: B01100000 // ASCII code for a full stop (.) MESSAGE: [8]

16 9608/42/O/N/20 © UCLES 2020 6 The following diagram represents a linked list. Data Pointer A B C D Ø The symbol Ø represents a null pointer. (a) The node with the data value C is removed from the list. Show the new state of the linked list. [2] (b) State what happens to the node with the data value C when it is removed from the list. … … [1] (c) State what is meant by a null pointer. … [1]

17 9608/42/O/N/20 © UCLES 2020 [Turn over (d) The linked list is implemented as a 1D array, LinkedList. The array is declared as a record data type, with two fields, Data and Pointer. The function FindValue() takes as a parameter, the value to be searched for in the linked list. The function follows the pointers in the linked list. It returns -1 if the value is not found, or it returns the pointer to the value if it is found. The global variable StartPointer points to the first element in the list. Write pseudocode for the function FindValue(). … … … … … … … … … … … … … … … … … … [8]

18 9608/42/O/N/20 © UCLES 2020 (e) A linked list and a record are both examples of abstract data types. Identify and describe one other abstract data type. Abstract data type … Description … … … … … … … [4]

19 9608/42/O/N/20 © UCLES 2020 BLANK PAGE

20 9608/42/O/N/20 © UCLES 2020 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 2020 [Turn over Cambridge International AS & A Level COMPUTER SCIENCE 9608/42 Paper 4 Written Paper October/November 2020 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 2020 series for most Cambridge IGCSE™, Cambridge International A and AS Level and Cambridge Pre-U components, and some Cambridge O Level components.

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 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.

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 3 of 13 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/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 4 of 13 Question Answer Marks 1(a) • Bubble (sort) • Insertion (sort) 2 1(b)(i) LowerBound UpperBound ValueFound ValueToFind MidPoint 0 9 FALSE 21 4 3 1 2 2 TRUE One mark for columns 1 and 2, 1 mark for columns 3 and 4, 1 mark for column 5 3 1(b)(ii) Binary (search) 1 1(b)(iii) • 3 1 1(b)(iv) • 1 // 2 1 1(b)(v) • If UpperBound and LowerBound are the same // if value is on the upper bound or lower bound // if there is only 1 item in the list … • … the last value is not checked // it won't be found // the while loop doesn't checks the last value 2 1(b)(vi) • List is not sorted // Binary search only works on a sorted list • 2 is less than the midpoint // 2 is after a larger value // by example • … so (13 to) 2 would be discarded after first comparison // it will be looking for 2 in the lower half // value looking for will be discarded in first comparison 2

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 5 of 13 Question Answer Marks 2(a) A B C D E F G H I J K L Week number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 • A(2), B(3) following A, C(2) following B • D(4) following C, E(6) following C • F(2) following D, G(5) following D • H(2) following G, L(2) following K • I, J, K (2 each) following I 5 2(b)(i) A, B, C, D, G, H, K, L 1

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 6 of 13 Question Answer Marks 2(b)(ii) I, J, K // White-box, black-box, user testing // E, F, G // Graphics development, Focus group, Program remaining levels 1 2(c) PERT 1 Question Answer Marks 3(a) • person(clive). • animal(guinea_pig). • has_pet(clive, guinea_pig). • has_pet(clive, gecko). 4 3(b) gecko, cat 1 3(c) • wants_pet(Z, Y) • person(Z) // animal(Y) • AND animal(Y) // AND person(Z) • AND NOT • has_pet(Z, Y) 5

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 7 of 13 Question Answer Marks 4(a) • Correct header and close (where applicable) with one parameter (ignore other parameters) • parameter (any identifier) assigned to attribute FoodID • Correct values assigned to Name ("") and Calories (0) PYTHON def __init__(self, NewFoodID): self.__FoodID = NewFoodID self.__Name = "" self.__Calories = 0 PASCAL Constructor FoodItem.Create(NewFoodID : String); Begin FoodID := NewFoodID; Name : = ""; Calories := 0; End; VB Public Sub New(ByVal NewFoodID As String) FoodID = NewFoodID Name = "" Calories = 0 End Sub 3

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 8 of 13 Question Answer Marks 4(b) • Correct function header and close (where applicable) with no parameter (if they have a return data type it must be correct (Integer), but not necessary) • Returns Calories without other input/assignment (using return command, or assigning to GetCalories) PYTHON def GetCalories(self): return(self.__Calories) PASCAL Function FoodItem.GetCalories() : Integer; Begin GetCalories := Calories; End VB Public Function GetCalories() As Integer Return Calories End function 2 4(c) • Correct function header (and close) with one parameter passed (ignore additional parameters) (if they have a return data type it must be correct (Boolean), but not necessary) • Checks parameter is an integer between 0/1 and less than 2000. • …Returns true if parameter is valid and assigns parameter to Calories • …Returns false if invalid and does not assign the parameter to Calories FUNCTION SetCalories(NumCalories : INTEGER) RETURNS BOOLEAN DECLARE Valid : BOOLEAN IF NumCalories > 0 AND NumCalories < 2000 THEN Calories ← NumCalories Valid ← TRUE ELSE Valid ← FALSE ENDIF RETURN Valid ENDFUNCTION 4

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 9 of 13 Question Answer Marks 4(d)(i) Two from: • Limits access to given/set/get methods only // can only be accessed through the methods • …attributes cannot be accidentally changed // ensure attribute integrity/security against accidental change (not program) • Use of set method allows for validation of attribute • .. ensure attribute not set to inappropriate value // make sure attribute value is valid • Ensures encapsulation 2 4(d)(ii) Two from: • Child class can use/has the attributes/methods of its parent class (Accept transferring attributes/methods. • The class DailyCalories inherits (attributes/methods) from the class CustomerProfile • DailyCalories can use/extend the attributes/methods from CustomerProfile // by example 2 4(d)(iii) Two from: • Child class method/attribute can override parent class method/attribute // related / parent and child class have same method that has different functions/purpose • GetTotalCalories()/SetTotalCalories() method from CustomerProfile overwritten/has different function in DailyCalories • TotalCalories in DailyCalories overrides TotalCalories in CustomerProfile 2 4(e) Two from: • Writing a program as a sequence of (explicit) steps/commands // sequence of events/steps // step-by-step instructions • … to gain a required outcome/result // focus is on how to achieve a result / solve a problem • The statements in the program manipulate the data • An example would be procedural programming 2 4(f)(i) • Integration testing 1 4(f)(ii) • Acceptance testing 1

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 10 of 13 Question Answer Marks 4(f)(iii) Two from: • Test number • Type of test // type of test data • Test description • Expected outcome 2

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 11 of 13 Question Answer Marks 5 Label Op Code Operand Comment LDR #0 // initialise IX to zero [1] LDM #0 // initialise LENGTH [1] STO LENGTH LOOP: IN // input character [1] CMP FULLSTOP // is character a FULLSTOP (.) ? [1] JPE ENDP // jump to ENDP if TRUE STX MESSAGE // store character in MESSAGE + contents of IX [1] INC IX // increment IX [1] LDD LENGTH // increment LENGTH [1] INC ACC STO LENGTH JMP LOOP // jump to LOOP [1] ENDP: END // end program LENGTH: FULLSTOP: B01100000 // ASCII code for a full stop (.) MESSAGE: 8

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 12 of 13 Question Answer Marks 6(a) • A to B to D including NULL pointer in D … • … C not present // C present but nothing pointing to it 2 6(b) • Added to free space/list // free pointer points to C // last element in free space links to C 1 6(c) • Does not point to another node/address // end of list // end pointer 1 6(d) • Correct function header (and close), (sensible) parameter (Not boolean) (and return data type) • Starting pointer set using StartPointer • Check if current pointer is NULL • Check if data at current pointer = parameter • Updates/follows next pointer to current item's pointer • Recursion or iteration used to check all values not linear search • Returns correct pointer when value found • Returns −1 when all items check and still not found FUNCTION FindValue(Value : INTEGER) RETURNS INTEGER CurrentPointer ← StartPointer WHILE CurrentPointer <> NULL AND LinkedList[CurrentPointer].Data <> Value CurrentPointer ← LinkedList[CurrentPointer].Pointer ENDWHILE IF LinkedList[CurrentPointer].Data = Value THEN RETURN CurrentPointer ELSE RETURN -1 ENDIF ENDFUNCTION 8

9608/42 Cambridge International AS & A Level – Mark Scheme PUBLISHED October/November 2020 © UCLES 2020 Page 13 of 13 Question Answer Marks 6(e) Four from a single ADT (one for identifying and three for description): e.g. • Stack - Linear structure - Last in first out structure - Has top and base stack pointers - Uses push to add items to top of stack - Uses pop to remove items from top of stack • Queue - Linear structure - First in first out structure - Has start and end of queue pointers - Can be circular - Uses enqueue to add item to end of queue - Uses dequeue to remove item from start of queue • Binary tree - Each node can have up to two (child) nodes - Parent node is above, and child nodes follow - Each node contains the data and pointer(s) - Has a root node - Can have leaf nodes - Can be output/searched in-order/post-order/pre-order - Can be ordered or unordered - Description of adding a new node // Description of ordered tree • Class - A class represents an object - Objects are instances of classes - (An object) has attributes and methods - Classes can be inherited • Hash table - Key calculated from value - .. (key) that represents a location // stores values in key locations - Key used to access location - Description of managing collisions 4