Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8

The three answers, in source order, are:

The change of variable in the third case handles the additive shift in the recursive argument exactly; it is not an unjustified deletion of the +1. These Big theta notation conclusions use the usual admissible input sizes, or bounded integer rounding of subproblem sizes.

$\Theta (n^{{\log }_{2}7})$, approximately $\Theta (n^{2.8074})$, arithmetic operations. Strassen's algorithm replaces an $n\times n$ matrix multiplication by seven products of half-size blocks and a constant number of block additions and subtractions. ConsequentlyThe Master theorem applies with $a=7$, $b=2$, since $2<{\log }_{2}7$. Padding an arbitrary matrix dimension to the next power of two changes the dimension by less than a factor of two and preserves this asymptotic bound. The cost model counts scalar arithmetic as constant time; it is not a bit-complexity claim for arbitrarily large integer entries.

Let $q=n/k$. After each linear-time selection algorithm and partition, exactly $k$ elements are removed, so the successive input sizes are $n,n-k,\dots ,k$. Thus the standard efficient implementation takesHere selection can use median of medians for worst-case linear time; a suitable randomised linear-time selection routine gives the same bound in expectation. Merely sorting each remaining array would introduce an avoidable logarithmic factor.

Recursively partition into equal halves by rank, keeping the selected median in the lower half:All elements are distinct, so both halves have exactly $|A|/2$ elements. Since $|A|/k$ remains a power of two, every internal split occurs at a rank divisible by $k$.

For correctness, the desired ranks in the lower half are $k,2k,\dots ,|A|/2$. In the upper half they are the same local multiples of $k$, shifted by $|A|/2$. These are exactly all desired global ranks. At a leaf of size $k$, its maximum is its sole requested local rank. Induction therefore proves that the output contains every requested order statistic, in increasing order, including the original maximum. There is no separate internal-node output of p, which would duplicate a rank already supplied by the lower subtree.

Use a worst-case linear-time selection algorithm and linear partitioning. The divide-and-conquer algorithm hasThere are ${\log }_2(n/k)$ internal levels, each with total work $\Theta (n)$, and $n/k$ leaves with total work $\Theta (n)$. Since the source assumes $n/k\ge 2$, the running time isThis is multiselection by balanced rank partitioning. In-place selection and partitioning can use the original array; the output has $n/k$ values. The multiselection recursion has depth $O(\log (n/k))$; the selection routine contributes its own auxiliary storage.