Revision Library

revisionlibrary.co.uk

GCSE · Computer Science

P2.1 Algorithms

OCR J277 · Calculators not allowed · about 100 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

Computational thinking involves breaking down complex problems using specific techniques before an algorithm is designed.

(a)Define what is meant by 'decomposition' when designing a solution to a problem.(2)

(b)Define what is meant by 'abstraction' when designing an algorithm.(2)

(Total for Question 1 is 4 marks)

A systems analyst is designing a new algorithm to calculate a student's average test score.

(a)State two ways in which an algorithm can be represented, other than by using a written description in ordinary sentences.(2)

(b)Identify one advantage of using a flowchart, rather than pseudocode, to represent an algorithm.(1)

(Total for Question 2 is 3 marks)

Flowcharts use standard symbol shapes to represent different steps in an algorithm.

(a)State the flowchart symbol shape used to represent a decision.(1)

(b)State the flowchart symbol shape used to represent an input or output step.(1)

(c)State the flowchart symbol shape used to represent the start or end (terminator) of an algorithm.(1)

(Total for Question 3 is 3 marks)

A programmer writes the following pseudocode, using the OCR Exam Reference Language.

total <- 0
FOR i <- 1 TO 5
    total <- total + i
NEXT i
OUTPUT total

(a)Complete a trace table for this algorithm, showing the value of i and total at the end of each pass through the loop.(4)

(b)State the value output by the algorithm.(1)

(Total for Question 4 is 5 marks)

A programmer writes the following pseudocode.

count <- 0
num <- 18
WHILE num > 1
    num <- num / 2
    count <- count + 1
ENDWHILE
OUTPUT count

(a)Complete a trace table showing the values of num and count each time the loop body executes.(5)

(b)State the number of times the loop body executes.(1)

(Total for Question 5 is 6 marks)

An array called scores contains the values [55, 62, 48, 71, 60, 39] at indices 0 to 5.

(a)Describe how a linear search algorithm would locate the value 71 in this array, stating the number of comparisons needed.(3)

(b)State one disadvantage of using a linear search, rather than a binary search, on a large, sorted dataset.(1)

(Total for Question 6 is 4 marks)

A sorted array called nums, in ascending order, contains: [3, 9, 14, 22, 27, 35, 41, 48, 55, 62] at indices 0 to 9.

(a)State the condition that must be met before a binary search can be used on this array.(1)

(b)A binary search uses mid <- (lower + upper) DIV 2 to find the middle index at each step. Complete a trace table to show the values of lower, upper and mid, and the outcome of each comparison, as a binary search locates the value 41.(5)

(c)State the number of comparisons made to find the value using binary search in part (b), and explain why this is fewer than a linear search would need in the worst case for this array.(2)

(Total for Question 7 is 8 marks)

An array contains the values [8, 3, 6, 1, 9], which need to be sorted into ascending order using a bubble sort that compares and swaps adjacent items.

(a)Show the state of the array after each comparison in the first full pass of the bubble sort.(4)

(b)State the maximum number of full passes a bubble sort would need to fully sort a list of 5 items.(1)

(Total for Question 8 is 5 marks)

An array contains the values [5, 2, 9, 1, 6], to be sorted into ascending order using insertion sort.

(a)Complete a trace table to show the state of the array after each new element has been inserted into its correct position.(4)

(b)Insertion sort is described as an 'in-place' sorting algorithm. State what is meant by an in-place algorithm.(1)

(Total for Question 9 is 5 marks)

Merge sort is an example of a 'divide and conquer' algorithm.

(a)Describe how merge sort would sort a list of 8 unsorted numbers, referring to both the dividing stage and the merging stage.(4)

(b)State one advantage of merge sort over bubble sort when sorting a very large dataset.(1)

(Total for Question 10 is 5 marks)

An array called scores has 10 elements, at indices 0 to 9.

(a)Write an algorithm, using pseudocode, that finds and outputs the largest value in the array scores.(4)

(Total for Question 11 is 4 marks)

A programmer needs to validate user input.

(a)Write an algorithm, using pseudocode, that repeatedly asks the user to input a number, and only accepts a value between 1 and 10 inclusive, then outputs the message 'Valid' once an acceptable value has been entered.(4)

