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

Dynamic programming stores answers to overlapping subproblems so they can be reused. Its optimal substructure requirement, the principle of optimality, says that an optimal answer's remaining subproblem solution must itself be optimal once the final decision and state are fixed.

For global sequence alignment without mismatches, use the two prefix lengths as the state. A final column is either a letter of the first string opposite a gap, a gap opposite a letter of the second, or two equal letters. Removing that column leaves one of three smaller prefix problems. If its alignment were suboptimal, replacing it by a better alignment would improve the whole answer. Many different alignments reach the same prefix state, making reuse valuable. Unequal-letter columns and double-gap columns are forbidden, rather than assigned ordinary finite penalties.

Let $D_{i,j}$ be the optimal score for aligning the complete prefixes of lengths $i,j$. The boundary values and recurrence areThe last candidate is omitted when the letters differ. Fill rows or columns in increasing index order and return $D_{m,n}$. The final-column cases in part (a) exhaust all legal alignments and each can be appended to an optimal smaller alignment, proving the recurrence by induction on $i+j$.

There are $(m+1)(n+1)$ entries and at most three constant-time candidates per interior entry. Thus the time is $O(mn)$ for positive $m,n$, or $O(mn+m+n+1)$ including empty-input boundary cases, with the same full-table space bound. Computing only the score can reduce auxiliary storage to $O(\min (m,n)+1)$ by retaining two rows. This is global sequence alignment without mismatches; admitting a diagonal move on unequal letters would solve a different problem.

Store one maximizing predecessor together with every table value. For alignment traceback, start at $(m,n)$ and follow these pointers:

Continue to $(0,0)$, including boundary moves, then reverse the collected columns. Any deterministic choice among tied predecessors gives an optimal alignment. Each step decreases at least one index, so reconstruction costs $O(m+n)$ additional time and output space. The full score table or predecessor table requires $O(mn)$ storage for positive lengths.

Enumerate all pairs of contiguous substrings, run the global algorithm on each pair, and take the largest score, also allowing the empty alignment of score zero. There are $O(m^2)$ substrings of the first input and $O(n^2)$ of the second. Each call costs at most $O(mn)$ for positive lengths, giving the requested upper bound $O(m^3{n}^3)$. Substrings are contiguous; enumerating arbitrary subsequences would be a different search.

For local sequence alignment without mismatches, let $L_{i,j}$ maximize the score of alignments of a suffix of each prefix of lengths $i,j$, allowing both suffixes to be empty. Initialize $L_{i,0}=L_{0,j}=0$ and fillZero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because $g\ge 0$, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.

Return ${\max }_{0\le i\le m,0\le j\le n}{L}_{i,j}$, since an optimal pair of substrings may finish before either full string ends. The time is $O(mn)$ for positive input lengths, with $O(mn)$ full-table space or linear rolling-row space for the score alone. If an alignment is wanted, start alignment traceback at a maximum entry and stop at zero. No mismatching diagonal is introduced.