Algorithms — Paper 2 · A Level Computer Science 9618

2 (a) Four program modules form part of a program for a library. A description of the relationship between the modules is summarised as follows: Module name Description UpdateLoan() • Calls either LoanExtend() or LoanReturn() • Called with parameters LoanID and BookID • Calls CheckReserve() to see whether the book has been LoanExtend() reserved for another library user • Returns TRUE if the loan has been extended, otherwise returns FALSE • Called with BookID CheckReserve() • Returns TRUE if the book has been reserved, otherwise returns FALSE • Called with parameters LoanID and BookID LoanReturn() • Returns a REAL (which is the value of the fine to be paid in the case of an overdue loan) Draw a structure chart to show the relationship between the four modules and the parameters passed between them. [5] (b) The definition for module LoanReturn() is amended as follows: Module name Description Called with parameters LoanID, BookID and Fine LoanReturn() The module code checks whether the book has been returned on time and then assigns a new value to Fine • LoanID and BookID are of type STRING • Fine is of type REAL Write the pseudocode header for the amended module LoanReturn(). … … [2] (c) A program will: • input 50 unique integer values • output the largest value • output the average of the values excluding the largest value. Draw a program flowchart to represent the algorithm. Variable declarations are not required. It is not necessary to check that each input value is unique. [6]

13 marks

Mark scheme: 2(a) 5 One mark for: 1 All four boxes correctly labelled and positioned 2 Selection diamond (only on UpdateLoan and no iteration arrows) 3 Parameters to and from LoanExtend() 4 Parameters to and from CheckReserve() 5 Parameters to and from LoanReturn() 2(b) PROCEDURE LoanReturn (LoanID, BookID : STRING, 2 BYREF Fine : REAL) One mark for each underlined part 2(c) Example solution: 6 One mark for each functional group as listed below: 2(c) Explanation of mark points: 1 Initialise MAX to first value input 2 Set Total to zero 3 Input 49 more values (or 50 values in total) 4 Sum all values input 5 Set new MAX when Input value > MAX in a loop 6 Sum all but largest (or subtract MAX from total), calculate and output average

This question in 9618/21 May/June 2021

5 A global 2D array Result of type INTEGER is used to store a list of exam candidate numbers together with their marks. The array contains 2000 elements, organised as 1000 rows and 2 columns. Column 1 contains the candidate number and column 2 contains the mark for the corresponding candidate. All elements contain valid exam result data. A procedure Sort() is needed to sort Result into ascending order of mark using an efficient bubble sort algorithm. Write pseudocode for the procedure Sort(). … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … [8]

8 marks

Mark scheme: 5 PROCEDURE Sort() 8 DECLARE Temp : INTEGER DECLARE NoSwaps : BOOLEAN DECLARE Boundary, Row, Col : INTEGER Boundary ← 999 REPEAT NoSwaps ← TRUE FOR Row ← 1 TO Boundary IF Result[Row, 2] > Result[Row + 1, 2] THEN FOR Col ← 1 TO 2 Temp ← Result [Row, Col] Result [Row, Col] ← Result [Row + 1, Col] Result [Row + 1, Col] ← Temp NEXT Col NoSwaps ← FALSE ENDIF NEXT J Boundary ← Boundary - 1 UNTIL NoSwaps = TRUE ENDPROCEDURE Mark as follows: 1 Outer loop 2 Inner loop 3 Correct comparison in a loop 4 Correct swap of col1 array elements in a loop 5 Correct swap of col2 array elements in a loop (via loop or separate statements) 6 'NoSwap' mechanism: Conditional outer loop including flag reset 7 'NoSwap' mechanism: Set flag in inner loop to indicate swap 8 Reducing Boundary in the outer loop

This question in 9618/21 May/June 2021

4 A teacher uses a paper-based system to store marks for a class test. The teacher requires a program to assign grades based on these results. The program will output the grades together with the average mark. Write a detailed description of the algorithm that will be needed. … … … … … … … … … … … … … … … … … … … … … … … … [6]

6 marks

Mark scheme: 4 Marks awarded for a description of each of the following steps of the 6 algorithm: 1 Reference variables for Count of students and Total marks 2 Loop through all students (Count) 3 Input individual mark (in loop) 4 Compare mark with threshold / boundary values to determine grade (in loop) 5 Output the grade for a student (in loop) 6 Maintain a Total (and Count if required) (in loop) 7 Calculate average by dividing Total by Count and Output (after loop) Note: Max 6 marks