(Total for Question 12 is 4 marks)

A programmer intends the following pseudocode to output the sum of all even numbers between 1 and 20 inclusive, but it contains errors.

total <- 0
FOR i <- 1 TO 20
    IF i / 2 = 0 THEN
        total <- total + 1
    ENDIF
NEXT i
OUTPUT total

(a)Identify two errors in the algorithm above which mean it does not correctly output the sum of all even numbers between 1 and 20.(2)

(b)Rewrite the algorithm with these errors corrected.(2)

(Total for Question 13 is 4 marks)

A programmer compares linear search and binary search on datasets of different sizes.

(a)Explain why the difference in efficiency between linear search and binary search becomes more significant as the size of the dataset increases.(3)

(b)Calculate the maximum number of comparisons required by a binary search on a sorted list of 1024 items.(2)

(Total for Question 14 is 5 marks)

An array called numbers contains 6 elements, at indices 0 to 5.

(a)Write an algorithm, using pseudocode, for a bubble sort that sorts the array numbers into ascending order. Your algorithm should use nested loops.(6)

(Total for Question 15 is 6 marks)

A school is choosing which sorting algorithm to use to sort a list of 5000 student records by surname. The list is already nearly in alphabetical order, because it was exported from an existing system that keeps records mostly sorted. Discuss which of bubble sort, insertion sort and merge sort would be most suitable for this task, justifying your answer by referring to how each algorithm works and how efficient it is.

(Total for Question 16 is 6 marks)

A student is asked to write a program to help organise a school's sports day.

(a)State two sub-problems the student could identify by decomposing the problem 'organise a school's sports day'.(2)

(b)Explain, using this scenario, what is meant by 'abstraction' when designing an algorithm.(2)

(Total for Question 17 is 4 marks)

A programmer writes the following pseudocode.

FUNCTION doubleIfEven(num)
    IF num MOD 2 = 0 THEN
        RETURN num * 2
    ELSE
        RETURN num
    ENDIF
ENDFUNCTION

total <- 0
FOR i <- 1 TO 4
    total <- total + doubleIfEven(i)
NEXT i
OUTPUT total

(a)Complete a trace table to show the value returned by doubleIfEven for each value of i, and the running value of total.(4)

(b)State the value output by the program.(1)

(Total for Question 18 is 5 marks)

An algorithm uses a FOR loop that runs from 0 to 15 inclusive, using a variable called cycle to count each iteration.

(a)State the 8-bit binary representation of the maximum value that cycle reaches.(1)

(b)Convert the maximum value of cycle to hexadecimal.(1)

(c)Explain why programmers often use hexadecimal, rather than binary, when reading values from trace tables or debugging output.(2)

(Total for Question 19 is 4 marks)

Two algorithms both correctly sort the same array. One algorithm sorts the array in place, while the other creates a new array during sorting.

(a)State which of these two algorithms is likely to use more memory, and explain your reasoning.(2)

(Total for Question 20 is 2 marks)

Mark scheme · P2.1 Algorithms

Question 1

(a) B1 identifies decomposition as breaking a large or complex problem down (oe)
(a) B1 into smaller, more manageable sub-problems that are easier to solve individually (oe)
(a) Answer: Decomposition is the process of breaking a large, complex problem down into a series of smaller, more manageable sub-problems.
(b) B1 identifies abstraction as removing or ignoring unnecessary detail (oe)
(b) B1 so that only the information relevant to solving the problem is kept/used (oe)
(b) Answer: Abstraction is the process of removing unnecessary detail from a problem so that only the information relevant to solving it remains.

Question 2

(a) B1 flowchart
(a) B1 pseudocode (accept structured English)
(a) Answer: Flowchart; pseudocode.
(b) B1 a valid advantage, e.g. it shows the flow/structure/logic of the algorithm visually, making it easier for people who cannot yet read code to follow (oe)
(b) Answer: A flowchart shows the structure and flow of the algorithm visually, so it can be understood by people without programming knowledge.

Question 3

(a) B1 diamond (accept rhombus)
(a) Answer: Diamond (rhombus).
(b) B1 parallelogram
(b) Answer: Parallelogram.
(c) B1 oval/rounded rectangle (terminator)
(c) Answer: Oval (rounded rectangle).

