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 / c

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.