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

This document consists of 14 printed pages and 2 blank pages. DC (NF) 133468/3 © UCLES 2017 [Turn over Cambridge International Examinations Cambridge International Advanced Subsidiary and Advanced Level * 4 2 5 3 0 0 8 2 9 8 * COMPUTER SCIENCE 9608/22 Paper 2 Fundamental Problem-solving and Programming Skills October/November 2017 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/22/O/N/17 © UCLES 2017 1 (a) (i) Procedural high-level languages usually support different data types. Give an appropriate data type for each data value in the following table: Data value Data type FALSE 03/03/2013 35 "INTEGER" 3.5 "35" [6] (ii) The following is a declaration in a high-level language: DEFINE MyGrade[1 to 100] State the data structure of variable MyGrade. … [1] (iii) An experienced programmer is presented with program code in an unfamiliar high-level language. State two features of the code that the programmer should be able to recognise. 1 … … 2 … … [2]

3 9608/22/O/N/17 © UCLES 2017 [Turn over (b) (i) In the ASCII character set ‘A’ is represented by the value 65. The values representing the other characters of the alphabet follow in sequence, so ‘B’ is represented by 66, ‘C’ by 67 and so on. The following table represents consecutive memory locations. Each memory location stores one byte. Complete the table to show how the string "CAGE" may be stored in memory using the ASCII set. Address Data 100 101 102 103 104 105 [2] (ii) In a high-level language, a LENGTH function is used to return the number of characters in a string. Explain what is stored in addition to the string characters to allow this function to determine this number. … … … … [2] (c) Functions and procedures are subroutines. Explain why parameters are used with subroutines. … … … … … … [3]

4 9608/22/O/N/17 © UCLES 2017 (d) The following pseudocode is an example of a CASE structure. CASE OF MyMark 75 to 100: MyGrade "Distinction" 35 to 74: MyGrade "Pass" 0 to 34: MyGrade "Fail" OTHERWISE: OUTPUT "Invalid value entered" ENDCASE (i) Describe what will happen if the pseudocode is tested when MyMark has the following values: 27 … … 101 … … [2] (ii) Use pseudocode to write an IF statement with the same functionality. … … … … … … … … … … … … … … … … [5]

5 9608/22/O/N/17 © UCLES 2017 [Turn over Question 2 begins on the next page.

6 9608/22/O/N/17 © UCLES 2017 2 A 1D array, ClassName, of type STRING contains 100 elements. The following pseudocode represents a simple algorithm to process the array. DECLARE SearchValue : STRING DECLARE FoundFlag : BOOLEAN DECLARE Index : INTEGER INPUT SearchValue FoundFlag FALSE Index 1 WHILE Index < 101 AND FoundFlag = False IF ClassName[Index] = SearchValue THEN OUTPUT Index FoundFlag TRUE ENDIF Index Index + 1 ENDWHILE IF FoundFlag = FALSE THEN OUTPUT "Not found" ENDIF (a) Describe the purpose of the algorithm. … … … … … … [2]

7 9608/22/O/N/17 © UCLES 2017 [Turn over (b) Draw a program flowchart to represent this algorithm. Note that variable declarations are not required in program flowcharts. [9]

8 9608/22/O/N/17 © UCLES 2017 3 A 1D array, Product, of type STRING is used to store information about a range of products in a shop. There are 100 elements in the array. Each element stores one data item. The format of each data item is as follows: <ProductID><ProductName> • ProductID is a four-character string of numerals • ProductName is a variable-length string The following pseudocode is an initial attempt at defining a procedure, ArraySort, which will perform a bubble sort on Product. The array is to be sorted in ascending order of ProductID. Line numbers have been added for identification purposes only. 01 PROCEDURE SortArray 02 DECLARE Temp : CHAR 03 DECLARE FirstID, SecondID : INTEGER 04 FOR I 1 TO 100 05 FOR J 2 TO 99 06 FirstID MODULUS(LEFT(Product[J], 6)) 07 SecondID MODULUS(LEFT(Product[J + 1], 6)) 08 IF FirstID > SecondID 09 THEN 10 Temp Product[I] 11 Product[I] Product[J + 1] 12 Product[J + 1] Temp 13 ENDFOR 14 ENDIF 15 ENDFOR 16 ENDPROCEDURE

9 9608/22/O/N/17 © UCLES 2017 [Turn over The pseudocode on page 8 contains a number of errors. Complete the following table to show: • the line number of the error • the error itself • the correction that is required. Note: • If the same error occurs on more than one line, you should only refer to it ONCE. • Lack of optimisation should not be regarded as an error. Line number Error Correction 01 Wrong procedure name – “SortArray” PROCEDURE ArraySort [8]

10 9608/22/O/N/17 © UCLES 2017 4 Programming languages provide built-in functions to generate random numbers. To be truly random, the frequency of each number generated should be the same. You are required to write program code to test the random number generator of your chosen language. The test should: • generate a given number of random numbers between 1 and 10 inclusive • keep a count of the number of times each number is generated • calculate the expected frequency of each number 1 to 10 • output the actual frequency of each number 1 to 10 • output the difference between the actual frequency and the expected frequency. The program code should be written as a procedure. In pseudocode, the procedure heading will be: PROCEDURE TestRandom(Repetitions AS INTEGER) The parameter, Repetitions, contains a value representing the total number of random numbers that should be generated. The following example shows the expected output for the procedure call, TestRandom(200). The expected frequency is 20. Number Frequency Difference 1 17 −3 2 21 1 3 12 −8 4 28 8 5 20 0 6 19 −1 7 21 1 8 16 −4 9 24 4 10 22 2

11 9608/22/O/N/17 © UCLES 2017 [Turn over (a) Write program code for the procedure, TestRandom. Visual Basic and Pascal: You should include the declaration statements for variables. Python: You should show a comment statement for each variable used with its data type. Programming language … Program code … … … … … … … … … … … … … … … … … … … … … … … … [16]

12 9608/22/O/N/17 © UCLES 2017 (b) Name three features of a typical IDE that would help a programmer to debug a program. Explain how each of these could be used in the debugging of the TestRandom procedure from part (a). Feature 1 … Explanation … … … … Feature 2 … Explanation … … … … Feature 3 … Explanation … … … … [6] (c) The procedure is developed and run using the call TestRandom(200). No system errors are produced. To ensure that the procedure works correctly, you need to check the output. Describe two checks you should make to suggest the program works correctly. 1 … … … 2 … … … [2]

13 9608/22/O/N/17 © UCLES 2017 5 A sports club maintains a record of the email address of each of its members. The details are stored in a text file, EmailDetails.txt. The format of each line of the text file is as follows: <MembershipNumber><EmailAddress> • MembershipNumber is a four-character string of numerals • EmailAddress is a variable-length string When members leave the club their details need to be removed from the file. A procedure, RemoveDetails is required. This will perform the following actions: 1. Input the MembershipNumber of the club member to be removed 2. Create a new file, NewEmailDetails.txt 3. Copy all the lines from EmailDetails.txt to NewEmailDetails.txt, except the line with the matching MembershipNumber Write pseudocode for the procedure, RemoveDetails. For the built-in functions list, refer to the Appendix on page 15. … … … … … … … … … … … … … … … … [9]

14 9608/22/O/N/17 © UCLES 2017 BLANK PAGE

15 9608/22/O/N/17 © UCLES 2017 Appendix Built-in functions (pseudocode) In each function, if the function call is not properly formed, the function returns an error. MODULUS(x : INTEGER, y : INTEGER) RETURNS INTEGER returns the remainder when x is divided by y using integer arithmetic. Example: MODULUS(5, 2) will return 1 INT(x : REAL) RETURNS INTEGER returns the integer part of x. Example: INT(27.5415) returns 27 LENGTH(ThisString : STRING) RETURNS INTEGER returns the integer value representing the length of string ThisString. Example: LENGTH("Happy Days") returns 10 LEFT(ThisString : STRING, x : INTEGER) RETURNS STRING returns leftmost x characters from ThisString. Example: LEFT("ABCDEFGH", 3) returns string "ABC" RIGHT(ThisString : STRING, x : INTEGER) RETURNS STRING returns rightmost x characters from ThisString. Example: RIGHT("ABCDEFGH", 3) returns string "FGH" TONUM(ThisString : STRING) RETURNS INTEGER returns a numeric value equivalent to ThisString. Example: TONUM("1201") returns integer value 1201 Operators (pseudocode) Operator Description & Concatenates (joins) two strings. Example: "Summer" & " " & "Pudding" produces "Summer Pudding" AND Performs a logical AND on two Boolean values. Example: TRUE AND FALSE produces FALSE OR Performs a logical OR on two Boolean values. Example: TRUE OR FALSE produces TRUE

16 9608/22/O/N/17 © UCLES 2017 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 12 printed pages. © UCLES 2017 [Turn over Cambridge Assessment International Education Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/22 Paper 2 Written Paper October/November 2017 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 2017 series for most Cambridge IGCSE®, Cambridge International A and AS Level components and some Cambridge O Level components.

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 2 of 12 Question Answer Marks 1(a)(i) Data value Data type FALSE BOOLEAN 03/03/2013 DATE // DATETIME 35 INTEGER "INTEGER" STRING 3.5 REAL "35" STRING One mark for each data type Mark first data type given in each case 6 1(a)(ii) 1D Array // 1D List 1 1(a)(iii) Ability to recognise: • selection statement • iteration statement • assignment statements • data declarations / structures / data types / use of variables or objects • modular structure / functions / procedures / subroutines • subroutine parameters • Specific types of statement e.g. Input, Output, File operations • Code format • Operators Mark as follows: Any two from above, or valid alternative Accept by example 2 1(b)(i) Data 67 // 0100 0011 // 043h 65 // 0100 0001 // 041h 71 // 0100 0111 // 047h 69 // 0100 0101 // 045h One mark for 67 and 65 One mark for 71 and 69 Accept binary, denary or hex values (hex must be clearly indicated) Max one mark if blank cell anywhere in sequence Ignore any data values before or after the four characters 2

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 3 of 12 Question Answer Marks 1(b)(ii) • A value representing the number of characters ... ... stored at beginning of string OR • Terminator / special character ... ... stored to indicate the end of string One mark for each phrase or equivalent. 2 1(c) Explanation includes: • to pass values to/from the subroutine • to produce re-useable code • to avoid global variables • to allow recursion One mark per answer Max 3 1(d)(i) 27: MyGrade assigned the value "Fail" 101: Output the text "Invalid Value Entered" Ignore minor spelling mistakes 2 1(d)(ii) IF MyMark >= 75 AND MyMark <=100 THEN MyGrade ← "Distinction" ELSE IF MyMark >= 35 AND MyMark <=74 THEN MyGrade ← "Pass" ELSE IF MyMark >= 0 AND MyMark <=34 THEN MyGrade ← "Fail" ELSE OUTPUT "Invalid value entered" ENDIF ENDIF ENDIF One mark for each of: • One correct range test • ‘IF’ equivalent (nested or not) to three CASE range tests... • ... with three corresponding assignments • Equivalent of CASE OTHERWISE with corresponding OUTPUT statement • Matching (three) ENDIFs (Or one if ELSIFs used) Max 4 if solution doesn't work under all circumstances // is not functionally equivalent to CASE 5

9 © Ques 2(a 2(b 9608/22 © UCLES 2017 stion a) Mar • • • b) rk as follows To search and output if search v Cambridg s: for a given t the positio value not fou ge Internatio P value in the on in the arr und then ou onal AS/A L PUBLISHED Page 4 of 12 Answer e array ray if the se utput “Not fo Level – Mar D r arch value ound” k Scheme is found Octobe er/Novembe 201 M er 17 Marks Max 2 9

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 5 of 12 Question Answer Marks 2(b) Mark as follows: • One mark for START and STOP / END • One mark for each bracketed pair • One mark for each of other labelled symbol (decision box shape must be correct) • Allow F/T from incorrect decision symbol Full marks should be awarded for functionally equivalent solutions. Question Answer Marks 3 Line number Error Correction 01 Wrong procedure name – "SortArray" PROCEDURE ArraySort 02 Wrong data type - CHAR DECLARE Temp: STRING 03 Variables undefined DECLARE FirstID, SecondID, I, J : INTEGER 04 Wrong 'Value2' of 100 FOR I ← 1 TO 99 05 Wrong range FOR J ← 1 TO (100 – I) 06/07 Wrong function - MODULUS Replace MODULUS with TONUM: FirstID ← TONUM(LEFT(Product[J], 06/07 Wrong value of 6 Should be 4: FirstID ← TONUM(LEFT(Product[J], 10 Assigning wrong value to Temp Temp ← Product[J] 11 Assigning wrong value to Product[I] Product[J] ← Product[J + 1] 13/14 Lines reversed 13 ENDIF 14 ENDFOR One mark for each correct row Max 8

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 6 of 12 Question Answer Marks 4(a) Pseudocode solution included here for development and clarification of mark scheme. Programming language solutions appear in the Appendix. PROCEDURE TestRandom (Repetitions : INTEGER) DECLARE Frequency : ARRAY [1 : 10] OF INTEGER DECLARE Expected : REAL / INTEGER //allow either DECLARE NextRandom : INTEGER DECLARE N : INTEGER FOR N ← 1 TO 10 Frequency[N] ← 0 ENDFOR Expected ← INT(Repetitions / 10) CALL RANDOMIZE() //Set random seed FOR N ← 1 TO Repetitions NextRandom ← INT(RND() * 10) + 1 Frequency[NextRandom] ← Frequency[NextRandom] + 1 ENDFOR OUTPUT "The expected frequency is " & Expected OUTPUT "Number Frequency Difference" FOR N ← 1 TO 10 OUTPUT N & " " & Frequency[N] & " " & Frequency[N] – Expected ENDFOR ENDPROCEDURE Mark as follows: 1. Procedure heading (including parameter) 2. Array declaration – 10 or 11 elements 3. Array declaration – data type 4. Variable declaration for a loop counter (integer) or expected frequency (integer or real) 5. Variable declaration for next random value (For Python solutions, mark points 1 to 4 may be gained by suitable comments) 6. Initialise all elements of array 7. To set all elements to zero 8. Calculate expected frequency 16

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 7 of 12 Question Answer Marks 4(a) 9. Loop to generate required number of random values 10. Use of relevant RANDOM() function in a loop 11. Generate random integer value in the range 1 to 10 in a loop 12. Increment (array) element in a loop 13. Output expected frequency message not in any loop 14. Output column header text 15. (Loop to) output each row 16. ... including three correct values (spaces optional) 4(b) • Single-stepping – to allow program statements to be executed one at a time • Breakpoints – to pause / stop the program at a specific line / statement • Variable / expression watch window – to monitor the value of variables / expressions as the program is run One mark for each Feature (text as above or equivalent) + 1 for meaningful explanation of use in context. 6 4(c) Program is probably working correctly if: • Header is present giving frequency as 20 • Column headers are present • All rows are present (1 to 10) • The difference is calculated correctly • Output is formatted correctly • Total differences should be zero • Sum of Frequencies should be 200 Max 2

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 8 of 12 Question Answer Marks 5 PROCEDURE RemoveDetails DECLARE FileLine: STRING DECLARE MemberToDelete: STRING OPENFILE "EmailDetails.txt" FOR READ OPENFILE "NewEmailDetails.txt" FOR WRITE INPUT MembershipNumber WHILE NOT EOF("EmailDetails.txt") READFILE "EmailDetails.txt", FileLine IF LEFT(FileLine, 4) <> MembershipNumber THEN WRITEFILE "NewEmailDetails.txt", FileLine ENDIF ENDWHILE CLOSEFILE "EmailDetails.txt" CLOSEFILE "NewEmailDetails.txt" ENDPROCEDURE Mark as follows: 1. Procedure declaration and end. No parameters. 2. Variable declaration of STRING for variable FileLine (or similar) 3. Input the MembershipNumber of the person who has left 4. Open EmailDetails for READ 5. Open NewEmailDetails for WRITE 6. Correct loop checking for EOF(EmailDetails) 7. Reading a line from EmailDetails.txt in a loop 8. Correct check for MemberToDelete in a loop 9. Writing a line to NewEmailDetails.txt in a loop 10. Closing both files (not in a loop) Max 9

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 9 of 12 Appendix - Program Code Example Solutions Q4 (a): Visual Basic Dim random As New Random() Sub TestRandom(ByVal repetitions As Integer) Dim randinrange As Integer Dim i As Integer Dim num(1 To 10) As Integer Dim freq As Integer Dim difference As Integer freq = repetitions / 10 'calculate expected frequency For i = 1 To 10 'initialise array to store total frequencies num(i) = 0 Next i For i = 1 To repetitions 'generate random numbers & increment appropriate freq randinrange = random.Next(1, 11) num(randinrange) = num(randinrange) + 1 Next i Console.WriteLine("The expected frequency is " & freq) 'report header Console.WriteLine("Number Frequency Difference") 'column headers For i = 1 To 10 'calc & display difference between expected and actual freq difference = num(i) - freq Console.WriteLine(i & " " & num(i) & " " & difference) Next i End Sub Other possible ways of calculating a random number in VB include: randinrange = CInt(Math.Floor((upperbound - lowerbound + 1) * Rnd())) + lowerbound randinrange = math.round((Rnd()*9)+1) randinrange = CInt(Math.Ceiling(Rnd() * 9

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 10 of 12 Q4 (a): Pascal procedure TestRandom(var Repetitions : integer); var Frequency : array[1..10] : integer; Expected, NextRandom, N : integer; begin Expected := Round(Repetitions/10); for N := 1 to 10 do Frequency[N] := 0; for N := 1 to Repetitions do begin NextRandom := random(10)+1; Frequency[NextRandom] := Frequency[NextRandom]+1; end; writeln ('The expected frequency is ', Expected); writeln ('Number Frequency Difference'); for N := 1 to 10 do writeln (' ',N,' ',Frequency[N],' ',Frequency[N]- Expected); end;

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 11 of 12 Q4 (a): Python # frequency is an array from 1 to 10 of type integer; # nextNumber is an integer which stores the created random number # expected is an integer which stores the expected frequency of each number def TestRandom (repetitions): import random frequency = [0 for i in range(1,11)] # initialise each frequency count to 0 expected = repetitions / 10 for i in range(1, repetitions + 1): nextNumber = random.randint(1,10) frequency[nextNumber] = frequency[nextNumber]+ 1 print ("The expected frequency is ", expected) print(" Number Frequency Difference") for i in range(1,11): print (" ", i, " ", frequency[i]," ", frequency[i] - expected) Alternative: def TestRandom (repetitions): expected = repetitions / 10 ## initialised as real/integer ## NextRandom and N defined as integers frequency =[0,0,0,0,0,0,0,0,0,0,0] ## defined as an array and initialised to zero for n in range (0,repetitions): nextNumber = randint(1, 10) frequency[nextNumber] += 1 print ('The expected frequency is ', expected) print ('Number Frequency Difference') for n in range (1, 11): print (n,' ',frequency[n],' ',frequency[n] - expected) Alternative: frequency =[0]*11 ## alternate way to initialise array to zero frequency =[] ## empty array/list Alternative: for n in range (1,11): frequency[n-1] = 0 ##alternate way to initialise array to zero

9608/22 Cambridge International AS/A Level – Mark Scheme PUBLISHED October/November 2017 © UCLES 2017 Page 12 of 12 Alternative: for n in range (0,11): ##alternate way to initialise array to zero frequency.append(0)