AQA A-Level Computer Science: Algorithms

The following algorithm and data were written for this exercise.

A programmer implements binary search to locate a value in a sorted array. The pseudocode is:

FUNCTION binarySearch(arr, n, target)
    low = 0
    high = n - 1
    WHILE low <= high
        mid = (low + high) DIV 2
        IF arr[mid] = target THEN
            RETURN mid
        ELSE IF target < arr[mid] THEN
            high = mid - 1
        ELSE
            low = mid + 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

The function is called on the sorted array below (indices 0 to 10), with target = 72:

Index	0	1	2	3	4	5	6	7	8	9	10
Value	4	11	18	27	33	46	59	68	72	85	97

(a) Complete a trace table showing the value of low, high, mid and arr[mid] on each iteration of the WHILE loop until the function returns. [6 marks]

(b) State the value returned by the function, and state how many comparisons of target against an array element were made to reach it. [2 marks]

(c) State the worst-case time complexity of binary search using Big-O notation, and justify it by reference to how the algorithm behaves as the array size n grows. [4 marks]

The following algorithm and data were written for this exercise.

The merge procedure is the heart of merge sort: it combines two already-sorted lists, left and right, into a single sorted list result by repeatedly taking the smaller of the two front elements. Three lines have been replaced by the labels (L1), (L2) and (L3):

FUNCTION merge(left, right)
    result = []
    i = 0
    j = 0
    WHILE i < LENGTH(left) AND j < LENGTH(right)
        IF left[i] <= right[j] THEN
            APPEND left[i] TO result
            (L1)                       # advance the left pointer
        ELSE
            APPEND right[j] TO result
            (L2)                       # advance the right pointer
        END IF
    END WHILE
    (L3)                               # deal with whichever list still has elements
    RETURN result
END FUNCTION

(a) State the line of code that should replace each of (L1) and (L2). [2 marks]

(b) Explain in words what step (L3) must do, and why it is needed. [2 marks]

(c) Using the completed algorithm, trace the merge of left = [12, 25, 40, 55] and right = [9, 18, 33, 60, 71]. Show, for each comparison, which element is taken and the contents of result afterwards, as a table. [4 marks]

(d) State the final merged list. [1 mark]

The following algorithm was written for this exercise.

Consider the procedure below, which operates on an array arr of n elements:

PROCEDURE process(arr, n)
    FOR i = 0 TO n - 1
        FOR j = 0 TO i
            OUTPUT arr[i], arr[j]
        END FOR
    END FOR
END PROCEDURE

(a) Derive the worst-case time complexity of process using Big-O notation. Show how you count the number of times the OUTPUT statement executes as a function of n. [3 marks]

(b) A second algorithm performs the same task in $O(n \log n)$O(nlogn) time. Determine which algorithm scales better for large datasets, and justify your answer with reference to how each grows as n increases. [3 marks]

The following algorithm and data were written for this exercise.

A bubble sort compares each adjacent pair in turn and swaps them if the left element is the larger. One pass of the inner loop is shown:

FOR j = 0 TO n - 2
    IF arr[j] > arr[j + 1] THEN
        SWAP arr[j], arr[j + 1]
    END IF
END FOR

The starting array is [7, 2, 9, 4, 1, 6] (so n = 6).

(a) Trace the first complete pass of the inner loop. For each value of j, give the comparison made, whether a swap occurs, and the state of the array afterwards, as a table. [3 marks]

(b) State the array after this first pass, and identify which element is now guaranteed to be in its final sorted position. Explain briefly why. [2 marks]

A student suggests that the best way to compare two algorithms is simply to run both on a laptop and time them with a stopwatch.

Explain why computer scientists instead measure an algorithm's efficiency asymptotically, using Big-O notation, rather than by timing the code. [4 marks]

The following five orders of time complexity each describe how an algorithm's running time grows with input size n:

$O(n^2), \quad O(1), \quad O(2^n), \quad O(n), \quad O(\log n)$O(n2),O(1),O(2n),O(n),O(logn)

(a) Order these five complexity classes from most efficient (slowest-growing) to least efficient (fastest-growing) for large n. [2 marks]

(b) State which one of these classes is considered intractable, and give a one-line reason. [1 mark]