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 / b / Solution

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.