Cambridge A Level Computer Science 9618 — 2021 May/June Paper 3 · Variant 3

1 Real numbers are stored in a computer system using floating-point representation with: • 10 bits for the mantissa • 6 bits for the exponent • Two’s complement form for both the mantissa and the exponent. (a) Calculate the normalised floating-point representation of –7.25 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (b) Calculate the denary value of the given binary floating-point number. Show your working. Mantissa Exponent 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Answer ...................................................................................................................................... [3] (c) The given binary floating-point number is not normalised. Normalise the floating-point number. Show your working. Mantissa Exponent 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (d) The denary number 513 cannot be stored accurately as a normalised floating-point number in this computer system. (i) Explain the reason for this. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [3] (ii) Describe an alteration to the way floating-point numbers are stored to enable this number to be stored accurately using the same total number of bits. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2]

Mark scheme: Question Answer Marks 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

More questions on Floating-point numbers, representation and manipulation

2 (a) Describe the purpose of a user-defined data type. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Define, using pseudocode, the following enumerated data types: (i) SchoolDay to hold data about the days students are usually in school. ........................................................................................................................................... ..................................................................................................................................... [1] (ii) WeekEnd to hold data about the days that are not school days. ........................................................................................................................................... ..................................................................................................................................... [1] (c) Define, using pseudocode, the composite data type ClubMeet. This will hold data about club members that includes: • first name and last name • the two days they attend: ○ one on a school day ○ one not on a school day. Use the enumerated types you created in part (b). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

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

More questions on User-defined data types

3 (a) Draw one line to connect each Operating System (OS) term to the most appropriate description about it. OS term Description Using secondary storage to simulate additional main memory Multi-tasking Managing the processes running on the CPU Paging Managing the execution of many programs that appear to run at the same time Interrupt handling Locating non-contiguous blocks of data and relocating them Scheduling Transferring control to another routine when a service is required Virtual memory Reading/writing same-size blocks of data from/to secondary storage when required [5] (b) Explain how an interpreter executes a program without producing a complete translated version of it. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

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

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 ................................................................................................................................................... ............................................................................................................................................. [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - ................................................................................................................................................... ............................................................................................................................................. [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2]

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)

More questions on Algorithms

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. Show your working and write your answers in the table provided. Base 4 5 Town 1 2 Town 2 1 8 Town 3 7 3 Town 6 1 5 6 Town 4 Town 5 Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Answers Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 [5] (b) Explain the use of graphs to aid Artificial Intelligence (AI). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

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

More questions on Algorithms

6 Give two benefits and two drawbacks of packet switching. Benefit 1 ........................................................................................................................................... .......................................................................................................................................................... Benefit 2 ........................................................................................................................................... .......................................................................................................................................................... Drawback 1 ...................................................................................................................................... .......................................................................................................................................................... Drawback 2 ...................................................................................................................................... .......................................................................................................................................................... [4]

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

7 The diagram shows a logic circuit. A P Y B C R Z Q (a) Complete the truth table for the given logic circuit. Show your working. Inputs Working space Outputs A B C P Q R Y Z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 [3] (b) State the name of the logic circuit. ............................................................................................................................................. [1] (c) Write the Boolean expressions for the two outputs Y and Z in the truth table as sum-of-products and state the purpose of each output. Y = ............................................................................................................................................ Purpose .................................................................................................................................... Z = ............................................................................................................................................ Purpose .................................................................................................................................... [4]

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

8 (a) State two factors that may affect the performance of a sorting algorithm. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one- dimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. The contents of both arrays after sorting are shown. Name Score 1 2 1 98 1 Smithfield Tom 2 97 2 Johnson Jane … … 248 5 248 Peters Jade 249 3 249 Allen John YearSize 249 ← Flag TRUE ← WHILE Flag = TRUE Flag FALSE ← FOR Student 1 TO YearSize - 1 ← IF Score[Student] < Score[Student + 1] THEN Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Score[Student] Score[Student + 1] ← Name[Student,1] Name[Student + 1,1] ← Name[Student,2] Name[Student + 1,2] ← Score[Student + 1] Temp1 ← Name[Student + 1,1] Temp2 ← Name[Student + 1,2] Temp3 ← Flag TRUE ← ENDIF NEXT Student ENDWHILE Write an algorithm, using pseudocode, that will perform the same task using an insertion sort. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [6]

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

More questions on Algorithms

9 (a) Describe what is meant by an imperative (procedural) programming language. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Describe what is meant by a declarative programming language. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (c) Identify the programming paradigm for each of these program code examples. Program code example Programming paradigm male(john). female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 X = X * Counter NEXT Counter Start: LDD Counter INC ACC STO Counter public class Vehicle { private speed; public Vehicle() { speed = 0; } } [4]

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; } }

More questions on Programming Paradigms