Cambridge A Level Computer Science 9608 — 2015 May/June Paper 4 · Variant 2

This document consists of 16 printed pages. DC (SLM) 108502 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 0 5 8 4 9 6 7 1 2 6 * COMPUTER SCIENCE 9608/42 Paper 4 Further Problem-solving and Programming Skills May/June 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/M/J/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 …

3 9608/42/M/J/15 © UCLES 2015 [Turn over 1 A turnstile is a gate which is in a locked state. To open it and pass through, a customer inserts a coin into a slot on the turnstile. The turnstile then unlocks and allows the customer to push the turnstile and pass through the gate. After the customer has passed through, the turnstile locks again. If a customer pushes the turnstile while it is in the locked state, it will remain locked until another coin is inserted. The turnstile has two possible states: locked and unlocked. The transition from one state to another is as shown in the table below. Current state Event Next state Locked Insert coin Unlocked Locked Push Locked Unlocked Attempt to insert coin Unlocked Unlocked Pass through Locked Complete the state transition diagram for the turnstile: … … … … … … start [5]

4 9608/42/M/J/15 © UCLES 2015 2 A declarative programming language is used to represent the knowledge base shown below: 01 capital_city(amman). 02 capital_city(beijing). 03 capital_city(brussels). 04 capital_city(cairo). 05 capital_city(london). 06 city_in_country(amman, jordan). 07 city_in_country(shanghai, china). 08 city_in_country(brussels, belgium). 09 city_in_country(london, uk). 10 city_in_country(manchester, uk). 11 country_in_continent(belgium, europe). 12 country_in_continent(china, asia). 13 country_in_continent(uk, europe). 14 city_visited(amman). 15 city_visited(beijing). 16 city_visited(cairo). These clauses have the following meaning: Clause Explanation 01 Amman is a capital city 06 Amman is a city in the country of Jordan 11 Belgium is a country in the continent of Europe 14 The travel writer visited Amman (a) More facts are to be included. The travel writer visited the city of Santiago which is the capital city of Chile, in the continent of South America. Write additional clauses to record this. 17 … … 18 … … 19 … … 20 … … [4]

5 9608/42/M/J/15 © UCLES 2015 [Turn over (b) Using the variable ThisCountry, the goal country_in_continent(ThisCountry, europe) returns ThisCountry = belgium, uk Write the result returned by the goal: city_in_country(ThisCity, uk) ThisCity = … … [2] (c) Complete the rule below to list the countries the travel writer has visited. countries_visited(ThisCountry) IF … … … … … [4]

6 9608/42/M/J/15 © UCLES 2015 3 A shop gives some customers a discount on goods totalling more than $20. The discounts are: • 5% for goods totalling more than $100 • 5% with a discount card • 10% with a discount card and goods totalling more than $100 (a) Complete the decision table. Conditions goods totalling more than $20 Y Y Y Y N N N N goods totalling more than $100 Y Y N N Y Y N N have discount card Y N Y N Y N Y N Actions No discount 5% discount 10% discount [4] (b) Simplify your solution by removing redundancies. Conditions goods totalling more than $20 goods totalling more than $100 have discount card Actions No discount 5% discount 10% discount [5]

7 9608/42/M/J/15 © UCLES 2015 [Turn over (c) The simplified table produced in part (b) is used as a design for program code. The following identifier table shows the parameters to be passed to the function Discount. This function returns the discount amount as an integer. Identifier Data type GoodsTotal INTEGER HasDiscountCard BOOLEAN Write program code for this function. Programming language … … … … … … … … … … … … … … … … … … … … … [6]

8 9608/42/M/J/15 © UCLES 2015 4 A payroll program is to be written using an object-oriented programming language. An Employee class is designed. Two subclasses have been identified: • HourlyPaidEmployee who is paid a monthly wage calculated from their hourly rate of pay and the number of hours worked during the month • SalariedEmployee who is paid a monthly wage which is one 12th of their annual salary (a) Draw an inheritance diagram for these classes. [3] (b) The design for the Employee class consists of: • properties • EmployeeName • EmployeeID • AmountPaidThisMonth • methods • SetEmployeeName • SetEmployeeID • CalculatePay Write program code for the class definition of the superclass Employee. Programming language … … … … … … … … … … … [5]

9 9608/42/M/J/15 © UCLES 2015 [Turn over (c) (i) State the properties and/or methods required for the subclass HourlyPaidEmployee. … … … … [4] (ii) State the properties and/or methods required for the subclass SalariedEmployee. … … … … [2] (d) Name the feature of object-oriented program design that allows the method CalculatePay to be declared in the superclass Employee. … … [1]

10 9608/42/M/J/15 © UCLES 2015 5 Data is stored in the array NameList[1:10]. This data is to be sorted. (a) (i) Complete the pseudocode algorithm for an insertion sort. FOR ThisPointer ← 2 TO … // use a temporary variable to store item which is to // be inserted into its correct location Temp ← NameList[ThisPointer] Pointer ← ThisPointer – 1 WHILE (NameList[Pointer] > Temp) AND … // move list item to next location NameList[…] ← NameList[…] Pointer ← … ENDWHILE // insert value of Temp in correct location NameList[…] ← … ENDFOR [7] (ii) A special case is when NameList is already in order. The algorithm in part (a)(i) is applied to this special case. Explain how many iterations are carried out for each of the loops. … … … … … … [3]

11 9608/42/M/J/15 © UCLES 2015 [Turn over (b) An alternative sort algorithm is a bubble sort: FOR ThisPointer ← 1 TO 9 FOR Pointer ← 1 TO 9 IF NameList[Pointer] > NameList[Pointer + 1] THEN Temp ← NameList[Pointer] NameList[Pointer] ← NameList[Pointer + 1] NameList[Pointer + 1] ← Temp ENDIF ENDFOR ENDFOR (i) As in part (a)(ii), a special case is when NameList is already in order. The algorithm in part (b) is applied to this special case. Explain how many iterations are carried out for each of the loops. … … … … [2]

12 9608/42/M/J/15 © UCLES 2015 (ii) Rewrite the algorithm in part (b), using pseudocode, to reduce the number of unnecessary comparisons. Use the same variable names where appropriate. … … … … … … … … … … … … … … … … … [5]

13 9608/42/M/J/15 © UCLES 2015 [Turn over 6 A queue Abstract Data Type (ADT) has these associated operations: • create queue • add item to queue • remove item from queue The queue ADT is to be implemented as a linked list of nodes. Each node consists of data and a pointer to the next node. (a) The following operations are carried out: CreateQueue AddName("Ali") AddName("Jack") AddName("Ben") AddName("Ahmed") RemoveName AddName("Jatinder") RemoveName Add appropriate labels to the diagram to show the final state of the queue. Use the space on the left as a workspace. Show your final answer in the node shapes on the right: [3]

14 9608/42/M/J/15 © UCLES 2015 (b) Using pseudocode, a record type, Node, is declared as follows: TYPE Node DECLARE Name : STRING DECLARE Pointer : INTEGER ENDTYPE The statement DECLARE Queue : ARRAY[1:10] OF Node reserves space for 10 nodes in array Queue. (i) The CreateQueue operation links all nodes and initialises the three pointers that need to be used: HeadPointer, TailPointer and FreePointer. Complete the diagram to show the value of all pointers after CreateQueue has been executed. Queue HeadPointer Name Pointer [1] [2] TailPointer [3] [4] [5] FreePointer [6] [7] [8] [9] [10] [4]

15 9608/42/M/J/15 © UCLES 2015 [Turn over (ii) The algorithm for adding a name to the queue is written, using pseudocode, as a procedure with the header: PROCEDURE AddName(NewName) where NewName is the new name to be added to the queue. The procedure uses the variables as shown in the identifier table. Identifier Data type Description Queue Array[1:10] OF Node Array to store node data NewName STRING Name to be added FreePointer INTEGER Pointer to next free node in array HeadPointer INTEGER Pointer to first node in queue TailPointer INTEGER Pointer to last node in queue CurrentPointer INTEGER Pointer to current node PROCEDURE AddName(BYVALUE NewName : STRING) // Report error if no free nodes remaining IF FreePointer = 0 THEN Report Error ELSE // new name placed in node at head of free list CurrentPointer ← FreePointer Queue[CurrentPointer].Name ← NewName // adjust free pointer FreePointer ← Queue[CurrentPointer].Pointer // if first name in queue then adjust head pointer IF HeadPointer = 0 THEN HeadPointer ← CurrentPointer ENDIF // current node is new end of queue Queue[CurrentPointer].Pointer ← 0 TailPointer ← CurrentPointer ENDIF ENDPROCEDURE

16 9608/42/M/J/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. Complete the pseudocode for the procedure RemoveName. Use the variables listed in the identifier table. PROCEDURE RemoveName() // Report error if Queue is empty … … … … OUTPUT Queue[…………………………………………………………].Name // current node is head of queue … // update head pointer … // if only one element in queue then update tail pointer … … … … // link released node to free list … … … ENDPROCEDURE [6]

® IGCSE is the registered trademark of Cambridge International Examinations. CAMBRIDGE INTERNATIONAL EXAMINATIONS Cambridge International Advanced Level MARK SCHEME for the May/June 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 May/June 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 – May/June 2015 9608 42 © Cambridge International Examinations 2015 1 locked unlocked push Attempt to insert coin Pass through start Insert coin Mark as follows: 1 mark for both states correct 1 mark for each further label [5] 2 (a) capital_city(santiago). city_in_country(santiago, chile). country_in_continent(chile,south_america). city_visited(santiago). accept in any order [4] (b) ThisCity = manchester london [2] (c) countries_visited(ThisCountry) IF city_visited(ThisCity) 1 AND 1 city_in_country(ThisCity, ThisCountry) 2 [4]

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 3 (a) Conditions goods totalling more than $20 Y Y Y Y N N N N goods totalling more than $100 Y Y N N Y Y N N have discount card Y N Y N Y N Y N Actions No discount X X X X X 5% discount X X 10% discount X 1 mark 1 mark 1 mark 1 mark [4] (b) Conditions goods totalling more than $20 Y Y Y Y N goods totalling more than $100 Y Y N N - have discount card Y N Y N - Actions No discount X X 5% discount X X 10% discount X 1 mark per column [5]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 (c) Example Pascal FUNCTION Discount(GoodsTotal: INTEGER; HasDiscountCard: BOOLEAN) : INTEGER; BEGIN (1) IF GoodsTotal > 20 (1) THEN (2) IF GoodsTotal > 100 (2) THEN (3) IF HasDiscountCard = TRUE (3) THEN (3) Discount := 10 (3) ELSE (3) Discount := 5 (2) ELSE (4) IF HasDiscountCard = TRUE (4) THEN (4) Discount := 5 (4) ELSE (4) Discount := 0 (1) ELSE (1) Discount := 0; END; Example Python def Discount(GoodsTotal, HasDiscountCard) : (1) if GoodsTotal > 20: (2) if GoodsTotal > 100: (3) if HasDiscountCard == True: (3) return 10 (3) else: (3) return 5 (2) else: (4) if HasDiscountCard == TRUE: (4) return 5 (4) else: (4) return 0 (1) else: (1) return 0 [6]

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 4 (a) [3]

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 (b) Example Pascal Type Employee = CLASS PUBLIC procedure SetEmployeeName Procedure SetEmployeeID Procedure CalculatePay PRIVATE EmployeeName : STRING EmployeeID : STRING AmountPaidThisMonth : Currency END; Mark as follows: Class header (1 mark) PUBLIC and PRIVATE used correctly (1 mark) EmployeeName + EmployeeID (1 mark) AmountPaidThisMonth (1 mark) Methods x 3 (1 mark) Example VB Class Employee Private EmployeeName As String Private EmployeeID As String Private AmountPaidThisMonth As Decimal Public Sub SetEmployeeName() End Sub Public Sub SetEmployeeID() End Sub Public Sub CalculatePay() End Sub Example Python Class Employee(): def __init__(self): self.__EmployeeName = "" self.__EmployeeID = "" self.__AmountPaidThisMonth = 0 def SetEmployeeName(self, Name): self.__EmployeeName = Name def SetEmployeeID(self, ID): self.__EmployeeID = ID def SetAmountPaidThisMonth(self, Paid): self.__AmountPaidThisMonth = Paid [max 5]

Page 7 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 (c) (i) HoursWorked 1 HourlyPayRate 1 SetHoursWorked 1 CalculatePay : Override 1 + 1 SetPayRate 1 [max 4] (ii) AnnualSalary 1 SetSalary 1 CalculatePay : Override 1 [max 2] (d) Polymorphism [1] 5 (a) (i) FOR ThisPointer
2 TO 10 // use a temporary variable to store item which is to // be inserted into its correct location Temp
NameList[ThisPointer] Pointer
ThisPointer – 1 WHILE (NameList[Pointer] > Temp) AND (Pointer > 0) // move list item to next location NameList[Pointer + 1]
NameList[Pointer] Pointer
Pointer - 1 ENDWHILE // insert value of Temp in correct location NameList[Pointer + 1] Temp
ENDFOR 1 mark for each gap filled correctly [7] (ii) The outer loop (FOR loop) is executed 9 times (1 mark) it is not dependant on the dataset (1 mark) The Inner loop (WHILE loop) is not entered (1 mark) as the condition is already false at the first encounter (1 mark) [max 3] (b) (i) outer loop is executed 9 times (1 mark) inner loop is executed 9 times (for each iteration of the outer loop) (1 mark) not dependant on the dataset (1 mark) [max 2]

Page 8 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 (ii) NumberOfItems
10 REPEAT NoMoreSwaps
TRUE FOR Pointer
1 TO NumberOfItems – 1 IF NameList[Pointer] > NameList[Pointer + 1] THEN NoMoreSwaps
FALSE Temp
NameList[Pointer] NameList[Pointer]
NameList[Pointer + 1] NameList[Pointer + 1]
Temp ENDIF ENDFOR NumberOfItems
NumberOfItems - 1 UNTIL NoMoreSwaps = TRUE Mark as follows: • change outer loop to a REPEAT/WHILE loop (1 mark) • FOR loop has variable used for final value (1 mark) • Initialise Boolean variable to TRUE (1 mark) • set Boolean variable to FALSE in correct place (1 mark) • number of items to consider on each pass decrements (1 mark) • Correct stopping condition for REPEAT loop (1 mark) [max 5] 6 (a) Head Ben Ahmed Tail Jatinder 0 1 mark for Head and Tail pointers 1 mark for 3 correct items – linked as shown 1 mark for correct order with null pointer in last nod [3]

Page 9 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 42 © Cambridge International Examinations 2015 (b) (i) Queue HeadPointer Name Pointer 0 [1] 2 [2] 3 TailPointer [3] 4 0 [4] 5 [5] 6 FreePointer [6] 7 1 [7] 8 [8] 9 [9] 10 [10] 0 Mark as follows: HeadPointer =0 & TailPointer = 0 FreePointer assigned a value Pointers[1] to [9] links the nodes together Pointer[10] = 'Null' [4] (ii) PROCEDURE RemoveName() // Report error if Queue is empty IF HeadPointer = 0 THEN Error ELSE OUTPUT Queue[HeadPointer].Name // current node is head of queue CurrentPointer
HeadPointer // update head pointer HeadPointer
Queue[CurrentPointer].Pointer //if only one element in queue,then update tail pointer IF HeadPointer = 0 THEN TailPointer
0 ENDIF // link released node to free list Queue[CurrentPointer].Pointer
FreePointer FreePointer
CurrentPointer ENDIF ENDPROCEDURE [max 6]