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

This document consists of 16 printed pages. DC (KN/SW) 115643 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 4 0 9 5 2 0 9 1 3 2 * COMPUTER SCIENCE 9608/43 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/43/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 5 B Produce program design 5 C Write module code 15 D Module testing 10 E Integration testing 5 F Alpha testing 3 G Install software and acceptance testing 5 H Write end user training guide 5 J Write technical documentation 10 K End user training 4 L Sign off final system 1 (a) The project manager decides to construct a Program Evaluation Review Technique (PERT) chart from this data. 10 4 8 1 2 3 5 6 7 3 F 5 A 10 J 9 (i) Complete the PERT chart. [7] (ii) State the critical path. …[2] (iii) Calculate the minimum number of weeks for the completion of this solution. …[1]

3 9608/43/O/N/15 © UCLES 2015 [Turn over (b) For activity J: (i) State the earliest start time. Week number …[1] (ii) State the latest start time. Week number …[1] (c) Give a reason why the project manager used a PERT chart. … …[1]

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

5 9608/43/O/N/15 © UCLES 2015 [Turn over (c) Use the variable F to write the goal to find the father of Ahmed. …[1] (d) Write the rule to show that X is the mother of Y. mother(X, Y) IF … … [2] (e) W is a grandparent of Z if W is a parent of one of Z’s parents. Complete the following rule: grandparent(W, Z) IF … … …[2] (f) Complete the rule to show that G is a grandfather of K. grandfather(G, K) IF … … …[2]

6 9608/43/O/N/15 © UCLES 2015 3 A lending library stocks two types of item for loan: books and CDs. All stock items have a title, the date the item was acquired and whether the item is currently out on loan. Books have an author and ISBN. CDs have an artist and play time in minutes. The library needs a program to process data about the stock items. The program will use an object-oriented programming language. (a) Complete the class diagram showing the appropriate properties and methods. StockItem Title: STRING … … … ShowTitle() … … … Book CD Author: STRING … … … … … … … Constructor() ShowAuthor() … … … … … … [7]

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

8 9608/43/O/N/15 © UCLES 2015 (iii) to create a new instance of Book with: • identifier NewBook • title “Computers” • author A.Nyone • ISBN 099111 • acquired on 12/11/2001 • not out on loan Programming language … … … … … … … … …[3]

9 9608/43/O/N/15 © UCLES 2015 [Turn over Question 4 begins on page 10.

10 9608/43/O/N/15 © UCLES 2015 4 A binary tree Abstract Data Type (ADT) has these associated operations: • create the tree (CreateTree) • add an item to tree (Add) • output items in ascending order (TraverseTree) (a) Show the final state of the binary tree after the following operations are carried out. CreateTree Add("Dodi") Add("Farai") Add("Elli") Add("George") Add("Ben") Add("Celine") Add("Ali") [4]

11 9608/43/O/N/15 © UCLES 2015 [Turn over (b) The binary tree ADT is to be implemented as an array of nodes. Each node consists of data and two pointers. Using pseudocode, a record type, Node, is declared as follows: TYPE Node DECLARE Name : STRING DECLARE LeftPointer : INTEGER DECLARE RightPointer : INTEGER ENDTYPE The statement DECLARE Tree : ARRAY[1:10] OF Node reserves space for 10 nodes in array Tree. The CreateTree operation links all nodes into a linked list of free nodes. It also initialises the RootPointer and FreePointer. Show the contents of the Tree array and the values of the two pointers, RootPointer and FreePointer, after the operations given in part (a) have been carried out. Tree RootPointer Name LeftPointer RightPointer [1] [2] FreePointer [3] [4] [5] [6] [7] [8] [9] [10] [7]

12 9608/43/O/N/15 © UCLES 2015 (c) A programmer needs an algorithm for outputting items in ascending order. To design this, the programmer writes a recursive procedure in pseudocode. (i) Complete the pseudocode: 01 PROCEDURE TraverseTree(BYVALUE Root: INTEGER) 02 IF Tree[Root].LeftPointer … 03 THEN 04 TraverseTree( …) 05 ENDIF 06 OUTPUT …Name 07 IF … <> 0 08 THEN 09 TraverseTree( …) 10 ENDIF 11 ENDPROCEDURE [5] (ii) Explain what is meant by a recursive procedure. Give a line number from the code above that shows procedure TraverseTree is recursive. … … … Line number …[2] (iii) Write the pseudocode call required to output all names stored in Tree. … …[1]

13 9608/43/O/N/15 © UCLES 2015 [Turn over Question 5 begins on page 14.

14 9608/43/O/N/15 © UCLES 2015 5 Data about sports club members are stored in a random file of records. • The key field of a member record is the member ID (range 1000 to 9999). • Other member data are stored. • A hashing function is used to calculate a record address. • The random file initially consists of dummy records. • Dummy records are shown by member ID set to 0. FUNCTION Hash(MemberID : INTEGER) RETURNS INTEGER Address ← MemberID MOD 100 RETURN Address ENDFUNCTION (a) New members with the following member IDs have joined the sports club: 1001, 3005, 4096, 2098, 7002 Indicate where each record should be stored by deleting the zero and writing the member ID in the correct cell. MembershipFile Address MemberID Other member data 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 : : 96 0 97 0 98 0 99 0 [2]

15 9608/43/O/N/15 © UCLES 2015 [Turn over (b) (i) The program stores a new member’s data in the record variable NewMember. The field MemberID stores the member ID. Complete the pseudocode: 10 // generate record address 20 NewAddress ← … 30 // move pointer to the disk address for the record 40 SEEK … 50 PUTRECORD "MembershipFile", … [4] (ii) Before records can be saved to the file MembershipFile, the file needs to be opened. Complete the pseudocode. 01 TRY 02 OPENFILE … FOR RANDOM 03 EXCEPT 04 … 05 ENDTRY [2] (iii) A record with member ID 9001 is to be stored. Explain the problem that occurs when this record is saved. … … … …[2] (iv) Describe a method, without changing the function Hash, to handle the problem identified in part (b)(iii). … … … …[2]

16 9608/43/O/N/15 © UCLES 2015 (v) Write pseudocode to implement the method you described in part (b)(iv). Choose line numbers to indicate where your pseudocode should be inserted in the pseudocode of part (b)(i). … … … … … … … … … … … …[4] 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 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/43 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 43 © Cambridge International Examinations 2015 1 (a) (i) A F 5 B C E G 5 15 5 5 3 [max. 7] (ii) 1 – 2 – 3 – 5 – 6 – 7 – 9 – 8 – 10 1–5 scores 1 6–10 scores 1 [2] (iii) 43 weeks [1] (b) (i) week number 25 [1] (ii) week number 32 [1] (c) To see what activities can be done in parallel // show dependencies To record changes to project timings [max. 1]

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 2 (a) parent(philippe, meena). parent(gina, meena). [2] (b) ahmed, aisha, raul [2] (c) father(F, ahmed). [1] (d) mother(X, Y) IF female(X) AND parent(X, Y). [2] (e) grandparent(W, Z) IF parent(W,X) AND parent(X,Z). [2] (f) grandfather(G, K) IF male(G) AND grandparent(G, K). alternative: father(G, X) AND parent(X, K). [2]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 3 (a) StockItem Title: STRING DateAcquired : TDATETIME……………………… OnLoan: BOOLEAN .……………………………………… ……………………………………………………………………………………… ShowTitle() ShowDateAcquired() …………………………………… ShowOnLoan() ………………………………………………… ……………………………………………………………………………………… Book CD Author: STRING ISBN: STRING………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… Artist: STRING …………………………………………… Playtime: INTEGER …………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… Constructor() ShowAuthor() ShowISBN()………………………………………………………… ……………………………………………………………………………………… Constructor()………………………………………………… ShowArtist() ………………………………………………… ShowPlayTime() …………………………………………… ……………………………………………………………………………………… [max. 7]

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 (b) (i) Mark as follows: Class header Methods Properties Pascal StockItem = CLASS PUBLIC Procedure ShowTitle(); Procedure ShowDateAcquired(); Procedure ShowOnLoan(); PRIVATE Title : STRING; DateAcquired : TDateTime; OnLoan : Boolean; END; Python class StockItem : def __int__(self) : self.__Title = "" self.__DateAquired = "" self.__OnLoan = False def ShowTitle() : pass def ShowDateAcquired() : pass def ShowOnLoan() : pass VB.NET Class StockItem Public Sub ShowTitle() End Sub Public Sub ShowDateAquired() End Sub Public Sub ShowOnLoan() End Sub Private Title As String Private DateAquired As Date End Class [3]

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 (ii) Mark as follows: Class header and showing superclass Methods Properties Pascal TYPE Book = CLASS (StockItem) PUBLIC Procedure ShowAuthor(); Procedure ShowISBN(); PRIVATE Author : STRING; ISBN : STRING; END; Python class Book(StockItem) : def __init__(self) : self.__Author = "" self.__ISBN = "" def ShowAuthor() : pass def ShowISBN() : pass VB.NET Class Book : Inherits StockItem Public Sub ShowAuthor() End Sub Public Sub ShowISBN() End Sub Private Author As String Private ISBN As String ‘ reject integer End Class [3]

Page 7 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 (iii) Pascal NewBook := Book.Create; 1 NewBook.Title := 'Computers'; NewBook.Author := 'A.Nyone'; NewBook.ISBN := '099111'; 1 NewBook.DateAcquired := '12/11/2001'; NewBook.OnLoan := FALSE 1 Python NewBook = Book() 1 NewBook.Title = "Computers" NewBook.Author = "A.Nyone" NewBook.ISBN = "099111" 1 NewBook.DateAcquired = "12/11/2001" NewBook.OnLoan = False 1 VB.NET Dim NewBook As Book = New Book() 1 NewBook.Title = "Computers" NewBook.Author = "A.Nyone" NewBook.ISBN = "099111" 1 NewBook.DateAcquired = #12/11/2001# NewBook.OnLoan = False 1 [3]

Page 8 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 4 (a) [4] (b) Tree RootPointer Name LeftPointer RightPointer 1 [1] Dodi 5 2 [2] Farai 3 4 FreePointer [3] Elli 0 0 8 [4] George 0 0 [5] Ben 7 6 [6] Celine 0 0 [7] Ali 0 0 [8] 9 0 [9] 10 0 [10] 0 0 [7]

Page 9 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 (c) (i) 01 PROCEDURE TraverseTree(BYVALUE Root : INTEGER) 02 IF Tree[Root].LeftPointer < > 0 03 THEN 04 TraverseTree(Tree[Root].LeftPointer) 05 ENDIF 06 OUTPUT Tree[Root].Name 07 IF Tree[Root].RightPointer < > 0 08 THEN 09 TraverseTree(Tree[Root].RightPointer) 10 ENDIF 11 ENDPROCEDURE [5] (ii) A procedure that calls itself // is defined in terms of itself Line number: 04/09 [2] (iii) TraverseTree(RootPointer) [1] 5 (a) MembershipFile Address MemberID other member data 0 0 1 1001 2 7002 3 0 4 0 5 3005 6 0 7 0 8 0 : : : : 96 4096 97 0 98 2098 99 0 1001 and 7002 and 3005 1 4096 and 2098 1 [2]

Page 10 Mark Scheme Syllabus Paper Cambridge International A Level – October/November 2015 9608 43 © Cambridge International Examinations 2015 (b) (i) 10 // generate record address 20 NewAddress
Hash(NewMember.MemberID) 30 // move pointer to the disk address for the record 40 SEEK NewAddress 50 PUTRECORD "MembershipFile", NewMember [4] (ii) 01 TRY 02 OPENFILE "MembershipFile" FOR RANDOM 03 EXCEPT 04 OUTPUT "File does not exist" 05 ENDTRY [2] (iii) collisions/synonyms The previous record will be overwritten [2] (iv) Create an overflow area The ‘home’ record has a pointer to others with the same key OR Store the overflow record at the next available address in sequence OR Re-design the hash function …. to generate a wider range of indexes // to create fewer collisions [2] (v) 41 GETRECORD "MembershipFile", CurrentRecord 42 WHILE CurrentRecord.MemberID <> 0 43 NewAddress
NewAdress + 1 44 IF NewAddress > 99 THEN NewAddress
0 45 SEEK NewAddress 46 GETRECORD "MembershipFile", CurrentRecord 47 ENDWHILE [max. 4]