Question 4

(a) B1 i = 1, total = 1
(a) B1 i = 2, total = 3
(a) B1 i = 3, total = 6; i = 4, total = 10
(a) B1 i = 5, total = 15 (all five rows correct, cao)
(a) Answer: i: 1,2,3,4,5 -> total: 1,3,6,10,15
(b) B1 15 (cao)
(b) Answer: 15

Question 5

(a) B1 num = 9, count = 1
(a) B1 num = 4.5, count = 2
(a) B1 num = 2.25, count = 3
(a) B1 num = 1.125, count = 4
(a) B1 num = 0.5625, count = 5 (all five rows correct, cao)
(a) Answer: num: 9, 4.5, 2.25, 1.125, 0.5625 / count: 1,2,3,4,5
(b) B1 5 (cao)
(b) Answer: 5

Question 6

(a) B1 starts at index 0 and compares each item in turn to the target value (71) (oe)
(a) B1 moves to the next index each time the current item does not match, continuing until a match is found (oe)
(a) B1 correctly states 4 comparisons are needed (55, 62, 48, 71 - cao)
(a) Answer: The linear search checks index 0 (55), index 1 (62), index 2 (48), then index 3 (71), which matches. 4 comparisons are needed.
(b) B1 a linear search can require checking every item in the worst case, so it is much slower/less efficient on large datasets than a binary search (oe)
(b) Answer: A linear search may need to check every item in the dataset, making it much slower than a binary search for large, sorted data.

Question 7

(a) B1 the data/array must already be sorted (into ascending or descending order) (oe)
(a) Answer: The array must be sorted (in ascending or descending order).
(b) B1 step 1: lower=0, upper=9, mid=4, nums[4]=27, 41>27 so search upper half (lower<-5)
(b) B1 step 2: lower=5, upper=9, mid=7, nums[7]=48, 41<48 so search lower half (upper<-6)
(b) B1 step 3: lower=5, upper=6, mid=5, nums[5]=35, 41>35 so search upper half (lower<-6)
(b) B1 step 4: lower=6, upper=6, mid=6, nums[6]=41, value found
(b) B1 all four steps correct and consistent with each other (cao)
(b) Answer: Step1: mid=4 (27), search upper. Step2: mid=7 (48), search lower. Step3: mid=5 (35), search upper. Step4: mid=6 (41), found at index 6.
(c) B1 4 comparisons were made (ft from part b)
(c) B1 binary search eliminates half of the remaining items at each step, whereas a linear search worst case would need to check all 10 items one at a time (oe)
(c) Answer: 4 comparisons; binary search halves the remaining data each time, so it needs far fewer comparisons than the worst-case 10 needed by a linear search.

Question 8

(a) B1 compare 8 and 3: swap, giving [3, 8, 6, 1, 9]
(a) B1 compare 8 and 6: swap, giving [3, 6, 8, 1, 9]
(a) B1 compare 8 and 1: swap, giving [3, 6, 1, 8, 9]
(a) B1 compare 8 and 9: no swap needed, array remains [3, 6, 1, 8, 9] (cao)
(a) Answer: [3,8,6,1,9] -> [3,6,8,1,9] -> [3,6,1,8,9] -> [3,6,1,8,9] (end of pass 1)
(b) B1 4 (n - 1 passes for n = 5 items, cao)
(b) Answer: 4

Question 9

(a) B1 insert 2: [2, 5, 9, 1, 6]
(a) B1 insert 9: [2, 5, 9, 1, 6] (unchanged, as 9 is already greater than 5)
(a) B1 insert 1: [1, 2, 5, 9, 6]
(a) B1 insert 6: [1, 2, 5, 6, 9] (cao)
(a) Answer: [2,5,9,1,6] -> [2,5,9,1,6] -> [1,2,5,9,6] -> [1,2,5,6,9]
(b) B1 it sorts the data within the original data structure/array, without needing a significant amount of additional memory/another array (oe)
(b) Answer: An in-place algorithm sorts the data within its original array, without needing extra memory for a separate data structure.

Question 10