This question in 9618/22 May/June 2021

2 (a) Four program modules form part of a program for a library. A description of the relationship between the modules is summarised as follows: Module name Description UpdateLoan() • Calls either LoanExtend() or LoanReturn() • Called with parameters LoanID and BookID • Calls CheckReserve() to see whether the book has been LoanExtend() reserved for another library user • Returns TRUE if the loan has been extended, otherwise returns FALSE • Called with BookID CheckReserve() • Returns TRUE if the book has been reserved, otherwise returns FALSE • Called with parameters LoanID and BookID LoanReturn() • Returns a REAL (which is the value of the fine to be paid in the case of an overdue loan) Draw a structure chart to show the relationship between the four modules and the parameters passed between them. [5] (b) The definition for module LoanReturn() is amended as follows: Module name Description Called with parameters LoanID, BookID and Fine LoanReturn() The module code checks whether the book has been returned on time and then assigns a new value to Fine • LoanID and BookID are of type STRING • Fine is of type REAL Write the pseudocode header for the amended module LoanReturn(). … … [2] (c) A program will: • input 50 unique integer values • output the largest value • output the average of the values excluding the largest value. Draw a program flowchart to represent the algorithm. Variable declarations are not required. It is not necessary to check that each input value is unique. [6]

13 marks

Mark scheme: 2(a) 5 One mark for: 1 All four boxes correctly labelled and positioned 2 Selection diamond (only on UpdateLoan and no iteration arrows) 3 Parameters to and from LoanExtend() 4 Parameters to and from CheckReserve() 5 Parameters to and from LoanReturn() 2(b) PROCEDURE LoanReturn (LoanID, BookID : STRING, 2 BYREF Fine : REAL) One mark for each underlined part 2(c) Example solution: 6 One mark for each functional group as listed below: 2(c) Explanation of mark points: 1 Initialise MAX to first value input 2 Set Total to zero 3 Input 49 more values (or 50 values in total) 4 Sum all values input 5 Set new MAX when Input value > MAX in a loop 6 Sum all but largest (or subtract MAX from total), calculate and output average

This question in 9618/23 May/June 2021

5 A global 2D array Result of type INTEGER is used to store a list of exam candidate numbers together with their marks. The array contains 2000 elements, organised as 1000 rows and 2 columns. Column 1 contains the candidate number and column 2 contains the mark for the corresponding candidate. All elements contain valid exam result data. A procedure Sort() is needed to sort Result into ascending order of mark using an efficient bubble sort algorithm. Write pseudocode for the procedure Sort(). … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … [8]

8 marks

Mark scheme: 5 PROCEDURE Sort() 8 DECLARE Temp : INTEGER DECLARE NoSwaps : BOOLEAN DECLARE Boundary, Row, Col : INTEGER Boundary ← 999 REPEAT NoSwaps ← TRUE FOR Row ← 1 TO Boundary IF Result[Row, 2] > Result[Row + 1, 2] THEN FOR Col ← 1 TO 2 Temp ← Result [Row, Col] Result [Row, Col] ← Result [Row + 1, Col] Result [Row + 1, Col] ← Temp NEXT Col NoSwaps ← FALSE ENDIF NEXT J Boundary ← Boundary - 1 UNTIL NoSwaps = TRUE ENDPROCEDURE Mark as follows: 1 Outer loop 2 Inner loop 3 Correct comparison in a loop 4 Correct swap of col1 array elements in a loop 5 Correct swap of col2 array elements in a loop (via loop or separate statements) 6 'NoSwap' mechanism: Conditional outer loop including flag reset 7 'NoSwap' mechanism: Set flag in inner loop to indicate swap 8 Reducing Boundary in the outer loop

This question in 9618/23 May/June 2021

2 (a) An algorithm to sort a 1D array into ascending order is described as follows: • move the largest value to the end • keep repeating until the array is sorted. Apply the process of stepwise refinement to this algorithm in order to produce a more detailed description. Write the more detailed description using structured English. Your explanation of the algorithm should not include pseudocode statements. … … … … … … … … … … … … … … … … … … [6] (b) The program flowchart shown describes a simple algorithm. START Set Count to 1 Set Flag to FALSE Is Flag = YES FALSE AND Count <= 5 ? NO ReBoot() Set Count to Count + 1 Set Flag to Check() YES Is Flag = FALSE ? NO Alert(27) END Write pseudocode for the simple algorithm shown on page 6. … … … … … … … … … … … … … … … … [6]

12 marks

Mark scheme: 2(a) One mark for reference to: 6 1 The use a variable as an index to the array 2 A loop to iterate through the array 3 An Inner loop (with a reducing range) 4 Test if current element is greater than next element 5 if so then swap elements 6 Description of swap 7 Attempt at efficient algorithm Max 6 marks 2(b) Count ← 1 6 Flag ← FALSE WHILE Flag = FALSE AND Count <= 5 CALL ReBoot() Count ← Count + 1 Flag ← Check() ENDWHILE IF Flag = FALSE THEN CALL Alert(27) ENDIF One mark per point: 1 Initialisation of Count AND Flag 2 WHILE ... ENDWHILE // REPEAT ... UNTIL loop 3 ... including both conditions 4 Call ReBoot() AND increment Count inside the loop 5 Assign return value from Check() to Flag inside the loop 6 Final test of Flag AND call to Alert(27) not in a loop

This question in 9618/21 Oct/Nov 2021

3 A programmer is writing a program to help manage clubs in a school. Data will be stored about each student in the school and each student may join up to three clubs. The data will be held in a record structure of type Student. The programmer has started to define the fields that will be needed as shown in the following table. Field Typical value Comment StudentID "CF1234" Unique to each student Email "Carmen47@xyzmail.com" Contains letters, numbers and certain symbols Club_1 1 Any value in the range 1 to 99 inclusive Club_2 14 Any value in the range 1 to 99 inclusive Club_3 27 Any value in the range 1 to 99 inclusive (a) (i) Write pseudocode to declare the record structure for type Student. … … … … … … … [3] (ii) A 1D array Membership containing 3000 elements will be used to store the student data. Write pseudocode to declare the Membership array. … … [2] (iii) Some of the elements of the array will be unused. Give an appropriate way of indicating an unused array element. … … [1] (iv) Some students are members of less than three clubs. State one way of indicating an unused club field. … … [1] (b) A procedure GetIDs() will: • prompt and input the number of a club • output the StudentID of all the students who are members of that club • output a count of all students in the given club. Write pseudocode for the procedure GetIDs(). … … … … … … … … … … … … … … … … … … … … … … … … … [7]

14 marks

Mark scheme: 3(a)(i) Pseudocode: 3 TYPE Student DECLARE StudentID : STRING DECLARE Email : STRING DECLARE Club_1 : INTEGER DECLARE Club_2 : INTEGER DECLARE Club_3 : INTEGER ENDTYPE Mark as follows: • One mark for TYPE and ENDTYPE • One mark for StudentID and Email fields as STRING • One mark for all Club fields as INTEGER 3(a)(ii) DECLARE Membership : ARRAY [1:3000] OF Student 2 One mark per underlined phrase 3(a)(iii) One mark for any one of: 1 • Assign a value (of the corrrect data type) outside the normal range to one of the fields • Assign an empty string to the StudentID field / Email field • or value out of range to any club field 3(a)(iv) A number outside the range 1 to 99 1 3(b) PROCEDURE GetIDs() 7 DECLARE Index : INTEGER DECLARE ThisClub, Count : INTEGER OUTPUT "Please Input Club Number: " INPUT ThisClub Count ← 0 FOR Index ← 1 TO 3000 IF Membership[Index].Club_1 = ThisClub OR __ Membership[Index].Club_2 = ThisClub OR __ Membership[Index].Club_3 = ThisClub THEN Count ← Count + 1 OUTPUT Membership[Index].StudentID ENDIF NEXT Index OUTPUT "There are ", Count, " Students in the club" ENDPROCEDURE Mark as follows: 1 Declare and initialise Count 2 Prompt and Input club number before the loop 3 Loop through 3000 elements 4 Compare one club field with number input 5 Compare all Club fields with number input 6 If number found, OUTPUT of StudentID field and increment Count 7 Final OUTPUT of Count outside the loop Note: Max 6 if procedure heading and ending missing or incorrect (but allow array as parameter)

This question in 9618/22 Oct/Nov 2021

