ACJC H2 Computing 2023 Prelims

ANGLO-CHINESE JUNIOR COLLEGE JC2 PRELIMINARY EXAMINATION Higher 2 COMPUTING 9569/02 Paper 2 (Lab-based) 7 August 2023 3 hours Additional Materials: Electronic version of Task2.txt data file Electronic version of numbers.txt data file Electronic version of club.db data file Electronic version of DATA.txt data file Insert Quick Reference Guide READ THESE INSTRUCTIONS FIRST Answer all questions. All tasks must be done in the computer laboratory. You are not allowed to bring in or take out any pieces of work or materials on paper or electronic media or in any other form. Approved calculators are allowed. Save each task as it is completed. The use of built -in functions, where appropriate, is allowed for this paper unless stated otherwise. Note that up to 6 marks out of 100 will be awarded for the use of common coding standards for programming style. The number of marks is given in brackets [ ] at the end of each question or part question. The total number of marks for this paper is 100. __________________________________________________________________________________ This document consists of 11 printed pages and 1 blank page. [Turn Over

2 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/02 Instruction to candidates: Your program code and output for each of Tasks 1, 2 and 3 should be downloaded in a single .ipynb file. For example, your program code and output for Task 1 should be downloaded as TASK1_<your name>_<centre number>_<index number>.ipynb Make sure that each of your .ipynb files shows the required output in Jupyter Notebook. 1 Name your Jupyter Notebook as: TASK1_<your name>_<centre number>_<index number>.ipynb The task is to write addition and multiplication algorithms for large integers, assuming that the results of adding and multiplying single-digit integers have already been hard-coded. The addition algorithm described below is similar to what students learn in primary school. 1. Declare and initialise variables: • Create two string variables, s1 and s2, to store the numbers to be added; • The integer carry initially has a value of 0; • The string result initially is an empty string. 2. If s1 and s2 are of unequal length, pad the shorter string with '0's in front to make the two strings the same length. For example, if s1 is '1238' and s2 is '15', pad s2 so that s2 becomes '0015'. 3. Create a loop to iterate over both strings, starting from the largest index. For each cycle of the loop, perform the following steps. • Retrieve the digits of s1 and s2 at that index. Call them digit1 and digit2 respectively. • Define column_sum to be the numerical sum of digit1, digit2 and carry. • Concatenate the last (ones) digit of column_sum to the front of result. This is the new value of result. • The first (tens) digit of column_sum is the new value of carry. 4. If carry is larger than 0, concatenate carry to the front of result. This is the new value of result. 5. Return result. The Karatsuba algorithm is a recursive method of multiplying large (positive) integers efficiently. The recursive algorithm described below is a simplified version. The function karatsuba(s1,s2) takes two string variables, s1 and s2, which consist entirely of digits, and returns an integer. 1. If s1 and s2 are both of length 1, multiply them as single -digit numbers and return their product. 2. If s1 and s2 are of unequal length, pad the shorter string with '0's in front to make the two strings the same length . For example, if s1 is '1238' and s2 is '15', pad s2 so that s2 becomes '0015'.

3 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/02 [Turn Over 3. Define the following variables. • leng ← LENGTH(s1) • mid ← length DIV 2 • a ← LEFT(s1, leng – mid) • b ← RIGHT(s1, mid) • c ← LEFT(s2, leng – mid) • d ← RIGHT(s2, mid) 4. Use the karatsuba function recursively to find the following variables. • ac ← STRING(karatsuba(a,c)) • ad ← STRING(karatsuba(a,d)) • bc ← STRING(karatsuba(b,c)) • bd ← STRING(karatsuba(b,d)) 5. Perform the following concatenations. • (2 * mid) copies of '0' to the end of ac • mid copies of '0' to the end of ad • mid copies of '0' to the end of bc 6. Convert ac, ad, bc and bd to integers and add them. Return the sum. For each of the sub-tasks, add a comment statement at the beginning of the code, using the hash symbol ‘#’ to indicate the sub-task the program code belongs to, for example: In [1]: #Task 1.1 Program code Output: Task 1.1 Write program code to define addition(s1,s2) that implements the algorithm to sum two numbers represented as strings together. The function would return an integer. You do not need to perform data validation. For this sub-task, you are allowed to use the + operator only to add single-digit numbers together, and to concatenate strings. [5] Task 1.2 Test your code in Task 1.1 with the following test cases. • print(addition('12','34') == 46) • print(addition('1234','222') == 1456) • print(addition('999','1') == 1000) [2] Task 1.3 Write program code to define karatsuba(s1,s2). You do not need to perform data validation. For this sub-task, you are allowed to use the * operator only to multiply single-digit numbers together, and to concatenate multiple copies of strings. [7]

4 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/02 Task 1.4 Test your code in Task 1.3 with the following test cases. • print(karatsuba('15','20') == 300) • print(karatsuba('1234','22') == 27148) • print(karatsuba('999','222') == 221778) [2] Task 1.5 Write program code to: • Initialise a list lst1. • Randomly generate 50 integers in the range 1 to 100 (inclusive) and store them in lst1. • Find the sum of all the numbers in lst1 with the addition function from Task 1.1 and store the result as total_sum. Display total_sum. • Find the product of all the numbers in lst1 with the karatsuba function from Task 1.3 and store the result as total_prod. Display total_prod. For this sub-task, you are not allowed to use the + and * operators. [4] Save your Jupyter Notebook for Task 1.

5 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/02 [Turn Over 2 Name your Jupyter Notebook as: TASK2_<your name>_<centre number>_<index number>.ipynb The task is to use a circular queue to perform a breadth-first search through a binary tree , by following the algorithm in the flowchart below. This is done by using Object-Oriented Programming (OOP) to create a circular queue inside an Array, and to create the nodes for a binary tree data structure. ENQUEUE Root of Tree into Queue Node ← DEQUEUE from Queue YES NO START STOP INPUT Tree, Searchfor CREATE Queue Is Queue Empty? Is Node’s data equal to Searchfor? Does Node have a left child? Does Node have a right child? ENQUEUE left child of Node into Queue ENQUEUE right child of Node into Queue NO NO NO YES YES OUTPUT Not Found OUTPUT Found YES

6 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/02 For each of the sub-tasks, add a comment statement at the beginning of the code, using the hash symbol ‘#’ to indicate the sub-task the program code belongs to, for example: In [1]: #Task 2.1 Program code Output: Task 2.1 Define an Array class with the following properties: • capacity: an integer which gives the size of the array; • container: a list of length capacity which is initialised with all entries as None and the following methods: • add_data(new_data, i) replaces the entry in index i of container with new_data; • get_data(i) returns the entry in index i of container; • delete_data(i) replaces the entry in index i of container with None. [6] We use an array to hold a circular queue. The head pointer of the circular queue is the index of the first item of the circular queu