We can use dynamic programming on a directed graph G = (V, E) for speech recognition. Each edge (u, ν) ∈ E is labeled with a sound σ (u, ν) from a finite set ∑ of sounds. The labeled graph is a formal model of a person speaking a restricted language. Each path in the graph starting from a distinguished vertex ν₀ ∈ V corresponds to a possible sequence of sounds produced by the model. We define the label of a directed path to be the concatenation of the labels of the edges on that path.

a. Describe an efficient algorithm that, given an edge-labeled graph G with distinguished vertex ν₀ and a sequence s = 〈σ₁, σ₂, . . . , σ_k〉 of sounds from Σ, returns a path in G that begins at ν₀ and has s as its label, if any such path exists. Otherwise, the algorithm should return NO-SUCH-PATH. Analyze the running time of your algorithm.

Now, suppose that every edge (u, ν) ∈ E has an associated non negative probability p(u, ν) of traversing the edge (u, ν) from vertex u and thus producing the corresponding sound. The sum of the probabilities of the edges leaving any vertex equals 1. The probability of a path is defined to be the product of the probabilities of its edges. We can view the probability of a path beginning at ν₀ as the probability that a “random walk” beginning at ν₀ will follow the specified path, where we randomly choose which edge to take leaving a vertex u according to the probabilities of the available edges leaving u.

b. Extend your answer to part (a) so that if a path is returned, it is a most probable path starting at ν₀ and having label s. Analyze the running time of your algorithm.