2 (a) An algorithm to sort a 1D array into ascending order is described as follows: • move the largest value to the end • keep repeating until the array is sorted. Apply the process of stepwise refinement to this algorithm in order to produce a more detailed description. Write the more detailed description using structured English. Your explanation of the algorithm should not include pseudocode statements. … … … … … … … … … … … … … … … … … … [6] (b) The program flowchart shown describes a simple algorithm. START Set Count to 1 Set Flag to FALSE Is Flag = YES FALSE AND Count <= 5 ? NO ReBoot() Set Count to Count + 1 Set Flag to Check() YES Is Flag = FALSE ? NO Alert(27) END Write pseudocode for the simple algorithm shown on page 6. … … … … … … … … … … … … … … … … [6]

12 marks

Mark scheme: 2(a) One mark for reference to: 6 1 The use a variable as an index to the array 2 A loop to iterate through the array 3 An Inner loop (with a reducing range) 4 Test if current element is greater than next element 5 if so then swap elements 6 Description of swap 7 Attempt at efficient algorithm Max 6 marks 2(b) Count ← 1 6 Flag ← FALSE WHILE Flag = FALSE AND Count <= 5 CALL ReBoot() Count ← Count + 1 Flag ← Check() ENDWHILE IF Flag = FALSE THEN CALL Alert(27) ENDIF One mark per point: 1 Initialisation of Count AND Flag 2 WHILE ... ENDWHILE // REPEAT ... UNTIL loop 3 ... including both conditions 4 Call ReBoot() AND increment Count inside the loop 5 Assign return value from Check() to Flag inside the loop 6 Final test of Flag AND call to Alert(27) not in a loop

This question in 9618/23 Oct/Nov 2021

7 A string is a palindrome if it reads the same forwards as backwards. The following strings are examples of palindromes: "Racecar" "madam" "12344321" Upper-case and lower-case characters need to be treated the same. For example, 'A' is equivalent to 'a'. (a) A function IsPalindrome() will take a string parameter. The function will return TRUE if the string is a palindrome and will return FALSE if the string is not a palindrome. Write pseudocode for IsPalindrome(). … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … [7] (b) Strings may consist of several words separated by spaces. For example, the string "never odd or even" becomes a palindrome if the spaces are removed. The program flowchart represents an algorithm to produce a string OutString by removing all spaces from a string InString. START Set Index to 1 A NO B E YES F C G D END Complete the table by writing the text that should replace each of the labels B, C, D, F and G. Note: the text may be written as a pseudocode statement. Label Text A Set OutString to "" B C D E Set Index to Index + 1 F G [4]

11 marks

Mark scheme: 7(a) FUNCTION IsPalindrome(InString : STRING) RETURNS BOOLEAN 7 DECLARE IsPal : BOOLEAN DECLARE Index, Num : INTEGER DECLARE CharA, CharB : CHAR IsPal  TRUE Index  1 Num  INT(LENGTH(InString) / 2) WHILE Index <= Num AND IsPal = TRUE CharA  MID(InString, Index, 1) CharB  MID(Instring, LENGTH(Instring) – Index + 1, 1) IF UCASE(CharA) <> UCASE(CharB) THEN IsPal  FALSE // RETURN FALSE ENDIF Index  Index + 1 ENDWHILE RETURN IsPal // RETURN TRUE ENDFUNCTION Mark as follows: 1 Functions header including parameter, ending and return type 2 Calculation of number of pairs to match (length or half length) 3 Loop for half or whole string 4 …Extracting characters to compare // create reverse string 5 Convert characters to same case 6 Check for mismatch of characters inside loop / test for mismatch after loop for reversed string 7 Returning Boolean in both cases 7(b) 4 Label Text A Set OutString to "" B Is Index > LENGTH(InString)? C Is MID(InString, Index, 1) = " "? Set OutString to OutString & MID(InString, Index, D 1) E Set Index to Index + 1 F YES G NO Mark for each of:  B  D  C  ...F and G Note: The mark for F and G is dependent on a reasonable attempt at C

This question in 9618/21 May/June 2022

