Year 11 Paper 4: Algorithms and Ethics
Covers searching and sorting algorithms, algorithm design and trace tables, programming constructs, logic gates and boolean logic, ethics, law and environmental impact, representing text, images, sound and compression, and binary and hexadecimal number systems.
Year 11 follows a typical teaching order. No exam board defines what belongs to Year 11, and schools sequence the course differently. Check it against your own scheme of work before using it to decide what a class has covered.
Questions
Question 1 [2 marks]
Boolean Logic and Logic Gates
A logic circuit contains a single NOT gate.
State the output of the NOT gate when its input is 1, and its output when its input is 0.
Question 2 [2 marks]
Number Systems: Binary and Hexadecimal
Convert the denary number 45 into an 8-bit binary number.
Question 3 [2 marks]
Programming Constructs
A program stores a person's height in metres as a decimal value, for example 1.75.
State the most appropriate data type for this variable, and state one other example of data that would use this data type.
Question 4 [2 marks]
Searching and Sorting Algorithms
A binary search is carried out on the sorted list [3, 9, 14, 21, 28, 35] for the value 5, which is not in the list.
State what eventually happens when the binary search cannot find any matching value.
Question 5 [3 marks]
Representing Text, Images, Sound and Compression
A computer uses ASCII to represent text.
Explain what is meant by a character set, and state why ASCII cannot represent every character used in the world's written languages.
Question 6 [3 marks]
Algorithm Design and Trace Tables
The following pseudocode is run:
for i = 1 to 4
print i * 2
next i
State each value of i and its corresponding output, in order. The for loop includes both endpoint values.
Question 7 [4 marks]
Ethics, Law and Environmental Impact
A UK law requires organisations to keep personal data accurate, secure and used only for a stated purpose.
State which UK law this describes, and state three rights this law gives to individuals regarding their own personal data.
Question 8 [3 marks]
Number Systems: Binary and Hexadecimal
Two 4-bit binary values are combined using a bitwise AND: 1010 AND 1100.
Calculate the result of this bitwise AND, and state the general rule that a bitwise AND applies to each pair of corresponding bits.
Question 9 [2 marks]
Boolean Logic and Logic Gates
A logic circuit has two inputs, A and B, and its truth table is: A=0,B=0 gives output 0 ; A=0,B=1 gives output 1 ; A=1,B=0 gives output 1 ; A=1,B=1 gives output 0.
State the name of the single logic gate that matches this truth table, and write the Boolean expression for its output using A and B.
Question 10 [3 marks]
Number Systems: Binary and Hexadecimal
A logical shift right by 3 places is applied to the 8-bit binary number 01101000, with zeros filling the empty places on the left.
State the resulting 8-bit binary number, and state the denary value of the number both before and after the shift.
Question 11 [3 marks]
Ethics, Law and Environmental Impact
A company uses CCTV cameras with facial recognition software throughout its office building to track which employees enter and leave, and when.
Discuss the ethical issue this raises regarding employee privacy.
Question 12 [4 marks]
Boolean Logic and Logic Gates
A NAND gate has two inputs, C and D, and its output is the opposite of what an AND gate would give for the same inputs.
Write a Boolean expression for the NAND gate's output using C and D, and state its output when C=1 and D=1.
Question 13 [4 marks]
Programming Constructs
A subroutine called addTax is written to take a price as a parameter and return the price with 20% tax added.
Explain what a parameter is using addTax(price), distinguish the formal parameter from a supplied argument, and give a call with its returned value. Assume real arithmetic and 20% tax.
Use the example call addTax(100) in your explanation.
Question 14 [4 marks]
Ethics, Law and Environmental Impact
A student wants other people to be able to freely share and adapt an image they have created for a school project, as long as they are credited as the original creator, but does not want anyone to sell the image for profit.
Explain how a Creative Commons licence could allow the student to achieve this, rather than using traditional 'all rights reserved' copyright.
Question 15 [5 marks]
Programming Constructs
A programmer's code reads a number from the user as a string, and needs to convert it into an integer before doing a calculation. Later, the program needs to convert a calculated integer total back into a string so it can be joined with other text and displayed.
Explain why both of these conversions (casting) are needed, referring to what would go wrong without each one.
Question 16 [5 marks]
Searching and Sorting Algorithms
The list [7, 2, 9, 4] is sorted into ascending order using an insertion sort.
Starting with the first item as the sorted prefix, state the complete list after inserting each remaining item. Then explain which items shift during the final insertion and where the final key is placed.
Question 17 [5 marks]
Number Systems: Binary and Hexadecimal
A temperature sensor stores readings as 8-bit two's complement signed binary numbers, allowing both positive and negative values.
Explain how a negative number, for example -20, would be represented in 8-bit two's complement, describing the steps involved, and state the denary range of values that can be represented using 8-bit two's complement.
Question 18 [6 marks]
Searching and Sorting Algorithms
A programmer must choose a sorting algorithm to sort a list of 2 million transaction records that must be sorted from scratch once per night, with enough spare memory available to hold a full second copy of the list during sorting.
Discuss why a merge sort would be a more suitable choice than a bubble sort for this task.
Question 19 [6 marks]
Algorithm Design and Trace Tables
Design an algorithm, in pseudocode, that repeatedly asks the user to enter a number, stopping when the user enters -1, and then outputs the smallest number entered (not counting the -1).
Question 20 [6 marks]
Searching and Sorting Algorithms
A supermarket needs to search its list of 50000 product barcodes to find a product's price at the checkout. The list of barcodes is kept sorted, and a new search happens every time an item is scanned, hundreds of times a minute across many tills.
Discuss why binary search is well suited to these frequent lookups, comparing its worst-case checked-item comparisons with linear search. Explain the effect of losing sorted order, and name one other data structure that could support efficient exact barcode lookup.
Question 21 [6 marks]
Searching and Sorting Algorithms
A programmer needs to sort a list that is almost fully sorted already, with only a few items out of place.
Assume an array, very few inversions and standard merge sort that divides to singletons without skipping merges. Compare insertion sort and merge sort, including time and extra storage, and recommend an algorithm with a justified limitation of your recommendation.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| input 1 gives output 0 | B1 |
| input 0 gives output 1 | B1 |
| Final answer: Input 1 gives output 0; input 0 gives output 1 | |
| Question 2[2 marks] | |
|---|---|
| Answer or working | Marks |
| a correct method using binary place values (128, 64, 32, 16, 8, 4, 2, 1) | M1 |
| 00101101 | A1 |
| Question 3[2 marks] | |
|---|---|
| Answer or working | Marks |
| real (float) is the most appropriate data type, since the value needs decimal places | B1 |
| valid other example, for example a temperature reading, an average, or a price with pence | B1 |
| Final answer: Real/float; another example could be a temperature or an average, which also need decimal places | |
| Question 4[2 marks] | |
|---|---|
| Answer or working | Marks |
| the search keeps halving the remaining part of the list to search, narrowing down where 5 would be if it were present | B1 |
| once there is nothing left to check, the search reports (returns) that the value was not found in the list | B1 |
| Final answer: The search keeps halving the list until there is nothing left to check, then reports the value is not found | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| A character set is an agreed mapping between characters and distinct numeric codes. | B1 |
| Standard ASCII has 128 codes, representable in seven bits; it may be stored in a byte. | B1 |
| This finite repertoire is too small for all written languages; accept discussion of extended 8-bit sets if clearly distinguished. | B1 |
| Final answer: A character set maps characters to numeric codes. Standard ASCII has 128 codes, too few for all written languages; storing its codes in bytes does not enlarge its repertoire. | |
| Question 6[3 marks] | |
|---|---|
| Answer or working | Marks |
| First output is 2 | B1 |
| Middle outputs are 4 then 6 | B1 |
| Final output is 8 and the loop stops | B1 |
| Final answer: The output, on separate lines, is 2,4,6,8. The inclusive loop uses i=1,2,3,4, multiplying each by 2. | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| identify Data Protection Act 2018 or UK GDPR, preferably recognising their combined UK data-protection framework | B1 |
| one valid individual right, such as access to personal data | B1 |
| a second different valid right, such as rectification | B1 |
| a third different valid right, such as qualified erasure, restriction, objection or portability; rights are subject to applicable conditions/exemptions | B1 |
| Final answer: Data Protection Act 2018 and UK GDPR form the relevant framework. Rights include access, rectification and erasure in qualifying circumstances; other valid conditional rights include restriction, objection and portability. | |
| Question 8[3 marks] | |
|---|---|
| Answer or working | Marks |
| Compares corresponding bit pairs using AND. | M1 |
| 1000; a correct result earns the method mark. | A1 |
| Each output bit is 1 exactly when both corresponding inputs are 1, otherwise 0. | B1 |
| Final answer: 1000; a bitwise AND gives 1 in a position only when both corresponding bits are 1, otherwise 0 | |
| Question 9[2 marks] | |
|---|---|
| Answer or working | Marks |
| Names XOR (exclusive OR). | B1 |
| Gives A XOR B, or (A AND NOT B) OR (NOT A AND B), or another equivalent Boolean expression. | B1 |
| Final answer: XOR gate; output = A XOR B | |
| Question 10[3 marks] | |
|---|---|
| Answer or working | Marks |
| Resulting binary number 00001101. | B1 |
| Denary value before: 104. | B1 |
| Denary value after: 13. | B1 |
| Final answer: 00001101; denary value before: 104, after: 13 (divided by 8) | |
| Question 11[3 marks] | |
|---|---|
| Answer or working | Marks |
| constant identifiable monitoring can intrude on privacy and reduce employee trust | B1 |
| unclear purposes, access controls or retention raise concern about misuse of facial/movement data | B1 |
| weigh legitimate security needs against necessity/proportionality and transparent limits on monitoring | B1 |
| Final answer: Facial tracking collects sensitive identifying information and can monitor movements beyond reasonable need, reducing autonomy and trust. Safety/security benefits must be weighed against necessity, proportionality, transparent notice, retention/access controls, consent or other lawful justification; minimise surveillance and offer oversight. | |
| Question 12[4 marks] | |
|---|---|
| Answer or working | Marks |
| Combines C and D with AND, or uses an equivalent De Morgan form. | M1 |
| Negates the whole conjunction: NOT (C AND D), accepting NOT C OR NOT D. | M1 |
| Evaluates C AND D as 1 for C=D=1, or correctly substitutes into an equivalent expression. | M1 |
| Gives output 0; full evaluation credit for the correct stated output. | A1 |
| Final answer: output = NOT (C AND D); with C=1, D=1 the output is 0 | |
| Question 13[4 marks] | |
|---|---|
| Answer or working | Marks |
| Parameter is a named input in the subroutine definition | B1 |
| price receives the supplied value for each addTax call | B1 |
| Body uses price to calculate price * 1.2 | B1 |
| Example addTax(100) supplies 100 and returns 120 | B1 |
| Final answer: A parameter is a named input in a subroutine definition. In addTax(price), price is the formal parameter; calling addTax(100) supplies the argument 100 to it. The body uses that value to return price * 1.2, giving 120 for this call. | |
| Question 14[4 marks] | |
|---|---|
| Answer or working | Marks |
| copyright normally reserves reuse rights to the creator, subject to licences and legal exceptions | B1 |
| a Creative Commons licence grants reuse permissions in advance rather than requiring individual permission each time | B1 |
| attribution requires credit to the creator under the licence terms | B1 |
| a suitable licence such as CC BY-NC permits sharing/adaptation for non-commercial purposes; commercial use needs additional permission and NC is broader than merely prohibiting sales | B1 |
| Final answer: CC BY-NC can grant sharing and adaptation with attribution for non-commercial purposes while copyright remains with the creator. Commercial use requires separate permission; the NC restriction is broader than merely banning sale of the image. Copyright exceptions still apply. | |
| Question 15[5 marks] | |
|---|---|
| Answer or working | Marks |
| Numeric input initially has string type | B1 |
| Casting to integer enables numeric arithmetic | B1 |
| Without casting addition may concatenate or raise a type error | B1 |
| Cast integer total to string for text concatenation | B1 |
| Without a supported implicit conversion mixed-type concatenation may fail | B1 |
| Final answer: Cast numeric input text to an integer so arithmetic uses its numerical value: int("12") + 3 is 15. Without conversion a language may concatenate to form "123" or raise a type error. Cast a calculated total back with str(total) when joining it to text, for example "Total: " + str(15) gives "Total: 15"; a language without implicit conversion may otherwise reject the mixed types. Exact behaviour depends on the language. | |
| Question 16[5 marks] | |
|---|---|
| Answer or working | Marks |
| After inserting 2: [2,7,9,4] | B1 |
| After inserting 9: [2,7,9,4] | B1 |
| After inserting 4: [2,4,7,9] | B1 |
| Final insertion shifts 9 and 7 right | B1 |
| Place 4 after 2 in the sorted prefix | B1 |
| Final answer: The sorted prefix starts with 7. Insert 2: [2,7,9,4]. Insert 9: [2,7,9,4]. Insert 4: [2,4,7,9]. The final insertion shifts 9 and 7 right before placing 4 after 2. | |
| Question 17[5 marks] | |
|---|---|
| Answer or working | Marks |
| +20 = 00010100. | B1 |
| Inverts to 11101011. | B1 |
| Adds one to obtain 11101100 for -20; accept an equivalent correct two's complement method. | B1 |
| Minimum value -128. | B1 |
| Maximum value 127. | B1 |
| Final answer: -20 = 11101100 in 8-bit two's complement (invert 00010100 to get 11101011, then add 1); the range representable is -128 to 127 | |
| Question 18[6 marks] | |
|---|---|
| Answer or working | Marks |
| a bubble sort compares and swaps adjacent items repeatedly, and the number of comparisons it needs grows very quickly as the list gets much longer | B1 |
| a list as large as 2 million records, a bubble sort would take an impractically long time to complete each night | B1 |
| a merge sort instead divides the list repeatedly and merges the sorted parts back together, which scales far better to a very large list like this | B1 |
| a merge sort does need extra memory to hold the list's sub-lists while merging, roughly equivalent to a second copy of the list | B1 |
| since the system has enough spare memory available for a full second copy, this extra memory requirement is not a practical problem here | B1 |
| valid conclusion that merge sort is the more suitable choice, since it scales far better to 2 million records and the extra memory it needs is available | B1 |
| Final answer: Merge sort is far more suitable: it scales much better than bubble sort to 2 million records, and the extra memory it needs to hold a second copy while merging is available here | |
| Question 19[6 marks] | |
|---|---|
| Answer or working | Marks |
| declares a variable to store the smallest value found so far | B1 |
| inputs the first number and checks it is not -1 before initialising smallest; handles an immediate -1 by reporting that no smallest value exists | B1 |
| uses a loop that continues to input further numbers until -1 is entered, excluding the sentinel from processing | B1 |
| inside the loop, compares each newly entered number with the current smallest value | B1 |
| updates the smallest variable whenever a newly entered number is less than the current smallest value | B1 |
| outputs the smallest value once the loop ends if at least one non-sentinel number was entered | B1 |
| Final answer: input number / if number == -1 then / print "No numbers entered; no smallest value" / else / smallest = number / input number / while number != -1 / if number < smallest then smallest = number / endif / input number / endwhile / print smallest / endif | |
| Question 20[6 marks] | |
|---|---|
| Answer or working | Marks |
| Frequent barcode lookups need efficient repeated searches | B1 |
| Halving the interval yields at most 16 checked items | B1 |
| Linear search can require 50000 checks | B1 |
| Sorted order makes elimination correct | B1 |
| Unsorted data can cause false not-found results and needs sorting or a different search | B1 |
| Other indices such as hash tables can also provide efficient exact lookups | B1 |
| Final answer: Binary search is well suited to frequent lookups on the sorted barcodes: every unsuccessful comparison halves the interval, with at most 16 checks for 50000 items. Linear search may need 50000 checks, so repeated checkout lookups favour binary search. Correct comparisons require sorted order; an unsorted list can cause it to discard the interval containing the barcode and falsely report absence. Keep order on updates or sort first; linear search works without order but is slower for this workload. Binary search is not uniquely essential: a suitable hash index can also support quick exact lookups. | |
| Question 21[6 marks] | |
|---|---|
| Answer or working | Marks |
| Insertion sort moves each key into its sorted prefix | B1 |
| Few inversions mean few shifts and work near O(n) | B1 |
| Standard merge sort divides regardless of initial order | B1 |
| Standard merge sort takes O(n log n) even for sorted input | B1 |
| Insertion sort is in-place versus usual array merge auxiliary storage | B1 |
| Recommend insertion sort with a caveat about displacement and size | B1 |
| Final answer: Usually choose insertion sort for a nearly sorted list. It inserts each item into the sorted prefix and shifts only larger items. Work is O(n + I), where I is the number of inversions, and is close to linear when displacement is small. Standard merge sort still divides and merges through O(log n) levels with O(n) work per level, taking O(n log n). Insertion sort uses constant extra storage; merge sort usually needs an auxiliary array. If a few misplaced items are far away, or the list is very large, measure actual work rather than assuming near-linear performance. | |