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

This document has 20 pages. Any blank pages are indicated. Cambridge International AS & A Level COMPUTER SCIENCE 9608/43 Paper 4 Further Problem-solving and Programming Skills May/June 2021 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. * 8 9 7 1 0 0 7 5 4 4 * DC (CJ/CGW) 198995/3 © UCLES 2021 [Turn over

2 9608/43/M/J/21 © UCLES 2021 1 A vending machine allows users to insert coins to purchase an item. The user then enters the code for the item they would like the machine to dispense (give out). The user must re-enter the code until it is valid. If the code is valid but the user has not inserted enough money for the item chosen, the machine waits for more coins to be inserted. The user then has to re-enter the code. The user can press cancel at any time to return the money inserted into the machine. (a) The state-transition diagram shows the different states of the vending machine. Complete the state-transition diagram. … … … … … … … Return money Total the money inserted Check code valid Cancel Cancel Sufficient money Valid code Check total inserted Code re-entered [5]

3 9608/43/M/J/21 © UCLES 2021 [Turn over (b) The vending machine is part of a program that is written using object-oriented programming (OOP). The vending machine makes use of two classes that are described in the following tables. All attributes are declared as private. foodItem name : STRING code : STRING cost : REAL // the name of the item of food // the code to be entered for that item to be // selected // the cost of the item constructor(nameP, codeP, costP) getCode() getCost() getName() // creates an instance of foodItem // takes the name, code and cost as parameters // returns the code for the item // returns the cost of the item // returns the name of the item vendingMachine items : ARRAY[0:3] OF foodItem moneyIn : REAL // stores four items of type foodItem // stores the total money inserted by the // user, initialised to 0 in the constructor constructor(item1, item2, item3, item4) insertMoney() checkValid () getItemName() // creates an instance of vendingMachine, // takes four objects of type foodItem as // parameters and stores them in array items // takes the value of the coin as a parameter // and adds it to moneyIn // takes a code as a parameter and checks it is // valid against the food item codes // takes the array index as a parameter and // returns the name of the food items

4 9608/43/M/J/21 © UCLES 2021 (i) Write program code to declare the class vendingMachine. You are only required to write program code for the attribute declarations and the constructor. If you are writing in Python, include attribute declarations using comments. Use your programming language’s constructor method. Programming language … Program code … … … … … … … … … … … [4]

5 9608/43/M/J/21 © UCLES 2021 [Turn over (ii) The method checkValid() takes the food item code as a parameter. It checks the code against each element in items and returns: • –1 if the code is not valid • -2 if the code is valid, but the moneyIn is less than the cost of the item • the index of the item, if the code is valid and the moneyIn is greater than or equal to the cost of the item. Write program code for the method checkValid(). Programming language … Program code … … … … … … … … … … … … … [5] (iii) Four objects of type foodItem are declared with the identifiers: chocolate, sweets, sandwich, apple Write program code to declare an instance of vendingMachine with the identifier machineOne and the objects: chocolate, sweets, sandwich, apple. Programming language … Program code … … … … [2]

6 9608/43/M/J/21 © UCLES 2021 2 Peter uses a record structure, customer, to store data about customers. The data includes: • a unique customer ID between 10 000 and 99 999 • the customer's first name • the customer's last name • the customer's telephone number (for example, +44 1234567891). (a) Write pseudocode to define the record type customer. … … … … … … … … [3] (b) The customer records are stored in a random file. The location of each record is calculated as a hash value using: (customer.customerID modulus 1000) + 2 (i) Calculate the hash value for each of the customer IDs in the following table. Customer ID Hash value 40 125 10 131 [1] (ii) Two or more records could have the same hash value that results in a collision. Explain how the hashing algorithm can be designed to handle collisions. … … … … … … [3]

7 9608/43/M/J/21 © UCLES 2021 [Turn over (iii) The function, getCustomer(): • takes the customer ID as a parameter • passes the customer ID to the function getRecordLocation(), which returns the calculated hash value • reads and returns the record from the hashed location in the file customerRecords.dat You can assume that both the file and the record being accessed exist. Write pseudocode for the function getCustomer(). … … … … … … … … … … … … … … … … [5]

8 9608/43/M/J/21 © UCLES 2021 3 Alix manages a team of programmers who are creating a new computer game. Alix has listed some of the tasks, along with their estimated time to complete and their immediate predecessors in the following table: Task Description Predecessors Time to complete (weeks) A Design character – 1 B Program character movement A 1 C Design level 1 – 2 D Program level 1 C 2 E Design robot – 1 F Program robot movement E 1 G Integrate character in level 1 B, D 2 H Integrate robot in level 1 F, G 2 I Design level 2 C 2 J Program level 2 D, I 2 K Test level 1 H 3 L Integrate character and robot into level 2 J, K 2 (a) Complete the Program Evaluation Review Technique (PERT) chart for the tasks in the table. 4 7 2 E A 1 C 2 I 2 H 2 … … … … … … … … … … K 3 L 2 1 5 3 1 6 8 9 12 13 11 10 [5]

9 9608/43/M/J/21 © UCLES 2021 [Turn over (b) Explain how the tasks in the table can be divided between the team to allow concurrency of tasks. … … … … … … [2] (c) Explain the benefits of the team using program libraries in the development of the program. … … … … … … [3] (d) Identify two features in an editor that the developers can use to help them create their programs. Feature 1 … Feature 2 … [2]

10 9608/43/M/J/21 © UCLES 2021 4 Chon creates a binary tree structure to store options that the user can select from a menu (M) in his program. M R C A G L W (a) There are four new options that need to be added. If option G is selected, the user must choose either option D or option H. If option L is selected, the user must choose either option J or option P. Complete the following binary tree by adding options D, H, J and P. M R C A G L W [2]

11 9608/43/M/J/21 © UCLES 2021 [Turn over (b) Each node in the binary tree is stored using the following record structure: TYPE node leftPointer : INTEGER data : STRING rightPointer : INTEGER ENDTYPE The tree is stored as a 1D array, binaryTree. Null pointers are represented by –1. (i) The table shows the contents of the three fields in each record stored in the 1D array binaryTree. Complete the table to show the contents of binaryTree from part (a). rootPointer Index leftPointer data rightPointer 0 M freePointer 1 C 2 A 3 L 4 G 5 R 6 W 7 J 8 D 9 P 10 H 11 [4]

12 9608/43/M/J/21 © UCLES 2021 (ii) Write pseudocode to declare the array binaryTree to store up to 100 objects of type node. … … … … [2] (iii) A pre-order traversal on the following tree would output M C A G R L W M R C A G L W The pre-order traversal can be written as a recursive procedure: 1. output the root node 2. follow the left pointer and repeat from step 1 3. follow the right pointer and repeat from step 1. Complete the pseudocode recursive procedure preOrder(). PROCEDURE preOrder(BYVALUE rootPointer : INTEGER) … … … … … … … … … … … … …

13 9608/43/M/J/21 © UCLES 2021 [Turn over … … … … … … … ENDPROCEDURE [6]

14 9608/43/M/J/21 © UCLES 2021 5 A binary search algorithm searches for data in a sorted array. (a) The pseudocode function binarySearch()performs a binary search to find a given value in the global array, dataArray. If the value is found, the function returns its index. If the value is not found, the function returns –1. Complete the pseudocode for the function binarySearch(). FUNCTION binarySearch(BYVALUE upper, lower, searchValue : INTEGER) RETURNS INTEGER DECLARE flag : INTEGER DECLARE mid : INTEGER flag -2 mid 0 WHILE flag <> -1 mid lower + ((upper − lower) …………………………………………) IF upper < lower THEN RETURN ………………………………………… ELSE IF dataArray(mid) < searchValue THEN ………………………………………… ………………………………………… ELSE IF dataArray(mid) > searchValue THEN ………………………………………… ………………………………………… ELSE RETURN ………………………………………… ENDIF ENDIF ENDIF ENDWHILE ENDFUNCTION [4]

15 9608/43/M/J/21 © UCLES 2021 [Turn over (b) The binary search algorithm can be written recursively. Write program code for a recursive function recursiveBinarySearch(). Programming language … Program code … … … … … … … … … … … … … … … … … … … … … … … … [5]

16 9608/43/M/J/21 © UCLES 2021 6 The table shows assembly language instructions for a processor that has one general purpose register, the Accumulator (ACC), and an Index Register (IX). Instruction Explanation Label 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 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 contents of ACC at the given 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) AND <address> Bitwise AND operation of the contents of ACC with the contents of <address> XOR <address> Bitwise XOR operation of the contents of ACC with the contents of <address> OR <address> Bitwise OR operation of the contents of ACC with the contents of <address> OUT Output to screen the character whose ASCII value is stored in ACC 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 JMP <address> Jump to the given address END Return control to the operating system <label>: <op code> <operand> Labels an instruction <label>: <data> Gives a symbolic address <label> to the memory location with contents <data> An algorithm takes each letter of a stored 5-letter word and checks if the letter is upper case. If the letter is upper case, it outputs the letter. If the letter is not upper case, it converts the letter to upper case and then outputs it. All ASCII upper case letters have 010 as the three most significant bits. Assume each letter is alphabetic.

17 9608/43/M/J/21 © UCLES 2021 [Turn over Complete the assembly language program for the algorithm described using the instruction set provided on the previous page. Instruction Comment Label Op code Operand LDR #0 // load zero to IX // load count and check if it is 5 JPE endP // jump to end LDX word // load letter from indexed address word // check if it is upper case CMP #0 JPE output // jump to output if it is upper case LDX word // load letter from indexed address word // convert to upper case output: OUT // output the character // increase count by 1 INC IX // increase IX by 1 JMP start // return to start endP: end // end the program word: B01001000 B01101111 B01110101 B01110011 B01100101 mask1: B00100000 mask2: B11011111 count: 0 [6]

18 9608/43/M/J/21 © UCLES 2021 7 Giles is writing a program that uses a stack. The stack stores up to 1000 integers in the 1D array, stackArray. (a) The procedure setUpStack()takes two parameters: • the array, stackArray • a pointer to the last element pushed onto the stack, topOfStack The procedure initialises all array elements to −1 and the pointer to −1. Write pseudocode for the procedure setUpStack(). … … … … … … … … … [3] (b) The function pop() pops and returns the item from the top of the stack. If the stack is empty, it returns −1. Write pseudocode for the function pop(). … … … … … … … … … … [3]

19 9608/43/M/J/21 © UCLES 2021 BLANK PAGE

20 9608/43/M/J/21 © UCLES 2021 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 20 printed pages. © UCLES 2021 [Turn over Cambridge International AS & A Level COMPUTER SCIENCE 9608/43 Paper 4 Further Problem-solving and Programming Skills May/June 2021 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 2021 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 May/June 2021 © UCLES 2021 Page 2 of 20 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 2021 © UCLES 2021 Page 3 of 20 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 2021 © UCLES 2021 Page 4 of 20 Question Answer Marks 1(a) 1 mark for each completed space - accept any equivalent statements 5 Code re-entered Total the money inserted Check code valid Insert Coin Return money Dispense Item Enter code Insufficient money cancel cancel Sufficient money Check total inserted Valid code Cancel

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 5 of 20 Question Answer Marks 1(b)(i) 1 mark per bullet point to max 4 • Class declaration and end • Private Items declared as array with 4 elements of type foodItem • Private moneyIn declared as real and initialised to 0 in constructor • Constructor heading taking 4 parameters and end … • … assigning parameters to all 4 array values Example code: VB.NET Public Class vendingMachine Private items(3) As foodItem Private moneyIn As Single Public Sub New(item1, item2, item3, item4) items(0) = item1 items(1) = item2 items(2) = item3 items(3) = item4 moneyIn = 0 End Sub End Class Python class vendingMachine: #private items(4) of type foodItem #private moneyIn of type Real def __init__(self, item1, item2, item3, item4): self.__items = [] self.__items.append(item1) self.__items.append(item2) self.__items.append(item3) self.__items.append(item4) self.__moneyIn = 0 4

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 6 of 20 Question Answer Marks 1(b)(i) Pascal type vendingMachine = class private items : array[0..3] of foodItem; moneyIn : Real; public constructor init(); end; Constructor vendingMachine.init(item1, item2, item3, item4); begin items[0] := item1; items[1] := item2; items[2] := item3; items[3] := item4; moneyIn := 0; end;

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 7 of 20 Question Answer Marks 1(b)(ii) 1 mark per bullet point to max 5 • Function header taking parameter (and close where appropriate) • Finding position in array // finding if not in array … • … if not found, return −1 • Checking cost against moneyIn … • … if not enough money, return –2 • … if found and enough money, return position • Using Items, getCost() and getCode() throughout Example code: VB.NET Public Function checkValid(code) For x = 0 To 3 If items(x).getCode = code Then If items(x).getCost <= moneyIn Then Return x Else Return -2 End If End If Next Return -1 End Function Python def checkValidCode(code): for x in range (0,4): if items[x].getCode == code: if items[x].getCost <= moneyIn: return x else: return -2 return -1 5

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 8 of 20 Question Answer Marks 1(b)(ii) Pascal Function checkValidCode(code):Integer begin for x := 0 to 3 do if items[x].getCode = code then if items[x].getCost <= moneyIn then return x else return -2 return -1 end; 1(b)(iii) 1 mark per bullet point to max 2 • Declaration of new instance of vendingMachine with identifier machineOne … • …passing all four objects as parameters using constructor Example code: VB.NET Dim machineOne as vendingMachine machineOne = new vendingMachine(chocolate, sweets, sandwich, apple) Python machineOne = vendingMachine(chocolate, sweets, sandwich, apple) Pascal machineOne := vendingMachine.Create(chocolate, sweets, sandwich, apple); 2

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 9 of 20 Question Answer Marks 2(a) 1 mark per bullet point • Definition with identifier customer … • … customerID with data type integer • … remaining 3 fields with data type string e.g. TYPE customer DECLARE customerID AS INTEGER DECLARE firstName AS STRING DECLARE lastName AS STRING DECLARE telephoneNumber AS STRING ENDTYPE 3 2(b)(i) 1 mark for both hash values Customer ID Hash value 40125 127 10131 133 1 2(b)(ii) 1 mark per bullet point to max 3 • Check each location serially until finds a free record // linear search … • … or if reaches end of file continue checking from first record • … track how many records checked and if all checked report file full • Use of an overflow table … • … that stores records with collisions • … serially/in order • Implement a linked list for each hash location … • … store record in first free node in linked list • … update that location's last node linked list pointer 3

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 10 of 20 Question Answer Marks 2(b)(iii) 1 mark per bullet point to max 5 • Function declaration taking Customer ID as parameter returning type customer • Opening "customerRecords.data" for random • Calling getRecordLocation() with parameter … • … storing return value • Finding location in file using hash value … • … accessing record from location • … return value • Closing file in appropriate place under all conditions Example code: FUNCTION getCustomer(customerID) RETURNS customer DECLARE customerRec : customer filename = "customerRecords.dat" OPENFILE filename FOR RANDOM SEEK filename, getRecordLocation(customerID) GETRECORD filename, customerRec CLOSEFILE filename RETURN customerRec ENDFUNCTION 5

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 11 of 20 Question Answer Marks 3(a) 1 mark for each completed part 5 3(b) 1 mark per bullet point to max 2 • A C and E can be split between different people • B D F and I can be split between different people • G and J can be split between different people 2 1 2 3 4 5 6 7 8 9 10 11 12 K 3 13 C 2 E 1 D 2 F 1 G 2 H 2 I 2 J 2 L 2 A 1 B 1

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 12 of 20 Question Answer Marks 3(c) 1 mark per bullet point to max 3 • Do not have to write functions/code themselves • … therefore, saves time when writing the program • Thoroughly tested routines • … improve robustness of your program • You do not need to test/debug the routines • … saves time testing • Can make use of other people's expertise • … can use algorithms that you do not have the skills to write yourself 3 3(d) 1 mark per feature to max 2 e.g. • colour coding / pretty printing • auto-indent • auto-complete • collapse/expand modules • context sensitive prompts • breakpoints • dynamic syntax highlighting 2

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 13 of 20 Question Answer Marks 4(a) 1 mark for adding D and H below G 1 mark for adding J and P below L 2 M C A G D H R L J P W

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 14 of 20 Question Answer Marks 4(b)(i) 1 mark for rootPointer pointing to 0 1 mark for freePointer pointing to 11 1 mark for left and right correctly linked nodes 0 TO 5 1 mark for -1 added as pointer for all remaining null pointers rootPointer 0 Index leftPointer data rightPointer freePointer 11 0 1 M 5 1 2 C 4 2 -1 A -1 3 7 L 9 4 8 G 10 5 3 R 6 6 -1 W -1 7 -1 J -1 8 -1 D -1 9 -1 P -1 10 -1 H -1 11 (-1) (-1) 4 4(b)(ii) 1 mark per bullet point • Defining 1D array with 100 elements • of type node, with identifier binaryTree Example: DECLARE binaryTree : ARRAY[0:99] OF node 2

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 15 of 20 Question Answer Marks 4(b)(iii) 1 mark per bullet point • Outputting the data in the root node • Check if left Pointer is/is not –1 … • … recursive call left with left pointer as parameter, if not –1 • Check if right Pointer is/is not –1 … • … recursive call right with right pointer as parameter, if not −1 • Output, left, right in correct order with Example code: PROCEDURE preOrder(rootpointer) OUTPUT(binaryTree[rootPointer].Data) IF binaryTree[rootPointer].leftPointer <> -1 THEN preOrder(binaryTree[rootPointer].LeftPointer) ENDIF IF binaryTree[rootPointer].rightPointer <> -1 THEN preOrder(binaryTree[rootPointer].rightPointer) ENDIF ENDPROCEDURE 6

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 16 of 20 Question Answer Marks 5(a) 1 mark for both returns 1 mark for each completed statement FUNCTION binarySearch(BYVALUE upper,lower, searchValue : INTEGER) RETURNS INTEGER DECLARE flag : INTEGER DECLARE mid : INTEGER flag ← -2 mid ← 0 WHILE flag <> -1 mid ← lower + ((upper - lower) DIV 2) IF upper < lower THEN RETURN -1 ELSE IF dataArray(mid) < searchValue THEN lower ← mid + 1 ELSE IF dataArray(mid) > searchValue THEN upper ← mid - 1 ELSE RETURN mid ENDIF ENDIF ENDIF ENDWHILE ENDFUNCTION 4

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 17 of 20 Question Answer Marks 5(b) 1 mark per bullet point • If search value is greater, then recursive call… • …with the mid + 1 sent in place as lower (and other correct parameters) • If search value is less than recursive call… • …with the mid − 1 sent in place as upper (and other correct parameters) • Return −1 when not found AND Return mid when found Example code: VB.NET Function recursiveBinarySearch(ByVal lowerbound, ByVal upperbound, ByVal searchValue) Dim mid As Integer = 0 mid = lowerbound + ((upperbound - lowerbound) \ 2) If upperbound < lowerbound Then Return -1 Else If dataArray(mid) < searchValue Then Return recursivebinarySearch(mid + 1, upperbound, searchValue) ElseIf dataArray(mid) > searchValue Then Return recursivebinarySearch(lowerbound, mid - 1, searchValue) Else Return mid End If End If End Function 5

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 18 of 20 Question Answer Marks 5(b) Python def recursiveBinarySearch(lowerbound, upperbound, searchValue): mid = lowerbound + int((upperbound - lowerbound)/2) if upperbound < lowerbound: return -1 else: if dataArray[mid] < searchValue: return recursiveBinarySearch(mid + 1, upperbound, searchValue) elif dataArray[mid] > searchValue: return recursiveBinarySearch(lowerbound, mid - 1, searchValue) else: return mid Pascal Function recursiveBinarySearch(lowerbound:Integer, upperbound:Integer, searchValue: Integer):Integer; begin mid = lowerbound + ((upperbound - lowerbound) div 2); if upperbound < lowerbound then return -1; else if dataArray(mid) < searchValue then return recursiveBinarySearch(mid + 1, upperbound, searchValue); else if dataArray(mid) > searchValue then return recursiveBinarySearch(lowerbound, mid - 1, searchValue); end;

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 19 of 20 Question Answer Marks 6 Instruction Marks Label Op Code Operand LDR #0 start: LDD count 1 mark for start 1 mark for LDD count 1 mark for CMP #5 CMP #5 JPE endP LDX word AND Mask1 1 mark CMP #0 JPE output LDX word AND Mask2 1 mark output: OUT LDD count 1 mark INC ACC STO count INC IX JMP start endP: end word: B01001000 B01101111 B01110101 B01110011 B01100101 mask1: B00100000 mask2: B11011111 count: 0 6

9608/43 Cambridge International AS & A Level – Mark Scheme PUBLISHED May/June 2021 © UCLES 2021 Page 20 of 20 Question Answer Marks 7(a) 1 mark per bullet point • procedure header taking array and pointer as parameters … • … by reference • Initialising all 1000 array elements to −1 and pointer to −1 Example: PROCEDURE setUpStack(ByRef stackArray, ByRef topOfStack : INTEGER) FOR x = 0 to 999 stackArray[x] ← -1 NEXT x topOfStack ← -1 ENDPROCEDURE 3 7(b) 1 mark per bullet point • Function header (and end taking array and pointer by reference) and checking stack empty … • … if empty, return −1 • … if not empty, return topOfStack data item from stack and decrement pointer FUNCTION pop(ByRef stackArray, ByRef topOfStack: INTEGER) RETURNS INTEGER IF topOfStack < 0 THEN RETURN -1 ELSE dataToReturn ← stackArray[topOfStack] topOfStack ← topOfStack - 1 RETURN dataToReturn ENDIF ENDFUNCTION 3