8 A program allows a user to save passwords used to log in to websites. A stored password is then inserted automatically when the user logs in to the corresponding website. A global 2D array Secret of type STRING stores the passwords together with the website domain name where they are used. Secret contains 1000 elements organised as 500 rows by 2 columns. Unused elements contain the empty string (""). These may occur anywhere in the array. An example of a part of the array is: Array element Value Secret[27, 1] "thiswebsite.com" Secret[27, 2] Secret[28, 1] "thatwebsite.com" Secret[28, 2] Note: • For security, the passwords are stored in an encrypted form, shown as "" in the example. • The passwords cannot be used without being decrypted. • You may assume that the encrypted form of a password will NOT be an empty string. The programmer has started to define program modules as follows: Module Description • Takes two parameters: ○ a string ○ a character Exists() • Performs a case-sensitive search for the character in the string • Returns TRUE if the character occurs in the string, otherwise returns FALSE • Takes a password as a parameter of type string Encrypt() • Returns the encrypted form of the password as a string • Takes an encrypted password as a parameter of type string Decrypt() • Returns the decrypted form of the password as a string Note: in a case-sensitive comparison, 'a' is not the same as 'A'. (a) Write pseudocode for the module Exists(). … … … … … … … … … … … … … … … … … … … … [5] (b) A new module SearchDuplicates() will: • search for the first password that occurs more than once in the array and output a message each time a duplicate is found. For example, if the same password was used for the three websites ThisWebsite.com, website27.net and websiteZ99.org, then the following messages will be output: "Password for ThisWebsite.com also used for website27.net" "Password for ThisWebsite.com also used for websiteZ99.org" • end once all messages have been output. The module will output a message if no duplicates are found. For example: "No duplicate passwords found" Write efficient pseudocode for the module SearchDuplicates(). Encrypt() and Decrypt() functions have been written. Note: It is necessary to decrypt each password before checking its value. … … … … … … … … … … … … … … … … …

5 marks

Mark scheme: 8(a) FUNCTION Exists(ThisString : STRING, Search : CHAR) 5 RETURNS BOOLEAN DECLARE Found : BOOLEAN DECLARE Index : INTEGER Found  FALSE Index  1 WHILE Found = FALSE AND Index <= LENGTH(ThisString) IF MID(ThisString, Index, 1) = Search THEN Found  TRUE ELSE Index  Index + 1 ENDIF ENDWHILE RETURN Found ENDFUNCTION Marks as follows (Conditional loop solution): 1 Conditional loop while character not found and not end of string 2 Extract a char in a loop 3 Compare with parameter without case conversion in a loop 4 If match found, set termination logic in a loop 5 Return BOOLEAN value ALTERNATIVE (Using Count-controlled loop): FOR Index  1 TO LENGTH(ThisString) IF MID(ThisString, Index, 1) = Search THEN RETURN TRUE ENDIF NEXT Index RETURN FALSE Marks as follows (Count-controlled loop variant): 1 Loop for length of ThisString (allow from 0 or 1) 2 Extract a char in a loop 3 Compare with parameter without case conversion in a loop 4 If match found, immediate RETURN of TRUE 5 Return FALSE after the loop // Return Boolean if no immediate RETURN 8(b) PROCEDURE SearchDuplicates() 8 DECLARE IndexA, IndexB : INTEGER DECLARE ThisPassword, ThisValue : STRING DECLARE Duplicates : BOOLEAN Duplicates  FALSE IndexA  1 WHILE Duplicates = FALSE AND IndexA < 500 ThisValue  Secret[IndexA, 2] IF ThisValue <> "" THEN ThisPassword  Decrypt(ThisValue) FOR IndexB  IndexA + 1 TO 500 // IF Secret[IndexB, 2] <> "" THEN IF Decrypt(Secret[IndexB, 2]) = ThisPassword THEN OUTPUT "Password for " & Secret[IndexA, 1] & "also used for " & Secret[IndexB, 1] Duplicates  TRUE ENDIF ENDIF NEXT IndexB ENDIF IndexA  IndexA + 1 ENDWHILE IF Duplicates = FALSE THEN OUTPUT "No duplicate passwords found" ENDIF ENDPROCEDURE Marks as follows to Max 8: 1. (Any) conditional loop... 2. ... from 1 to 499 while (attempt at) no duplicate 3. Skip unused password 4. Use Decrypt() and assign return value to ThisPassword 5. Inner loop from outer loop index + 1 to 500 searching for duplicates 6. Compare ThisPassword with subsequent passwords (after use of Decrypt()) 7. If match found, set outer loop termination 8. and attempt an Output message giving duplicate 9. Output 'No duplicate passwords found' message if no duplicates found after the loop 8(c) One mark for each point that is referenced: 6 1 Initialise password to empty string at the start and return (attempted) password at the end of the function 2 Two loops to generate 3 groups of 4 characters // One loop to generate 12 / 14 characters 3 Use of RandomChar()to generate a character in a loop 4 Reject character if Exists()returns TRUE, otherwise form string in a loop 5 (Attempt to) use hyphens to link three groups 6 Three groups of four characters generated correctly with hyphens and without duplication (completely working algorithm)

