OCR A-Level Computer Science: Algorithms

The following graph and data were written for this exercise.

A delivery network is modelled as a directed weighted graph with six locations A to F. Each edge gives the one-way travel cost between two locations. The graph is supplied as an adjacency table (there is no diagram):

From	To	Weight
A	B	4
A	C	2
B	C	1
B	D	5
C	B	1
C	D	8
C	E	10
D	E	2
D	F	6
E	F	3

(a) Trace Dijkstra's shortest-path algorithm starting from source A. Show the table of tentative (best-so-far) distances to every node as the algorithm runs, and state the order in which nodes are finalised (settled), continuing until the destination F is settled. [6 marks]

(b) State the shortest path from A to F and its total cost. [2 marks]

(c) Explain how A* search improves on Dijkstra's algorithm by using an admissible heuristic. Your answer must state what "admissible" means and why admissibility guarantees A* still returns the optimal path. [4 marks]

The following algorithm was written for this exercise.

The recursive function below raises a number to a non-negative integer power:

// OCR-style pseudocode
function power(base, exp)
    if exp == 0 then
        return 1
    else
        return base * power(base, exp - 1)
    endif
endfunction

The function is called as power(3, 4).

(a) Trace the chain of recursive calls for power(3, 4). Show, as a table, each call that is made (the winding phase) and the value each call returns as the recursion unwinds. [5 marks]

(b) State the value finally returned by power(3, 4). [1 mark]

(c) Identify the base case and the general (recursive) case of this function, and give one drawback of using recursion rather than an equivalent iterative (loop-based) solution. [3 marks]

The following algorithm was written for this exercise.

The procedure below operates on an array arr of n elements:

// OCR-style pseudocode
procedure scan(arr, n)
    for i = 0 to n - 1        // outer loop
        j = n
        while j > 1           // inner loop: j is halved each time
            j = j DIV 2
            print(arr[i])
        endwhile
    next i
endprocedure

(a) Derive the worst-case time complexity of scan using Big-O notation. You must show how many times the print statement executes as a function of n, justifying the order you give. [3 marks]

(b) A different algorithm solves the same task in $O(n^2)$O(n2) time. Compare the scalability of scan against this $O(n^2)$O(n2) algorithm for large n, justifying your comparison with reference to how each grows as n increases. [3 marks]

The following data were written for this exercise.

An insertion sort sorts an array into ascending order. Starting from the second element, it takes each element in turn (the key) and inserts it into its correct position within the already-sorted portion to its left, shifting larger elements one place to the right to make room.

The starting array is:

[9, 5, 7, 2, 11, 4]

(a) Trace the first two passes of the insertion sort (i.e. inserting the element at index 1, then the element at index 2). For each pass, state the key being inserted and the state of the whole array after that pass, as a table. [3 marks]

(b) After pass k of an insertion sort, which portion of the array is guaranteed to be sorted, and why is it not yet guaranteed to be in its final positions? [2 marks]

In the study of computational complexity, problems are classified as either tractable or intractable.

Explain the difference between a tractable and an intractable problem, with explicit reference to polynomial and exponential time complexity. Give one example of a tractable problem and one example of an intractable problem. [4 marks]

Some problems are non-computable: no algorithm can ever solve them. The best-known example is the Halting problem.

(a) State what the Halting problem asks, and what Alan Turing proved about it. [2 marks]

(b) Give one consequence of the Halting problem for what computers can or cannot do. [1 mark]