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

Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the edit distance. Let $D[i,j]$ be the edit distance between the first $i$ symbols of the first sequence and the first $j$ of the second. Initialize $D[i,0]=i$ and $D[0,j]=j$. For $i,j>0$ computeThe cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. Induction on $i+j$ proves the dynamic programming recurrence correct.

Fill rows or columns in increasing order so every dependency is already available. There are $(m+1)(n+1)$ entries with constant work per interior entry: $O(mn)$ running time for nonempty sequences, or $O((m+1)(n+1))$ including the boundary cases. The full table has space complexity $O(mn)$; two rows give $O(n)$ auxiliary space when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.

For nonnegative integer amount $v$, let $M[t]$ be the minimum number of coins making amount $t$. Set $M[0]=0$ and compute, in increasing order of $t$,An empty candidate set has minimum $\infty$. Here denomination $1$ ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on $t$.

Return whether $M[v]\le k$. This solves the at-most-$k$ decision without needing a separate dimension for $k$. The table for the minimum coin change recurrence takes $O(nv)$ running time and $O(v)$ space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.

During the computation in part i, record an index $\mathrm{last}[t]$ attaining the minimum at every positive amount. Starting with $t=v$, print $x_{\mathrm{last}[t]}$ and replace $t$ by $t-x_{\mathrm{last}[t]}$, continuing until $t=0$.

Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to $v$ and their number is exactly $M[v]$, proving optimality. The total running time is $O(nv+M[v])$, including the output; $M[v]\le v$ because denomination $1$ is available. The predecessor array adds $O(v)$ to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.

Let $M_i[t]$ use only the first $i$ available coins. Initialize $M_0[0]=0$, $M_0[t]=\infty$ for $t>0$, and useomitting the second term when $t<x_i$. The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. Induction on $i$ proves correctness, and $M_n[v]$ is the required answer, including $\infty$ when no selection works.

The running time is $O(nv)$. A single amount array reduces auxiliary space to $O(v)$ if each coin updates amounts in descending order, $t=v,v-1,\dots ,x_i$. Then $M[t-x_i]$ still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.

The printed formula for the edge label has mismatched variable names. The type-correct reading is $x_i=\sigma (v_{i-1},v_i)$. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let $R_t$ be the set of vertices reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and updateAfter $k$ stages, answer yes exactly when $R_k\ne \varnothing$. A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on $t$. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at $v_0$.

If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the set of visited vertices. Start with $R_0(\{v_0\},v_0)$ and extend a matching edge to $w$ only when $w\notin S$, replacing $S$ by $S\cup \{w\}$. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when $k\ge |V|$. A straightforward bound is $O(k{2}^{|V|}(|V|+|E|))$ running time with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

Use the multiplicative score exactly as defined in the paper. Let $P_t(v)$ be the largest score of a matching length-$t$ route ending at $v$. Initialize $P_0(v_0)=1$ and mark all other entries unreachable. For each stage, clear the new layer and inspect matching edges from reachable entries:An empty candidate set is marked unreachable, rather than given score zero: a genuine route may have score zero. A Boolean reachability table or a sentinel $-1$ with a guard before multiplication distinguishes the cases. Store the maximizing predecessor edge at each reachable layer entry, retaining one on a tie.

Multiplication by a nonnegative edge factor preserves order, so replacing a prefix by a larger-scoring matching prefix cannot worsen its extension. Induction proves this maximum-product edge-labelled walk recurrence correct. Choose a reachable final entry of greatest score and follow its layer-indexed predecessors backwards to reconstruct the answer. If no final entry is reachable, report that no matching route exists, even though all numeric scores might otherwise look like zero.

The running time is $O(k(|V|+|E|))$, and rolling scores have space complexity $O(|V|)$, while retaining all reconstruction pointers gives space complexity $O(k|V|)$. For the vertex-simple interpretation, retain the visited set in each state as in part i, prohibit revisits and maximize the same products over those states. This exact exponential-state variant preserves both the zero-score distinction and predecessor reconstruction. If the starting vertex is unrestricted rather than inherited from part i, initialize $P_0(v)=1$ for every vertex. The calculation needs no independence assumption beyond the paper's definition of a product score; repeated physical edge-activation events would require a separate probabilistic model.