This question in 9618/22 May/June 2022

7 The following pseudocode represents an algorithm intended to output the last three lines as they appear in a text file. Line numbers are provided for reference only. 10 PROCEDURE LastLines(ThisFile : STRING) 11 DECLARE ThisLine : STRING 12 DECLARE Buffer : ARRAY[1:3] OF STRING 13 DECLARE LineNum : INTEGER 14 LineNum 1 15 OPENFILE ThisFile FOR READ 16 17 WHILE NOT EOF(ThisFile) 18 READFILE Thisfile, ThisLine // read a line 19 Buffer[LineNum] ThisLine 20 LineNum LineNum + 1 21 IF LineNum = 4 THEN 22 LineNum 1 23 ENDIF 24 ENDWHILE 25 26 CLOSEFILE ThisFile 27 FOR LineNum 1 TO 3 28 OUTPUT Buffer[LineNum] 29 NEXT LineNum 30 ENDPROCEDURE (a) There is an error in the algorithm. In certain cases, a text file will have at least three lines but the output will be incorrect. (i) State how the output may be incorrect. … … [1] (ii) Describe the error in the algorithm and explain how it may be corrected. Description … … … … Explanation … … … … [4] (b) The original algorithm is implemented and sometimes the last three lines of the text file are output correctly. State the condition that results in the correct output. … … [1] (c) Lines 20 to 23 inclusive could be replaced with a single pseudocode statement. Write the pseudocode statement. … … [2]

8 marks

Mark scheme: 7(a)(i) The lines are output in an incorrect sequence / in the wrong order / not as 1 they appear in the file 7(a)(ii) Description of error: (Max 2 marks) 4  If the final line of the file is not written into array element 3  then outputting the elements in the sequence 1 to 3 will give the error. Explanation of error correction: (Max 2 marks)  Attempt at description of 'shuffle'  Copy Buffer[2] to Buffer[1] AND copy Buffer[3] to Buffer[2]  Read a line from the file and write it to Buffer[3] OR  Store the index of the last element written to buffer (the last line of the file)  Replace the FOR loop with something that starts at index  and then wraps around (MOD 3) OR (two-loop solution, not using an array)  Loop to read file to end to get number of lines  close and re-open file  read (and discard) lines to number of lines - 3, then loop to read and output last 3 lines 7(b) If the number of lines in the text file is a multiple of three 1 7(c) Correct answers include: 2 LineNum  (LineNum MOD 3) + 1 // ((LineNum + 3) MOD 3) + 1 One mark for assignment to LineNum making any use of MOD One for completely correct statement

This question in 9618/23 May/June 2022

3 A 1D array Data of type integer contains 200 elements. Each element has a unique value. An algorithm is required to search for the largest value and output it. Describe the steps that the algorithm should perform. Do not include pseudocode statements in your answer. … … … … … … … … … … … … [5]

5 marks

Mark scheme: 3 One mark per point (Max 5): 5 1 Declare a variable / an integer Max 2 Assign value of first / any element to Max 3 Set up a loop to repeat 200 times / from start to end of array 4 Use the loop counter as the array index 5 If value of current element is greater than Max... 6 ...then assign value to Max 7 After the loop, Output Max

This question in 9618/21 Oct/Nov 2022

6 (a) The factorial of an integer number is the product of all the integers from that number down to 1. In general, the factorial of n is n × (n−1) × ... × 2 × 1 For example, the factorial of 5 is 5 × 4 × 3 × 2 × 1 = 120 In this question, n will be referred to as the BaseNumber. A function FindBaseNumber() will: • be called with a positive, non-zero integer value as a parameter • return BaseNumber if the parameter value is the factorial of the BaseNumber • return −1 if the parameter value is not a factorial. For example: Parameter value Value returned 120 5 12 −1 6 3 1 1 FindBaseNumber(12) will return −1 because 12 is not a factorial. You may use the rest of this page for rough working. Write pseudocode for the function FindBaseNumber(). … … … … … … … … … … … … … … … … … … … … … … … … … [7] (b) A program is written to allow a user to input a sequence of values to be checked using the function FindBaseNumber(). The user will input one value at a time. The variable used to store the user input has to be of type string because the user will input ‘End’ to end the program. Valid input will be converted to an integer and passed to FindBaseNumber() and the return value will be output. Complete the table by giving four invalid strings that may be used to test distinct aspects of the required validation. Give the reason for your choice in each case. Input Reason for choice … … … … … … … … … … … … [4]