(a) B1 the list is repeatedly split in half (divided) until each sub-list contains only one item (oe)
(a) B1 a sub-list containing a single item is considered already sorted (oe)
(a) B1 adjacent sub-lists are then merged back together, comparing the front item of each sub-list (oe)
(a) B1 the smaller/next item is placed into the new merged list, and this repeats until all sub-lists have been merged into one fully sorted list (oe)
(a) Answer: The list is repeatedly divided in half until each sub-list has one item, then pairs of sub-lists are merged back together in order, comparing front items, until one fully sorted list remains.
(b) B1 merge sort is more efficient/faster for large datasets, needing far fewer comparisons than bubble sort (oe)
(b) Answer: Merge sort is significantly more efficient than bubble sort for large datasets, requiring many fewer comparisons overall.

Question 11

(a) M1 initialises a variable to the first element of the array, e.g. max <- scores[0]
(a) M1 uses a loop to iterate through the remaining elements of the array, e.g. FOR i <- 1 TO 9
(a) M1 compares each element to the current maximum and updates it if a larger value is found, e.g. IF scores[i] > max THEN max <- scores[i]
(a) A1 outputs the maximum value after the loop has finished (any correct logic; ignore minor syntax errors)

(a) Answer:

max <- scores[0]
FOR i <- 1 TO 9
    IF scores[i] > max THEN
        max <- scores[i]
    ENDIF
NEXT i
OUTPUT max

Question 12

(a) M1 uses an INPUT statement to accept a value from the user
(a) M1 uses a loop that repeats while/until the value is out of range, e.g. REPEAT ... UNTIL
(a) M1 correct condition combining both bounds using an appropriate logical operator, e.g. num ≥ 1 AND num ≤ 10
(a) A1 outputs 'Valid' once the loop ends (any correct logic; ignore minor syntax errors)

(a) Answer:

REPEAT
    INPUT num
UNTIL num >= 1 AND num <= 10
OUTPUT "Valid"

Question 13

(a) B1 the condition i / 2 = 0 does not correctly test whether i is even (it should use MOD, e.g. i MOD 2 = 0)
(a) B1 the algorithm adds 1 instead of adding the value of i itself (should be total <- total + i)
(a) Answer: Error 1: the condition should test i MOD 2 = 0, not i / 2 = 0. Error 2: the algorithm should add i (total <- total + i), not add 1.
(b) M1 corrects the condition to test for an even number, e.g. i MOD 2 = 0
(b) A1 corrects the addition to total <- total + i, giving a fully correct algorithm (any correct logic; ignore minor syntax errors)

(b) Answer:

total <- 0
FOR i <- 1 TO 20
    IF i MOD 2 = 0 THEN
        total <- total + i
    ENDIF
NEXT i
OUTPUT total

Question 14

(a) B1 a linear search checks items one at a time, so its worst-case number of comparisons is directly proportional to the number of items, n (oe)
(a) B1 a binary search halves the remaining data at each step, so its worst-case number of comparisons grows much more slowly, proportional to log2(n) (oe)
(a) B1 as n grows very large, linear search's comparisons increase proportionally while binary search's increase only logarithmically, so the performance gap widens (oe)
(a) Answer: Linear search's worst-case comparisons grow directly with the size of the dataset, while binary search's grow only logarithmically (halving each time), so binary search becomes proportionally far faster as the dataset gets larger.
(b) M1 recognises that 1024 = 2¹⁰, or shows repeated halving of 1024 down to 1
(b) A1 10 (cao)
(b) Answer: 10

Question 15

(a) M1 outer loop that repeats a suitable number of times for the array size, e.g. FOR i <- 0 TO 4
(a) M1 inner loop that iterates through adjacent pairs of elements, e.g. FOR j <- 0 TO 4 - i
(a) M1 correct comparison of adjacent elements, e.g. IF numbers[j] > numbers[j + 1] THEN
(a) M1 uses a temporary variable to hold one value during the swap, e.g. temp <- numbers[j]
(a) M1 both assignments of the swap are correct, e.g. numbers[j] <- numbers[j+1] and numbers[j+1] <- temp
(a) A1 overall algorithm correctly sorts the array into ascending order with no logic errors (any correct logic; ignore minor syntax errors)

(a) Answer:

FOR i <- 0 TO 4
    FOR j <- 0 TO 4 - i
        IF numbers[j] > numbers[j + 1] THEN
            temp <- numbers[j]
            numbers[j] <- numbers[j + 1]
            numbers[j + 1] <- temp
        ENDIF
    NEXT j
NEXT i

Question 16

Level 3 (5-6): A detailed, coherent discussion that accurately describes how at least two of the algorithms work and links this to their efficiency. The nearly-sorted nature of the data is used to justify a clear, well-reasoned recommendation. Technical terminology is used accurately throughout.
Level 2 (3-4): Some relevant discussion of how the algorithms work, with limited or partial reference to efficiency or to the nearly-sorted nature of the data. A conclusion is given but is only partially justified. Technical terminology is used with some inaccuracy.
Level 1 (1-2): Basic, isolated statements are made about one or more of the algorithms, with little or no linking between ideas. Little or no reference to efficiency or to the nearly-sorted data. Conclusion, if present, is unjustified.
Level 0 (0): No creditable content.
Indicative content:
- Bubble sort repeatedly compares and swaps adjacent items across multiple passes; it is inefficient (many comparisons/swaps, roughly proportional to n^2) for a list of 5000 records, even if nearly sorted, because standard versions still make many passes.
- Insertion sort builds up a sorted list by taking each item and inserting it into its correct position among the items already sorted; on data that is already nearly sorted, very few shifts are needed for each item, so insertion sort performs close to its best case and can be very efficient here.
- Merge sort divides the list repeatedly and then merges the sorted sub-lists back together; it is consistently efficient (proportional to n log n) regardless of the initial order of the data, but requires extra memory for the sub-lists and is more complex to implement than the other two.
- A well-justified conclusion could recommend insertion sort, because the nearly-sorted nature of the data plays to its strength of few shifts, or merge sort, because it guarantees good performance for a large dataset of 5000 records regardless of order; either conclusion should be credited if it is properly justified with reference to the scenario.

Question 17

(a) B1 any valid sub-problem, e.g. scheduling the order/timing of events
(a) B1 any different valid sub-problem, e.g. assigning students to house teams, or recording race results, or allocating equipment
(a) Answer: Example sub-problems: scheduling the events; recording and ranking race results.
(b) B1 abstraction means removing details that are not relevant to solving the problem (oe)
(b) B1 a relevant example applied to the scenario, e.g. ignoring the weather forecast and focusing only on event times and participant lists (oe)
(b) Answer: Abstraction means ignoring details that are not needed to solve the problem, such as ignoring the weather forecast for the day and focusing only on the information needed to schedule events and record results.

Question 18

(a) B1 i = 1: doubleIfEven returns 1, total = 1
(a) B1 i = 2: doubleIfEven returns 4, total = 5
(a) B1 i = 3: doubleIfEven returns 3, total = 8
(a) B1 i = 4: doubleIfEven returns 8, total = 16 (cao)
(a) Answer: i=1: returns 1, total=1. i=2: returns 4, total=5. i=3: returns 3, total=8. i=4: returns 8, total=16.
(b) B1 16 (ft from part a, cao)
(b) Answer: 16

Question 19

(a) B1 00001111 (cao)
(a) Answer: 00001111
(b) B1 0F (accept F, cao)
(b) Answer: 0F
(c) B1 hexadecimal is much more compact/shorter than binary, so it is quicker and easier for a human to read (oe)
(c) B1 each hexadecimal digit represents exactly 4 bits, so converting between binary and hexadecimal is quick and there is less chance of error than reading long binary strings (oe)
(c) Answer: Hexadecimal is far more compact than binary and easier for humans to read; each hex digit maps to exactly 4 bits, making conversion quick and reducing the chance of misreading long binary strings.

Question 20

(a) B1 the algorithm that creates a new array (e.g. merge sort) is likely to use more memory
(a) B1 because it needs additional storage for the new array as well as the original, whereas an in-place algorithm reuses the original array's memory (oe)
(a) Answer: The algorithm that creates a new array uses more memory, because it needs space for both the new array and the original, whereas an in-place algorithm reuses the same memory throughout.

Algorithms - Worksheets, Questions and Revision

P2.1 Algorithms

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

Question 14

Question 15

Question 16

Question 17

Question 18

Question 19

Question 20