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

This document consists of 15 printed pages and 1 blank page. DC (AC) 95228/3 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 9 9 1 0 9 5 5 7 2 3 * COMPUTER SCIENCE 9608/42 Paper 4 Further Problem-solving and Programming Skills October/November 2015 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/42/O/N/15 © UCLES 2015 Throughout the paper you will be asked to write either pseudocode or program code. Complete the statement to indicate which high-level programming language you will use. Programming language ……………………………………………….………….………….………….……… 1 A large software house has been asked to supply a computerised solution for a business. The project manager has drawn up a list of activities and their likely duration. Activity Description Weeks to complete A Write requirement specification 1 B Produce program design 1 C Write module code 7 D Module testing 2 E Integration testing 2 F Alpha testing 2 G Install software and carry out acceptance testing 2 H Research and order hardware 1 J Install delivered hardware 3 K Write technical documentation 4 L Write user training guide 2 M Train users on installed hardware and software 1 N Sign off final system 1 (a) From this data a GANTT chart is constructed. Activity A B C D E F G H J K L M N Week number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

3 9608/42/O/N/15 © UCLES 2015 [Turn over (i) Complete the GANTT chart by adding activities M and N. [2] (ii) State the earliest completion date. Week number … [1] (b) There are problems with the progress of the project: • Activity E showed that the code contained major errors. The senior programmer now estimates that: • further module coding will require another 2 weeks • further module testing will require another 2 weeks • further integration testing will require another 2 weeks • The hardware delivery is delayed by 16 weeks. A revised GANTT chart is now required. (i) Complete the chart in the grid below. Activity A B C D E F G H J K L M N Week number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 [9] (ii) State the new estimated completion date. Week number … [1]

4 9608/42/O/N/15 © UCLES 2015 2 A declarative programming language is used to represent the following facts and rules: 01 male(ahmed). 02 male(raul). 03 male(ali). 04 male(philippe). 05 female(aisha). 06 female(gina). 07 female(meena). 08 parent(ahmed, raul). 09 parent(aisha, raul). 10 parent(ahmed, philippe). 11 parent(aisha, philippe). 12 parent(ahmed, gina). 13 parent(aisha, gina). 14 mother(A, B) IF female(A) AND parent(A, B). These clauses have the following meaning: Clause Explanation 01 Ahmed is male 05 Aisha is female 08 Ahmed is a parent of Raul 14 A is the mother of B if A is female and A is a parent of B (a) More facts are to be included. Ali and Meena are the parents of Ahmed. Write the additional clauses to record this. 15 … 16 … [2] (b) Using the variable C, the goal parent(ahmed, C) returns C = raul, philippe, gina Write the result returned by the goal parent(P, gina) P = … [2]

5 9608/42/O/N/15 © UCLES 2015 [Turn over (c) Use the variable M to write the goal to find the mother of Gina. … [1] (d) Write the rule to show that F is the father of C. father(F, C) IF … … [2] (e) Write the rule to show that X is a brother of Y. brother(X, Y) IF … … … … … [4]

6 9608/42/O/N/15 © UCLES 2015 3 A college has two types of student: full-time and part-time. All students have their name and date of birth recorded. A full-time student has their address and telephone number recorded. A part-time student attends one or more courses. A fee is charged for each course. The number of courses a part-time student attends is recorded, along with the total fee and whether or not the fee has been paid. The college needs a program to process data about its students. The program will use an object- oriented programming language. (a) Complete the class diagram showing the appropriate properties and methods. Student StudentName: STRING … … … ShowStudentName() … … … FullTimeStudent PartTimeStudent Address: STRING … … … … … … … Constructor() ShowAddress() … … … … … … [7]

7 9608/42/O/N/15 © UCLES 2015 [Turn over (b) Write program code: (i) for the class definition for the superclass Student. Programming language … … … … … … … … … [2] (ii) for the class definition for the subclass FullTimeStudent. Programming language … … … … … … … … … [3]

8 9608/42/O/N/15 © UCLES 2015 (iii) to create a new instance of FullTimeStudent with: • identifier: NewStudent • name: A. Nyone • date of birth: 12/11/1990 • telephone number: 099111 Programming language … … … … … … … [3] 4 A dictionary Abstract Data Type (ADT) has these associated operations: • Create dictionary (CreateDictionary) • Add key-value pair to dictionary (Add) • Delete key-value pair from dictionary (Delete) • Lookup value (Lookup) The dictionary ADT is to be implemented as a two-dimensional array. This stores key-value pairs. The pseudocode statement DECLARE Dictionary : Array[1:2000, 1:2] OF STRING reserves space for 2000 key-value pairs in array Dictionary. The CreateDictionary operation initialises all elements of Dictionary to the empty string. (a) The hashing function Hash is to extract the first letter of the key and return the position of this letter in the alphabet. For example Hash("Action") will return the integer value 1. (Note: The ASCII code for the letter A is 65.) Complete the pseudocode: FUNCTION Hash (…) RETURNS … DECLARE Number : INTEGER Number ← … … ENDFUNCTION [5]

9 9608/42/O/N/15 © UCLES 2015 [Turn over (b) The algorithm for adding a new key-value pair to the dictionary is written, using pseudocode, as a procedure. PROCEDURE Add(NewKey : STRING, NewValue : STRING) Index ← Hash(NewKey) Dictionary[Index, 1] ← NewKey // store the key Dictionary[Index, 2] ← NewValue // store the value ENDPROCEDURE An English-German dictionary of Computing terms is to be set up. (i) Dry-run the following procedure calls by writing the keys and values in the correct elements of Dictionary. Add("File", "Datei") Add("Disk", "Platte") Add("Error", "Fehler") Add("Computer", "Rechner") Dictionary Index Key Value 1 2 3 4 5 6 7 8 : : 1999 2000 [2] (ii) Another procedure call is made: Add("Drive", "Laufwerk") Explain the problem that occurs when this key-value pair is saved. … … … … [2]

10 9608/42/O/N/15 © UCLES 2015 (iii) Describe a method to handle the problem identified in part (b)(ii). … … … …[2] (iv) Write pseudocode to implement the method you described in part (b) (iii). Choose line numbers to indicate where your pseudocode should be inserted in the given pseudocode. 10 PROCEDURE Add(NewKey : STRING, NewValue : STRING) 20 Index ← Hash(NewKey) 30 Dictionary[Index, 1] ← NewKey // store the key 40 Dictionary[Index, 2] ← NewValue // store the value 50 ENDPROCEDURE … … … … … … … … … … [4]

11 9608/42/O/N/15 © UCLES 2015 [Turn over Question 5 begins on page 12.

12 9608/42/O/N/15 © UCLES 2015 5 The table shows assembly language instructions for a processor which has one general purpose register – the Accumulator (ACC). Instruction Explanation Op Code Operand LDM #n Immediate addressing. Load the number n to ACC LDD <address> Direct addressing. Load the contents of the given address to ACC STO <address> Store the contents of ACC at the given address ADD <address> Add the contents of the given address to the ACC INC <register> Add 1 to the contents of the register CMP <address> Compare the contents of ACC with the contents of <address> JPN <address> Following a compare instruction, jump to <address> if the compare was False END Return control to the operating system (a) (i) Dry-run this assembly language program using the trace table. 500 LDD 512 501 ADD 509 502 STO 512 503 LDD 511 504 INC ACC 505 STO 511 506 CMP 510 507 JPN 500 508 END 509 7 510 3 511 0 512 0

13 9608/42/O/N/15 © UCLES 2015 [Turn over Trace table Memory address Accumulator 509 510 511 512 7 3 0 0 [5] (ii) Explain the role address 511 has in this assembly language program. … … … … [2] (b) Using opcodes from the given table, write instructions to set the value at address 509 to 12. … … … … [2]

14 9608/42/O/N/15 © UCLES 2015 6 A company keeps details of its stock items in a file of records, StockFile. (a) The record fields are the ProductCode, the Price and the NumberInStock. Write the program code to declare the record structure StockItem. Programming language … … … … … … … … [4] (b) Before records can be read from file StockFile, the file needs to be opened. (i) Complete the pseudocode. 01 TRY 02 OPENFILE … 03 EXCEPT 04 … 05 ENDTRY [2] (ii) Explain the reason for including lines 01, 03, 04, 05. … … … … [2]

15 9608/42/O/N/15 © UCLES 2015 (c) A stock report program uses a variable of type StockItem declared as follows: DECLARE ThisStockItem : Stockitem The program reads each record in the file StockFile in turn. The program outputs the fields ProductCode and NumberInStock for each record. Write pseudocode for this. … … … … … … … … [4]

16 9608/42/O/N/15 © UCLES 2015 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. BLANK PAGE

® IGCSE is the registered trademark of Cambridge International Examinations. CAMBRIDGE INTERNATIONAL EXAMINATIONS Cambridge International Advanced Level MARK SCHEME for the October/November 2015 series 9608 COMPUTER SCIENCE 9608/42 Paper 4 (Written Paper), maximum raw mark 75 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 will not enter into discussions about these mark schemes. Cambridge is publishing the mark schemes for the October/November 2015 series for most Cambridge IGCSE®, Cambridge International A and AS Level components and some Cambridge O Level components.

Page 2 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 1 (a) (i) Activity A B C D E F G H J K L M N Week Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 mark for each square [2] (ii) week number 18 Allow follow through [1]

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (b) (i) Activity Description Weeks to complete A Write requirement specification 1 B Produce program design 1 C Write module code 7 D Module testing 2 E Integration testing 2 F Alpha testing 2 G Install software and carry out acceptance testing 2 H Research and order hardware 1 J Install delivered hardware 3 K Write technical documentation 4 L Write user training guide 2 M Train users on installed hardware and software 1 N Sign off final system 1 Activity A B C D E F G H J K L M N Week Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 mark per activity (but 1 mark for activity M and N) Notes: C must be after E (1 or 2 later is ok) D, E, F correct relative to C J must start in week 20 (allow 21, 22) G must come after the end of J (f.t.) K finishes after or at same time as F L finishes at the same time as G and after the end of J (or 1-2 weeks later) M starts when everything else has finished. N after or at same time as M [9] (ii) week number: 26 Allow f.t. [1]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 2 (a) parent(ali, ahmed). parent(meena, ahmed). Accept statements in either order Wrong capitalisation minus 1 mark [2] (b) P = ahmed aisha Ignore capitalisation Deduct 1 mark for every extra result [2] (c) mother(M, gina). Accept parent(M, gina) AND female(M). Accept a comma instead of AND Reject mother(M, gina) IF female(M) AND parent(M, gina). Ignore capitalisation [1] (d) father(F, C) IF male(F) AND parent(F, C). (1) (1) [2] (e) brother(X, Y) IF male(X)AND [1] parent(A, X) AND [1] parent(A, Y) [1] AND NOT X=Y. [1] Accept any variable for A, but it must be the same in both places Accept father/mother instead of parent Ignore capitalisation

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 3 (a) Student StudentName : STRING DateOfBirth : DATETIME ……………………………………………………………………………………… ShowStudentName() ShowDateOfBirth() ……………………………………………………………………………………… FullTimeStudent PartTimeStudent Address: STRING TelephoneNumber : STRING ……………………………………………………………………………………… NumberOfCourses : INTEGER Fee : Currency FeePaid : BOOLEAN Constructor() ShowAddress() ShowTelephoneNumber() ……………………………………………………………………………………… Constructor() ShowNumberOFCourses() ShowFee() ShowFeePaid() Mark as follows: Base class: – dateOfBirth declaration and associated method in Student – constructor Subclasses: – telephoneNumber declaration and associated method in FullTimeStudent – NumberOFCourses declaration and associated method in PartTimeStudent – fee declaration and associated method in PartTimeStudent – feepaid declaration and associated method in PartTimeStudent – constructor method in PartTimeStudent – inheritance arrows Ignore data types, ignore other methods/attributes Ignore brackets after methods [Max 7]

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (b) (i) Mark as follows (parts to be ignored in grey): If no programming language stated, map to 1 of the 3 below (or check in Q1ai) Class header & ending (watch out these may be squashed into the next clip) Ignore methods 2 attributes with correct data types No mark if subclass properties shown here Attributes required: StudentName DateOfBirth (accept variations e.g. DoB) Pascal TYPE Student = CLASS PUBLIC Procedure ShowStudentName(); Procedure ShowDateOfBirth(); PRIVATE StudentName : STRING; DateOfBirth : TDateTime; // accept string reject Date END; Python class Student : def __int__(self) : self.__StudentName = "" self.__DateOfBirth = "" # date(1,1,2015) def ShowStudentName() : pass def ShowDateOfBirth() : pass Ignore __ before attributes VB.NET Class Student Public Sub ShowStudentName() End Sub Public Sub ShowDateOfBirth() End Sub Private StudentName As String Private DateOfBirth As Date ‘ accept string End Class (Ignore: must inherit) Ignore Private/protected/public Don’t give a mark if using DIM [2]

Page 7 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (ii) Mark as follows: – Class header and showing superclass – Properties (Do not award this mark if properties from base class included here) Data types must be correct – Methods (Do not award this mark if methods from base class included here) must show heading and ending of procedure/function declaration Ignore PUBLIC, PRIVATE Pascal TYPE FullTimeStudent = CLASS (Student) PUBLIC Procedure ShowAddress(); Procedure ShowTelephoneNumber(); PRIVATE Address : STRING; TelephoneNumber : STRING; // reject integer END; Python class FullTimeStudent(Student) : def __init__(self) : self.__Address = "" self.__TelephoneNumber = "" def ShowAddress() : pass def ShowTelephoneNumber() : pass VB.NET Class FullTimeStudent : Inherits Student Public Sub ShowAddress() End Sub Public Sub ShowTelephoneNumber() End Sub Private Address As String Private TelephoneNumber As String ‘ reject integer End Class No mark if using DIM [3]

Page 8 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (iii) 1 mark per statement to max 3 Missing string delimiters: penalise once Accept use of constructor Pascal NewStudent := FullTimeStudent.Create; NewStudent.StudentName := 'A.Nyone'; NewStudent.DateOfBirth := EncodeDate(1990, 11,12);//:= ‘11/12/1990’ NewStudent.TelephoneNumber := '099111'; Alternative NewStudent := FullTimeStudent.Create(‘A.Nyone’, ‘12/11/1990’, ‘099111’); Python NewStudent = FullTimeStudent() NewStudent.StudentName = "A.Nyone" NewStudent.DateOfBirth = "12/11/1990" NewStudent.TelephoneNumber = "099111" Alternative NewStudent = FullTimeStudent(‘A.Nyone’, ‘12/11/1990’, ‘099111’) VB.NET Dim NewStudent As FullTimeStudent = New FullTimeStudent() NewStudent.StudentName = "A.Nyone" NewStudent.DateOfBirth = #11/12/1990# NewStudent.TelephoneNumber = "099111" Alternative Dim NewStudent As FullTimeStudent = New FullTimeStudent(“A.Nyone”, “12/11/1990”, “099111”) [Max 3]

Page 9 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 4 (a) FUNCTION Hash(Key : STRING) RETURNS INTEGER DECLARE Number : INTEGER Number
ASCII(LEFTSTRING(Key,1)) // Number
ASCII(Key[1]) Number
Number – 64 RETURN Number // Result
Number // Hash
Number ENDFUNCTION Accept ASC instead of ASCII Accept LEFT instead of LEFTSTRING Key can be a different identifier but must be the same in both places [5] (b) (i) Dictionary Index Key Value 1 2 3 Computer Rechner 4 Disk Platte 5 Error Fehler 6 File Datei 7 8 : : : : 1999 2000 Ignore spelling mistakes 1 mark for 2 correct pairs entered in correct slots [2] (ii) Collision / synonym / space already occupied / same index in array Overwrites previous key-value pair reject error [Max 2] (iii) Create an overflow area The 'home' record has a pointer to others with the same key // linked list OR Store the overflow record at the next available address … in sequence (= next available) OR Re-design the hash function …. // write a different/another algorithm to generate a wider range of indexes // enlarging storage space // to create fewer collisions [2]

Page 10 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (iv) Mark as follows: Check whether slot is empty: IF Dictionary[Index,1] <>”” // != ‘’ // > NULL // > NONE If not: update index: THEN Index
<some value> …to find an empty slot (loop / follow pointer / go to overflow area) reject FOR loop Insert code between lines 20 and 30 21 WHILE Dictionary[Index,1] > "" 22 Index
Index + 1 23 IF Index > 2000 24 THEN 25 Index
1 26 ENDIF 27 ENDWHILE [4] 5 (a) (i) Memory Address Accumulator 509 510 511 512 0 7 3 0 0 7 7 0 1 1 7 14 14 1 2 2 14 21 21 2 3 3 3 marks 1 mark 1 mark If values changed in column 509 or 510 don’t give marks for 511/512 [5] (ii) stores the counter value for ….// acts as a control variable/counter How many times the loop has been performed // control the loop Ignore re-stating the steps [2] (b) LDM #12 (must be instruction before storage) STO 509 (must be final instruction) 1 mark for each instruction [2]

Page 11 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 6 (a) 1 mark for structure header/ending 1 mark for each field correct, take away 1 mark for additional fields Python answers will use a class Pascal TYPE StockItem = RECORD ProductCode : String; // accept integer Price : Currency; // accept real NumberInStock : Integer; END; Python class StockItem : def __init__(self) : self.ProductCode = "" # = 0 self.Price = 0.0 # = 0 self.NumberInStock = 0 VB.NET STRUCTURE StockItem Dim ProductCode As String ‘ accept integer Dim Price As Decimal ‘ Double/single Dim NumberInStock As Integer END STRUCTURE VB6 Type StockItem ProductCode As String ‘ accept integer Price As Currency ‘ Double/single NumberInStock As Integer END Type [4]

Page 12 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 42 © Cambridge International Examinations 2015 (b) (i) 01 TRY 02 OPENFILE "StockFile" FOR READ/RANDOM // ignore “ 03 EXCEPT 04 OUTPUT "File does not exist" 05 ENDTRY [2] (ii) (Line 01) alerts system to check for possible run-time errors (exception) (Lines 03, 04) handle the exception without the program crashing // keeps program running// provide alternative statements to execute to avoid run-time error Accept “exception handling” for 1 mark [Max 2] (c) WHILE NOT EOF("StockFile") READFILE "StockFile", ThisStockItem // accept reading separate fields OUTPUT ThisStockItem.ProductCode OUTPUT ThisStockItem.NumberInStock ENDWHILE 1 mark for loop (accept REPEAT) 1 mark for EOF(“StockFile”) // StockFile.Peek <> -1 / NONE/’’ 1 mark for READ record 1 mark for OUTPUT of 2 fields Ignore opening and closing file [4]