11 marks

Mark scheme: 6(a) Example by repeated multiplication: 7 Mark as follows (multiplication solution), (Max 7): 1 Function heading and ending including parameter and return type 2 Declaration and initialisation of local Num 3 Any conditional loop 4 Conditional loop until ThisValue found or Try out of range 5 Multiply Try by Num in a loop 6 Compare Try with ThisValue and set termination if the same in a loop 7 Increment Num and repeat in a loop 8 Attempt to Return Num if ThisValue is a factorial or -1 otherwise FUNCTION FindBaseNumber(ThisValue : INTEGER) RETURNS INTEGER DECLARE Num, Try : INTEGER DECLARE Found : BOOLEAN Num  0 Found  FALSE Try  1 WHILE Try <= ThisValue AND Found = FALSE Num  Num + 1 Try  Try * Num IF Try = ThisValue THEN //BaseNumber found Found  TRUE ENDIF ENDWHILE IF Found = TRUE THEN RETURN Num ELSE RETURN -1 ENDIF ENDFUNCTION 6(a) Alternative FOR LOOP solution. Mark as follows: 1 Function heading and ending including parameter and return type 2 Declaration of local Integer value for Num and Try 3 Count-controlled Loop from 1 to ThisValue 4 Multiply Try by Num in a loop 5 Compare Try with ThisValue in a loop 6 ...Immediate return of Num if they are the same in a loop 7 Return –1 if ThisValue not found after loop FUNCTION FindBaseNumber(ThisValue : INTEGER) RETURNS INTEGER DECLARE Num, Try : INTEGER Try  1 FOR Num  1 TO ThisValue Try  Try * Num IF Try = ThisValue THEN //BaseNumber found RETURN Num ENDIF NEXT Num RETURN -1 ENDFUNCTION 6(b) One mark per row. 4 Examples of invalid strings: 1 Non-numeric but not "End" // contains space or other non-numeric characters 2 Real number 3 Integer value out of range (i.e. <= 0) 4 Empty string 5 Correct word but wrong case e.g. "end" rather than "End" Input Reason for choice "Aardvark" Non-numeric (and not "End") "27.3" Numeric but not an integer "-3" // "0" A non-positive integer "" An empty string

This question in 9618/22 Oct/Nov 2022

7 A teacher is designing a program to perform simple syntax checks on programs written by students. Two global 1D arrays are used to store the syntax error data. Both arrays contain 500 elements. • Array ErrCode contains integer values that represent an error number in the range 1 to 800. • Array ErrText contains string values that represent an error description. The following diagram shows an example of the arrays. Index ErrCode ErrText 1 10 "Invalid identifier name" 2 20 "Bracket mismatch" 3 50 "Undeclared variable" 4 60 "Type mismatch in assignment" … 500 999 <Undefined> Note: • There may be less than 500 error numbers so corresponding elements in both arrays may be unused. Unused elements in ErrCode have the value 999. The value of unused elements in ErrText is undefined. • Values in the ErrCode array are stored in ascending order but not all values may be present, for example, there may be no error code 31. The teacher has defined two program modules as follows: Module Description • takes two parameters as integers: ○ a line number in the student’s program ○ an error number • searches for the error number in the ErrCode array: OutputError() ○ if found, outputs the corresponding error description and the line number, for example: "Bracket mismatch on line 34" ○ if not found, outputs the line number and a warning, for example: "Unknown error on line 34" SortArrays() sorts the arrays into ascending order of ErrCode (a) Write efficient pseudocode for module OutputError(). … … … … … … … … … … … … … … … … [6] (b) Write an efficient bubble sort algorithm in pseudocode for module SortArrays(). … … … … … … … … … … … … … … … … … … … … … … … … … … … [8]

14 marks

