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

For the first recurrence relation, the master theorem compares $n^2$ with $n^{{\log }_{2}6}$. Since $2<{\log }_{2}6$, the recursive leaves dominate and the answer is $\Theta (n^{{\log }_{2}6})$. More explicitly, the work at depth $j$ is $n^2(6/4{)}^j$, a growing geometric series that stops at depth ${\log }_{2}n-O(1)$, where its sum has that order.

For the second recurrence relation, each step subtracts two and adds one until reaching a base case. For integral $n>4$ there are $\lceil (n-4)/2\rceil$ steps, so $T(n)=1+\lceil (n-4)/2\rceil$ and the answer is $\Theta (n)$.

The third set of printed requirements is inconsistent. The specified base values and its recurrence relation give $T(n)=1$ identically, as strong induction immediately verifies: $4\cdot 1-4\cdot 1+1=1$. In particular $T(8)=1$, while the extra condition demands $T(8)>2T(4)=2$. Thus no function satisfies all the printed conditions. Dropping that extra inequality gives $\Theta (1)$.

The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put $U_j=T(2^j)$. Its equation has the general formbecause $U_j-1$ has characteristic equation $(r-2{)}^2=0$. The printed values $U_1=U_2=1$ force $A=B=0$. With suitably different initial values, the condition $U_j>2U_{j-1}$ for arbitrarily large $j$ instead requires $B{2}^j-1>0$, hence $B>0$ and $U_j=\Theta (j{2}^j)$, or $T(n)=\Theta (n\log n)$. That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.

Maintain the two largest entries of each segment, counting repeated values as separate entries. A singleton returns its value and a sentinel $-\infty$ for its missing runner-up. Split a longer segment into two nonempty halves, recursively obtain $(m_L,s_L)$ and $(m_R,s_R)$, and combine them byFor example, an implementation on an indexed sequence can use:The result is top2(0,n). The global maximum is one of the two child maxima. Once its side is identified, the global second maximum is either that side's runner-up or the other side's maximum; the displayed formula exhausts these possibilities. This proves the divide-and-conquer algorithm by induction on segment length. There are $n$ leaves and $n-1$ constant-cost combinations, so its time complexity is $\Theta (n)$, with $O(\log n)$ recursive stack space for balanced splits. A Maybe value can replace the formal sentinel for a generic ordered element type. If both largest entries are equal, both are returned; a second distinct value is a different specification.

For each segment retain its total weight $S$, largest possibly-empty prefix weight $P$, largest possibly-empty suffix weight $Q$, and largest possibly-empty internal contiguous weight $B$. The maximum-subarray segment summary combines adjacent segments asAn empty segment has all four values zero. For a singleton of weight $x$, use $(x,\max (0,x),\max (0,x),\max (0,x))$. The recursive procedure splits into halves, computes their summaries and applies these four formulas; the root's $B$ is the desired maximum weight.

To return an actual subsequence, attach half-open endpoints to each of $P,Q,B$. A prefix endpoint starts at its segment's left boundary, and a suffix endpoint ends at its right boundary, including empty prefixes and suffixes. Store the interval belonging to whichever candidate wins a maximum. The crossing candidate joins a left suffix to a right prefix, which meet at the split point; the other candidates keep their child endpoints. Choose an empty interval on ties at weight zero. Return the root's winning interval as a slice of the original input. This augmentation still has constant-size state and constant-time combinations.

For correctness, a prefix either stays inside the left half or consists of the entire left half and a right prefix. The suffix argument is symmetric. An optimal contiguous segment either lies in one half or crosses the split, in which case it consists of a left suffix and a right prefix. Each upper bound in the formulas is attained by its recorded candidate, proving exactness. Empty candidates ensure that an all-negative input returns the empty subsequence.

There are $\Theta (n)$ tree nodes, each using a constant number of additions and comparisons. The divide-and-conquer algorithm therefore takes $\Theta (n)$ time and $O(\log n)$ stack space, plus the cost of copying the returned slice if a copy is required. In the stated example it selects zero-based interval $[3,6)$ of weight 8. Carrying all four summary values avoids rescanning the halves at each split.