OCR GCSE Computer Science: Algorithms

A music-streaming app stores the play counts of songs in a list. Sometimes the list is held in ascending sorted order and sometimes it is unsorted. A developer must decide whether to use a linear search or a binary search to find a particular play count.

Discuss how a linear search and a binary search each work, and explain how the developer should choose between them for this app. You should refer to whether the data is sorted, the size of the list, and the efficiency of each algorithm. (6 marks)

The following list was written for this exercise. A binary search is used to find the value 31 in the sorted list below. Array indices start at 0, and the midpoint is calculated as mid = (low + high) DIV 2 (integer division).

[4, 9, 15, 22, 31, 38, 47, 56, 60]

(a) Copy and complete a trace table showing the values of low, high and mid, the value of list[mid], and the action taken at each step, until 31 is found. (3 marks)

(b) State the total number of comparisons with list[mid] that the binary search made to find 31. (1 mark)

The following list was written for this exercise. A bubble sort is applied to the list below. The sort compares adjacent items from left to right and swaps them if the left item is greater than the right item.

[7, 3, 9, 2]

(a) Write out the state of the list after each swap during the first complete pass through the list. (2 marks)

(b) State which value is guaranteed to be in its correct final position at the end of the first pass, and explain why. (1 mark)

A program needs to find the largest value in an array of numbers called scores. The array has at least one element. A student starts to write the algorithm in OCR Exam Reference Language but has left two gaps.

largest = scores[0]
for i = 1 to scores.length - 1
    if scores[i] > ............(1).......... then
        ............(2)..........
    endif
next i
print(largest)

(a) State what should replace gap (1) and gap (2) so that the algorithm correctly finds the largest value. (2 marks)

(b) Explain why the loop starts at i = 1 rather than i = 0. (1 mark)

Computational thinking uses three key techniques: decomposition, abstraction and algorithmic thinking.

Describe what is meant by decomposition and what is meant by abstraction, giving one example of how each could be applied when planning a program to manage a school library. (2 marks)

A binary search can only be carried out on data that meets one particular condition.

State the condition that the data must meet before a binary search can be used. (1 mark)