Mark scheme: 7(a) One mark per point (Max 6): 6 1 Procedure heading and ending including parameters 2 Conditional loop containing incrementing Index... 3 ...terminating when ErrNum found 4 ...terminating when ErrCode[Index] > ErrNum (i.e. ErrNum not found) 5 ... OR after element 500 tested 6 Test if found and OUTPUT 'Found' message 7 ...otherwise OUTPUT 'Not Found' message PROCEDURE OutputError(LineNum, ErrNum : INTEGER) DECLARE Index : INTEGER Index  0 // Search until ErrNum found OR not present OR end of array REPEAT Index  Index + 1 UNTIL ErrCode[Index] >= ErrNum OR Index = 500 IF ErrCode[Index] = ErrNum THEN OUTPUT ErrText[Index], " on line ", LineNum //Found ELSE OUTPUT "Unknown error on line ", LineNum //Not found ENDIF ENDPROCEURE 7(b) One mark per point (Max 8): 8 1 Procedure heading and ending as shown 2 Conditional loop correctly terminated 3 An inner loop 4 Correct range for inner loop 5 Comparison (element J with J+1) in a loop 6 Swap elements in both arrays in a loop 7 'No-Swap' mechanism: • Conditional outer loop including flag reset • Flag set in inner loop to indicate swap 8 Efficiency (this scenario): terminate inner loop when ErrCode = 999 9 Reducing Boundary in the outer loop PROCEDURE SortArrays() DECLARE TempInt, J, Boundary : INTEGER DECLARE TempStr : STRING DECLARE NoSwaps : BOOLEAN Boundary  499 REPEAT NoSwaps  TRUE FOR J  1 TO Boundary IF ErrCode[J]> ErrCode[J+1] THEN //first swap ErrCode elements TempInt  ErrCode[J] ErrCode[J]  ErrCode[J+1] ErrCode[J+1]  TempInt //now swap corresponding ErrText elements TempStr  ErrText[J] ErrText[J]  ErrText[J+1] ErrText[J+1]  TempStr NoSwaps  FALSE ENDIF NEXT J Boundary  Boundary - 1 UNTIL NoSwaps = TRUE ENDPROCEDURE 7(c)(i) ErrCode should be an INTEGER // ErrCode should not be a STRING 1 7(c)(ii) Benefits include: 2 1 Array of records can store mixed data types / multiple data types under a single identifer 2 Tighter / closer association between ErrCode and ErrText // simpler code as fields may be referenced together // values cannot get out of step as with two arrays 3 Program easier to design / write / debug / test / maintain / understand One mark per point Note: Max 2 marks 7(c)(iii) DECLARE Error : ARRAY[1:500] OF ErrorRec 1

This question in 9618/22 Oct/Nov 2022

3 A program stores data in a text file. When data is read from the file, it is placed in a queue. (a) The diagram below represents an Abstract Data Type (ADT) implementation of the queue. Each data item is stored in a separate location in the data structure. During initial design, the queue is limited to holding a maximum of 10 data items. The operation of this queue may be summarised as follows: • The Front of Queue Pointer points to the next data item to be removed. • The End of Queue Pointer points to the last data item added. • The queue is circular so that locations can be reused. 0 1 2 3 4 5 Red Front of Queue Pointer 6 Green 7 Blue 8 Pink End of Queue Pointer 9 (i) Describe how the data items Orange and Yellow are added to the queue shown in the diagram. … … … … … … … … [4] (ii) The following diagram shows the state of the queue after several operations have been performed. All queue locations have been used at least once. 0 D4 1 D3 End of Queue Pointer 2 D27 3 D8 4 D33 5 D17 Front of Queue Pointer 6 D2 7 D1 8 D45 9 D60 State the number of data items in the queue. … [1] (b) The design of the queue is completed and the number of locations is increased. A function AddToQueue() has been written. It takes a string as a parameter and adds this to the queue. The function will return TRUE if the string was added successfully. A procedure FileToQueue() will add each line from the file to the queue. This procedure will end when all lines have been added or when the queue is full. Describe the algorithm for procedure FileToQueue(). Do not use pseudocode in your answer. … … … … … … … … … … … [5]

10 marks

Mark scheme: 3(a)(i) One mark per point: 4 1 Check that the queue is not full 2 EoQ pointer will move to point to location 9 3 Data item Orange will be stored in location referenced by EoQ pointer 4 EoQ pointer will move to point to location 0 5 Data item Yellow will be stored in location referenced by EoQ pointer Note: max 4 marks 3(a)(ii) 7 1 3(b) One mark per bullet: 5 1 Open file in READ mode 2 Loop to EOF()// read / process all the lines in file 3 Loop will end when return value from AddToQueue() is FALSE / queue is full 4 Read a line from the file in a loop 5 Pass string to AddToQueue()// AddToQueue()is executed with line as parameter

This question in 9618/22 May/June 2023