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

A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With $a$ equally sized subproblems of size approximately $n/b$ and nonrecursive work $f(n)$, its recurrence relation has the form $T(n)=aT(n/b)+f(n)$, with constant-size base cases, $a\ge 1$ and $b>1$.

Write $p={\log }_{b}a$. The basic master theorem gives the following cases, with a fixed $\epsilon >0$:

For the common extended middle case, $f(n)=\Theta (n^p{\log }^{k}n)$ with fixed $k\ge 0$ gives $T(n)=\Theta (n^p{\log }^{k+1}n)$. A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.

For an ascending sorted array, maintain a candidate interval $[\ell ,r]$ initially containing every index. Compare the target with the middle entry at $m=\lfloor (\ell +r)/2\rfloor$. Equality returns $m$; if the target is smaller, replace $r$ by $m-1$; if larger, replace $\ell$ by $m+1$. An empty interval reports absence.

The loop invariant is that any target occurrence still possible lies inside the candidate interval. Sortedness justifies discarding the appropriate half after each unequal comparison. The interval length decreases to at most half its previous length, establishing termination and correctness. After $t$ unsuccessful comparisons there are at most $n/2^t$ candidates, so at most $\lfloor {\log }_{2}n\rfloor +1$ comparisons suffice for $n\ge 1$. Each iteration uses constant work on a random-access array. Thus binary search takes $O(\log (n+1))$ running time, conventionally written $O(\log n)$ for nontrivial input sizes. Empty input is handled in constant time.

Assume ascending sorted arrays; descending storage can be accessed in reverse index order without copying. Among $2n$ entries, the requested rank is $k=n+1$ in ascending order, not $n$. Repeated values occupy repeated ranks.

Choose $i$ entries from the first array and $j=k-i$ from the second, using their prefixes. The feasible range is $\max (0,k-n)\le i\le \min (n,k)$. Write $A_L=A[i]$, $A_R=A[i+1]$, and similarly $B_L,B_R$ at $j$, with missing left endpoints replaced by $-\infty$ and missing right endpoints by $+\infty$. These are conceptual sentinels, not extra stored entries.

Use binary search over the feasible values of $i$:

For correctness, in the last case every left entry is no greater than every right entry, and exactly $k$ entries lie on the left. Their maximum is therefore the $k$-th smallest entry. The failed inequalities are monotone in the searched index: increasing $i$ raises the $A$ boundary and decreases the $B$ boundary, so it cannot repair $A_L>B_R$; the other case is symmetric. A partition of the first $k$ entries of a merged ordering supplies an admissible solution, including ties. Each step halves an interval with at most $n+1$ choices, giving $O(\log (n+1))$ running time and $O(1)$ auxiliary space. This is a two-sorted-array order statistic without constructing the merged array.

If coordinate $j$ is not an essential variable of a function, changing that coordinate alone never changes the output, for any values of the other coordinates. Take two inputs with the same $i$-th coordinate. Change their other coordinates one at a time to transform the first input into the second. Every such change is inessential, so all intermediate outputs are equal.

Define $f_i(t)=f(1,\dots ,1,t,1,\dots ,1)$, with $t$ in position $i$. The preceding argument gives $f(x_1,\dots ,x_n)=f_i(x_i)$. Since $i$ is essential, $f_i$ is nonconstant. The conclusion depends on the full “for every context” negation of essentiality, not merely on testing a coordinate at one selected input.

If $n=1$, return its sole index without a query. Otherwise first evaluate $f(t,t,\dots ,t)$ for $t=1,\dots ,d$ until two different outputs are found. Part i says these outputs are precisely $f_i(t)$, so two values $a,b$ with $f_i(a)\ne f_i(b)$ must exist. This uses at most $d$ calls to the function-evaluation oracle.

Maintain a candidate index set $S$, initially all indices. Split $S$ into two nearly equal pieces and choose one, $H$. Query the input that is $b$ on $H$ and $a$ everywhere else. Its output equals $f_i(b)$ exactly when $i\in H$, and otherwise equals $f_i(a)$. Retain the indicated half and repeat until one index remains.

The loop invariant is $i\in S$, and the witness outputs keep each test unambiguous. There are at most $\lceil {\log }_{2}n\rceil$ splitting queries. The total is at most $d+\lceil {\log }_{2}n\rceil$ evaluations, which is $O(d\log n)$ for $n\ge 2$, and in fact a stronger additive bound. Only oracle calls are being counted; explicitly constructing each query vector can require $O(n)$ ordinary work. This is identification of a unique essential variable.

Restrict the unknown function to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all $n$ possibilities. A binary decision tree of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore $q\ge \lceil {\log }_{2}n\rceil =\Omega (\log n)$. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed $d$.