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

Increment a single clock on each discovery and finish, starting with clock zero. Lexicographic depth-first search givesThe first search tree has discovery edges $1\to 3$, $3\to 5$, $3\to 6$. The edge $5\to 1$ returns to an active ancestor. Once that tree finishes, vertex $2$ is a new root whose neighbour $1$ is already finished, and vertex $4$ is the final root. This accounts for all twelve events in the DFS discovery and finishing times.

The only possibilities are $f[2]\in \{10,11\}$. Vertex $2$ reaches all of $1,3,5,6$. In depth-first search, all vertices reachable from an active vertex must have been discovered and finished before its own finishing event, except for active ancestors. None of these four can be an ancestor of $2$, because none can reach $2$. Thus all four are finished before $2$ finishes.

Vertex $4$ cannot already be finished at that point: its outgoing edge to $2$ would have caused $2$ to be visited before it could finish. It also cannot be a descendant of $2$, since $2$ cannot reach $4$. Therefore $4$ is either still undiscovered or an active ancestor. In the first case the only remaining events are discovery and finishing of $4$, giving $f[2]=10$. In the second case the only remaining event is finishing of $4$, giving $f[2]=11$.

Both occur. Starting the outer traversal with $2$ leaves $4$ undiscovered and gives time $10$. Starting with $4$ and taking its edge to $2$ first makes $4$ an ancestor and gives time $11$. The argument does not assume any particular order on the other edges.

The strongly connected components areThe directed cycle $1\to 3\to 5\to 1$ makes its three vertices mutually reachable. Vertex $6$ has no outgoing edge. Vertex $2$ reaches that cycle but has no return path from it, and vertex $4$ reaches the other components but has no incoming path from them. These facts exclude every further merger.

Sort the open intervals by increasing left endpoint. Scan them in that order, maintaining the largest right endpoint $R$ among previously seen intervals. For the next interval $(a,b)$, report an intersection if $a<R$; otherwise set $R=\max (R,b)$ and continue. Equality is allowed: $(a,R)$ and $(R,b)$ do not meet because the intervals are open. For zero or one interval, return that they are mutually non-intersecting.

If $a<R$, a previous interval with right endpoint $R$ has left endpoint at most $a$ and has positive length. Together with $b>a$, this guarantees an interior common point. Conversely, if $a\ge R$, every earlier interval ends at or before $a$, so none intersects the new one. This loop invariant proves correctness. A comparison sort costs $O(n\log n)$ time and the scan costs $O(n)$.

For the lower bound, transform an input of integers $z_1,\dots ,z_n$ for the element distinctness problem intoEqual integers produce identical, intersecting intervals. Unequal integers differ by at least one, so their intervals are disjoint. The answer therefore decides whether all the integers are distinct. Moreover, comparing any two constructed endpoints can be simulated by comparing their original integers and, only on equality, their fixed offsets $0$ or $1$. Thus the transformation preserves the comparison model, rather than gaining extra information from arithmetic on arbitrary endpoints. The supplied distinctness lower bound gives $\Omega (n\log n)$ comparisons, matching the upper bound. This is the comparison lower bound for interval disjointness.

Let $m=|s|$, ${\ell }_i=|w_i|$, and let $D(i,j)$ be the minimum number of words chosen from $w_1,\dots ,w_i$, in their given order, whose concatenation equals the length-$j$ prefix of a list of $s$. Use $\infty$ for impossibility. The boundary values areFor $i\ge 1$,Here $s[a:b]$ denotes indices $a,\dots ,b-1$. The first case omits $w_i$. In the second, the last selected word is $w_i$, so removing it leaves a solution using only earlier words for the shorter prefix. These are exhaustive alternatives. Conversely either alternative constructs a valid solution, proving the dynamic programming recurrence. Even an empty word causes no cycle because both alternatives use row $i-1$.

Fill rows in increasing $i$ and store the chosen alternative for every finite entry. If $D(n,m)=\infty$, report no solution. Otherwise trace back from $(n,m)$: a skip moves to $(i-1,j)$; a take records index $i$ and moves to $(i-1,j-{\ell }_i)$. Reverse the recorded indices to obtain the required subsequence. Ties may choose either valid predecessor.

There are $(n+1)(m+1)$ states. A substring comparison costs $O({\ell }_i)$, so under the given bounds $m=O(n)$ and ${\ell }_i=O(1)$ the running time is $O(n^2)$, with $O(n^2)$ storage including reconstruction choices. Two rows give $O(m)$ working storage if only the optimum count is needed. For the source example, the optimum is three words, indices $(2,5,6)$, whose concatenation is 010111. This is ordered word concatenation dynamic programming.