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

This document consists of 15 printed pages and 1 blank page. DC (AC/SW) 95230/2 © UCLES 2015 [Turn over Cambridge International Examinations Cambridge International Advanced Level * 7 8 8 1 0 7 0 8 9 7 * COMPUTER SCIENCE 9608/43 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/43/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/43/M/J/15 © UCLES 2015 [Turn over 1 A petrol filling station has a single self-service petrol pump. A customer can use the petrol pump when it is ready to dispense petrol. The pump is in use when the customer takes the nozzle from a holster on the pump. The pump dispenses petrol while the customer presses the trigger on the nozzle. When the customer replaces the nozzle into the holster, the pump is out of use. The cashier must press a reset button to make the pump ready for the next customer to use. The petrol pump’s four possible states and the transition from one state to another are as shown in the table below. Current state Event Next state Pump ready Take nozzle Pump in use Pump in use Press trigger Pump dispensing Pump dispensing Stop pressing trigger Pump in use Pump in use Replace nozzle Pump out of use Pump out of use Reset pump display Pump ready Complete the state transition diagram for the petrol pump: … … … … … … … … … start [9]

4 9608/43/M/J/15 © UCLES 2015 2 A declarative programming language is used to represent the knowledge base shown below: 01 dairy_product(cheese). 02 meat(beef). 03 meat(chicken). 04 meat(lamb). 05 made_with(burger, beef). 06 made_with(kofta, lamb). 07 made_with(quiche, cheese). 08 made_with(quiche, egg). 09 made_with(quiche, flour). These clauses have the following meaning: Clause Explanation 01 Cheese is a dairy product 02 Beef is a meat 05 A burger is made with beef (a) More facts are to be included. Laasi is made with the dairy products milk and yogurt. Write additional clauses to record this. 10 … … 11 … … 12 … … 13 … … [4]

5 9608/43/M/J/15 © UCLES 2015 [Turn over (b) Using the variable TypeOfMeat, the goal meat(TypeOfMeat) returns TypeOfMeat = beef, chicken, lamb Write the result returned by the goal: made_with(quiche, Ingredient) Ingredient = … … [2] (c) Complete the rule to list the dishes made with meat. contains_meat(Dish) IF … … … … … [4]

6 9608/43/M/J/15 © UCLES 2015 3 An insurance company calculates the cost of car insurance from a basic price. The driver may: • get a discount on the basic price of the insurance • have to pay an extra charge The decision is arrived at as follows: • for a driver aged 25 or over: • 5% discount if no previous accident • no discount if a previous accident • for a driver under the age of 25: • 5% discount if no previous accident and licence held for 3 or more years • no discount if a previous accident but licence held for 3 or more years • no discount if no previous accident but licence held for less than 3 years • 10% extra charge if a previous accident and licence held for less than 3 years (a) Complete the decision table. Conditions Age under 25 Y Y Y Y N N N N Previous accident Y Y N N Y Y N N Licence held for 3 or more years Y N Y N Y N Y N Actions 10% extra charge No discount 5% discount [6] (b) Simplify your solution by removing redundancies. Conditions Age under 25 Previous accident Licence held for 3 or more years Actions 10% extra charge No discount 5% discount [3]

7 9608/43/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 CostPercentageChange. This function returns the percentage change from the basic price as an integer. A discount should be shown as a negative integer. An extra charge should be shown as a positive integer. Identifier Data type Comment DriverAge INTEGER Age of driver in years HadAccident BOOLEAN Whether driver has had a previous accident YearsLicenceHeld INTEGER Number of years the driver has held licence Write program code for this function. Programming language … … … … … … … … … … … … … … … … … … … … [6]

8 9608/43/M/J/15 © UCLES 2015 4 A sports club stores data about its members. A program is to be written using an object-oriented programming language. A Member class is designed. Two subclasses have been identified: • FullMember • JuniorMember (a) Draw an inheritance diagram for these classes. [3] (b) The design for the Member class consists of • properties • MemberName • MemberID • SubscriptionPaid • methods • SetMemberName • SetMemberID • SetSubscriptionPaid

9 9608/43/M/J/15 © UCLES 2015 [Turn over Write program code for the class definition of the superclass Member. Programming language … … … … … … … … … … … [5] (c) Additionally a DateOfBirth property is required for the JuniorMember class. (i) Write program code for the class definition for the subclass JuniorMember. … … … … … … [3] (ii) Write program code to create a new instance of JuniorMember. Use identifier NewMember with the following data: name Ahmed with member ID 12347, born on 12/11/2001, who has paid his subscription. … … … … … … [3]

10 9608/43/M/J/15 © UCLES 2015 5 A stack Abstract Data Type (ADT) has these associated operations: • create stack • add item to stack (push) • remove item from stack (pop) The stack ADT is to be implemented as a linked list of nodes. Each node consists of data and a pointer to the next node. (a) There is one pointer: the top of stack pointer, which points to the last item added to the stack. Draw a diagram to show the final state of the stack after the following operations are carried out. CreateStack Push("Ali") Push("Jack") Pop Push("Ben") Push("Ahmed") Pop Push("Jatinder") Add appropriate labels to the diagram to show the final state of the stack. Use the space on the left as a workspace. Show your final answer in the node shapes on the right: [3]

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

12 9608/43/M/J/15 © UCLES 2015 (ii) The algorithm for adding a name to the stack is written, using pseudocode, as a procedure with the header PROCEDURE Push (NewName) Where NewName is the new name to be added to the stack. The procedure uses the variables as shown in the identifier table. Identifier Data type Description Stack Array[1:10] OF Node NewName STRING Name to be added FreePointer INTEGER Pointer to next free node in array TopOfStackPointer INTEGER Pointer to first node in stack TempPointer INTEGER Temporary store for copy of FreePointer PROCEDURE Push(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 Stack[FreePointer].Name ← NewName // take a temporary copy and // then adjust free pointer TempPointer ← FreePointer FreePointer ← Stack[FreePointer].Pointer // link current node to previous top of stack Stack[TempPointer].Pointer ← TopOfStackPointer // adjust TopOfStackPointer to current node TopOfStackPointer ← TempPointer ENDIF ENDPROCEDURE

13 9608/43/M/J/15 © UCLES 2015 [Turn over Complete the pseudocode for the procedure Pop. Use the variables listed in the identifier table. PROCEDURE Pop() // Report error if Stack is empty … … … … OUTPUT Stack […].Name // take a copy of the current top of stack pointer … // update the top of stack pointer … // link released node to free list … … … ENDPROCEDURE [5]

14 9608/43/M/J/15 © UCLES 2015 6 A recursively defined procedure X is defined below: PROCEDURE X(BYVALUE n : INTEGER) IF (n = 0) OR (n = 1) THEN OUTPUT n ELSE CALL X(n DIV 2) OUTPUT (n MOD 2) ENDIF ENDPROCEDURE (a) Explain what is meant by recursively defined. … … [1] (b) Explain how a stack is used during the execution of a recursive procedure. … … … … [2] (c) Dry run the procedure X by completing the trace table for the procedure call: CALL X(40) Call number n (n = 0) OR (n = 1) n DIV 2 n MOD 2 1 40 FALSE 20 2 3 4 5 6 OUTPUT … [6]

15 9608/43/M/J/15 © UCLES 2015 (d) State the process that is carried out by procedure X. … … [1] (e) Write program code for procedure X. Programming language … … … … … … … … … [5]

16 9608/43/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. BLANK PAGE

® 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/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 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 43 © Cambridge International Examinations 2015 1 Pump ready Pump in use Replace nozzle Press trigger start Take nozzle Pump out of use Pump dispensing Stop pressing trigger Reset pump display [9] 2 (a) made_with(laasi, milk). made_with(laasi, yogurt). dairy_product(milk). dairy_product(yogurt). [4] (b) Ingredient = cheese, egg, flour [2] (c) contains_meat(Dish) IF made_with(Dish, X) (2 marks) AND (1 mark) meat(X) (1 mark) [4]

Page 3 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 3 (a) Conditions Age under 25 Y Y Y Y N N N N Previous accident Y Y N N Y Y N N Licence held for 3 or more years Y N Y N Y N Y N Actions 10% extra cost X No discount X X X X 5% discount X X X 1 mark 1 mark 1 mark 1 mark 1 mark 1 mark [6] (b) Conditions Age under 25 Y Y Y Y N N Previous accident Y Y N N Y N Licence held for 3 or more years Y N Y N - - Actions 10% extra cost X No discount X X X 5% discount X X 1 mark 1 mark 1 mark [3]

Page 4 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 (c) Example Pascal FUNCTION CostPercentageChange(DriverAge : INTEGER; HadAccident : BOOLEAN; YearsLicenceHeld : INTEGER) : INTEGER; BEGIN IF DriverAge >= 25 THEN IF HadAccident = TRUE THEN CostPercentageChange := 0 ELSE CostPercentageChange := -5 ELSE IF HadAccident = TRUE THEN IF YearsLicenceHeld < 3 THEN CostPercentageChange := 10 ELSE CostPercentageChange := 0 ELSE IF YearsLicenceHeld < 3 THEN CostPercentageChange := 0 ELSE CostPercentageChange:= -5; END; Example Python def CostPercentageChange(DriverAge, HadAccident, YearsLicenceHeld) : if DriverAge >= 25: if HadAccident: return 0 else: return -5 else: if HadAccident: if YearsLicenceHeld < 3: return 10 else: return 0 else: if YearsLicenceHeld < 3: return 0 else: return -5;

Page 5 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 Mark as follows: Correct function header Correct IF statement (1) Correct IF statement (2) Correct IF statement (3) Correct IF statement (4) Correct IF statement (5) Correct return statement (or equivalent) [max 6] OR equivalent demonstrating correct logic 4 (a) [3] (b) Example Pascal Member = CLASS PUBLIC Procedure SetMemberName; Procedure SetMemberID; Procedure SetSubscriptionPaid; PRIVATE MemberName : STRING; MemberID : STRING; SubscriptionPaid : Boolean; END;

Page 6 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 Example Python class Member() : def__init__(self): PUBLIC self.__MemberName = "" self.__MemberID = "" self.__SubscriptionPaid = False def SetMemberName(self, Name): self.MemberName = Name def SetMemberID(self, ID): self.MemberID = ID def SetSubscriptionPaid(self, Paid): self.SubscriptioPaid = Paid Mark as follows: Class header (1 mark) Public and Private used correctly (1 mark) MemberName + MemberID (1 mark) SubscriptionPaid (1 mark) Methods × 3 (1 mark) [5] (c) (i) Example Pascal JuniorMember = CLASS (Member) PUBLIC Procedure SetDateOfBirth; PRIVATE DateOfBirth : DateTime; END; Example Python class JuniorMember (Member): def__init__self: super().__init__() self.DateOfBirth = "" def SetDateOfBirth(self, Date): self.DateOfBirth = Date def SetMemberName(self, Name): super().SetMemberName(Name) def SetMemberID(self, ID): super().SetMemberID(ID) def SetSubscriptionPaid(self, Paid): super().SetSubscriptioPaid(Paid) [3]

Page 7 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 (ii) Example Pascal NewMember := JuniorMember.Create; (1 mark) NewMember.SetMemberName('Ahmed'); NewMember.SetMemberID('12347'); (1 mark) NewMember.SetSubscriptionPaid(TRUE); NewMember.SetDateOfBirth("12/11/2001"); (1 mark) Example Python NewMember := JuniorMember() (1 mark) NewMember.SetMemberName("Ahmed") NewMember.SetMemberID("12347") (1 mark) NewMember.SetSubscriptionPaid(TRUE) NewMember.SetDateOfBirth("12/11/2001") (1 mark) [3] 5 (a) Jatinder Ben Ali 0 1 mark for Top of Stack pointer 1 mark for 3 correct items 1 mark for correct order with null pointer in last node [3] Top of Stack

Page 8 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 (b) (i) Stack TopOfStackPointer Name Pointer 0 [1] 2 [2] 3 FreePointer [3] 4 1 [4] 5 [5] 6 [6] 7 [7] 8 [8] 9 [9] 10 [10] 0 Mark as follows: TopOfStackPointer FreePointer Pointers[1] to [9] Pointer[10] [4]

Page 9 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 (ii) PROCEDURE Pop() // Report error if Stack is empty IF TopOfStackPointer = 0 THEN Error ELSE OUTPUT Stack[TopOfStackPointer].Name // take a copy of the current top of stack pointer TempPointer
TopOfStackPointer // update the top of stack pointer TopOfStackPointer
Stack[TempPointer].Pointer // link released node to free list Stack[TempPointer].Pointer
FreePointer FreePointer
TempPointer ENDIF ENDPROCEDURE 1 mark for each line of code as above (first 4 lines + ENDIF for 1 mark) [Max 5] 6 (a) A procedure that calls itself // is defined in terms of itself [1] (b) Before procedure call is executed current state of the registers/local variables is saved onto the stack When returning from a procedure call the registers/local variables are re-instated [2] (c) Call number n (n=0) OR (n=1) n DIV 2 n MOD 2 1 40 FALSE 20 0 2 20 FALSE 10 0 3 10 FALSE 5 0 4 5 FALSE 2 1 5 2 FALSE 1 0 6 1 TRUE 1 mark 1 mark 1 mark OUTPUT 101000 – 1 mark for each pair of bits. [6] (d) Conversion of denary number into binary [1]

Page 10 Mark Scheme Syllabus Paper Cambridge International A Level – May/June 2015 9608 43 © Cambridge International Examinations 2015 (e) (i) Example Pascal Procedure X(n: INTEGER) BEGIN IF (n = 0) OR (n = 1) THEN Write(n) ELSE BEGIN X(n DIV 2); Write(n MOD 2); END; END; Example Python def X(n): if (n == 0) or (n == 1): print(n, end="") else: X(n // 2) print(n % 2, end="") Mark as follows: Procedure heading & ending Boolean expression correctly grouped statements within ELSE recursive call Using DIV and MOD correctly [5]