Computer Science 9618/31 May/June 2021: question paper and mark scheme

Mark scheme

1(a) Working: one mark for calculation of the mantissa and one mark for 3 calculation or use of the exponent Exponent: one from: = 0.11101 × 23 // 0.11101 × 211 // 0.11101 × 103 // 0.11101 × 1011 = 1.00011 × 23 // 1.00011 × 211 // 1.00011 × 103 // 1.00011 × 1011 = appropriate shifting of binary point for +7.25 Mantissa: one from: = 111.01 (conversion to binary +7.25 – 10 bits) = 0111010000 (mantissa 10 bits for +7.25 = 1000101111(one’s complement mantissa for –7.25) = 1000110000 (two’s complement mantissa for –7.25) Correct Answer (Max 1) Mantissa Exponent 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1(b) One mark for working out the exponent 3 One mark for working out the mantissa One mark for the correct answer Example answers • =1.011000111 × 27 (exponent is 7) • =10110001.11 // –128 + 32 + 16 + 1 + 0.5 + 0.25 // convert to positive 01001110.01 (and add a minus sign to the answer) • –78.25 1(c) One mark for working 3 One mark for correct mantissa One mark for correct exponent Example answers Number of places added to exponent for normalisation −6 for number to retain its value // mantissa moved 6 places left Mantissa 0 1 1 1 0 0 0 0 0 0 Exponent 1 0 0 0 0 1 1(d)(i) One mark for each correct marking point (Max 3) 3 • Requires 11 bits / more than 10 bits to store (accurately) / reference to maximum (positive) number that can be stored = 511 • Denary 513 in binary is 1000000001 // Normalised: 0.1000000001 • Results in overflow 1(d)(ii) One mark for each correct marking point (Max 2) 2 • The number of bits for the mantissa must be increased • 11/12 bits mantissa and 5/4 bits exponent

Mark scheme

2(a) One mark for each correct marking point (Max 2) 2 • To create a new data type (from existing data types) • To allow data types not available in a programming language to be constructed // To extend the flexibility of the programming language 2(b)(i) TYPE SchoolDay = (Monday, Tuesday, Wednesday, Thursday, 1 Friday) 2(b)(ii) TYPE WeekEnd = (Saturday, Sunday) 1 2(c) One mark for each marking point (Max 4) 4 • TYPE ClubMeet and ENDTYPE correct • DECLARE FirstName and DECLARE LastName included with correct data types • DECLARE Schoolday included with correct data types from part 2(b)(i) • DECLARE Weekend included with correct data types from part 2(b)(ii) Example answer TYPE ClubMeet DECLARE FirstName : STRING DECLARE LastName : STRING DECLARE Schoolday : SchoolDay DECLARE Weekend : WeekEnd ENDTYPE

Mark scheme

3(a) One mark for each correct line from Operating System Term to Description 5 Managing the execution of many programs that appear to run at the same time 3(b) One mark for each correct statement (Max 4) 4 • An interpreter examines source code one statement at a time • Check each statement for errors • …If no error is found the statement is executed • …If an error is found this is reported and the interpreter halts • Interpretation is repeated for every iteration in repeated sections of code/in loops • Interpretation has to be repeated every time the program is run

Mark scheme

4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

Mark scheme

5(a) Working (Max 3) 5 May be seen on diagram • Initialisation: setting Base to 0 • … and the rest of the towns to ∞ • Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ May be seen in working section of paper • Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8 5(b) One mark for each correct marking point (Max 3) 3 • Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide relationships between nodes • AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression methods

Mark scheme

6 One mark for each correct benefit (Max 2) 4 • Accuracy – Ensures accurate delivery of the message • Completeness – Missing packets can be easily detected and a re-send request sent so the message arrives complete • Resilience – if a network changes the router can detect this and send the data another way to ensure it arrives • Path also available to other users // Doesn’t use whole bandwidth // allows simultaneous use of channel by multiple users • Better security as packets hashed and sent by different routes. One mark for each correct drawback (Max 2) • Time delays to correct errors // Network problems may introduce errors in packets • Requires complex protocols for delivery • Unsuitable for real time transmission applications

Mark scheme

7(a) One mark for working, (all three columns P, Q and R) 3 One mark for each correct column Y, Z A B C P Q R Y Z 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 7(b) Full adder 1 7(c) One mark for each point 4 _ _ _ _ _ _ Y = A B C + A B C + A B C + A B C Purpose: Sum bit _ _ _ Z = A B C + A B C + A B C + A B C Purpose: Carry output

Mark scheme

8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student

Mark scheme

9(a) One mark for each correct marking point (Max 2) 2 • Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to perform • … in the order written / given • … each line of code changes something in the program run. 9(b) One mark for each correct marking point (Max 2) 2 • Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a mathematical style 9(c) One mark for each correct programming paradigm (Max 4) 4 Program code example Programming paradigm male(john). female(ethel). Declarative parent(john, ethel). FOR Counter = 1 TO 20 X = X * Counter Procedural / imperative NEXT Counter Start: LDD Counter INC ACC Low-level / assembly STO Counter public class Vehicle { private speed; public Vehicle() { Object oriented / (OOP) speed = 0; } }