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

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the

n

-bit inputs as

x = a B + b

y = c B + d

, where

B = 2^{k}

and

k = ⌈ n /2 ⌉

. Compute only three recursive products:

p = a c, q = b d, r = (a - b) (c - d) .

(1)

Then the Karatsuba three-product identity gives

x y = p B^{2} + (p + q - r) B + q .

(2)

The absolute differences have at most

k

bits; multiply their magnitudes and restore the sign of

r

. Additions, subtractions and shifts cost

O (n)

bit operations. With constant-size base cases, the recurrence relation is

T (n) = 3 T (⌈ n /2 ⌉) + O (n)

, giving $O (n^{l o g_{2} 3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.

b

 0  0

Solution

 0  0

Use minimum search in a rotated distinct array, then return the cyclic predecessor of the minimum:

rotatedMaximum(A):
    n = length(A)                 # require n >= 1
    lo = 0
    hi = n - 1
    while lo < hi:
        mid = floor((lo + hi) / 2)
        if A[mid] > A[hi]:
            lo = mid + 1
        else:
            hi = mid
    return A[(lo + n - 1) mod n]

The loop invariant says that the minimum index lies in the inclusive interval. If A[mid] > A[hi], the rotation break lies to the right of mid; otherwise the segment from mid to hi is increasing and its indices after mid cannot be the minimum. Each update at least halves the interval. Distinct entries make the comparison decisive, including a completely unshifted array. The predecessor of the unique minimum is the maximum, and the one-element case returns that element. The running time is $O (lo g n)$ , with

O (1)

auxiliary space.

c

 0  0

Solution

 0  0

For fixed

a \geq 1

b > 1

and

d \geq 0

, a version of the Master theorem states that, with bounded positive base costs,

T (n) = a T (n / b) + Θ (n^{d}), p = lo g_{b} a ⟹ T (n) = ⎩ ⎨ ⎧ Θ (n^{p}), Θ (n^{p} lo g n), Θ (n^{d}), d < p, d = p, d > p .

(1)

Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.

$A$ : $T_{A} (n) = 3 T_{A} (⌈ 2 n /3 ⌉) + Θ (1)$ , hence $O (n^{l o g_{3/2} 3})$ , with exponent approximately $2.7095$ . Base cases must include $n \leq 2$ because the ceiling otherwise need not decrease.
$B$ : $T_{B} (n) = 9 T_{B} (⌈ n /3 ⌉) + O (n^{2})$ , hence $O (n^{2} lo g n)$ by comparison with the equality recurrence having $Θ (n^{2})$ overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
$C$ : $T_{C} (n) = 3 T_{C} (n - 1) + Θ (1)$ , whose expansion is a geometric series, hence $O (3^{n})$ , in fact $Θ (3^{n})$ for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.

$B$ is asymptotically fastest; $C$ is slowest. Even the quadratic-logarithmic upper bound for

B

is smaller than the tight polynomial order of

A

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

a

Solution

b

Solution

c

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

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

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion