15-7 Viterbi algorithm We can use dynamic programming on a directed graph G = (V, E) for speech recognition. Each edge (u, v) E E is labeled with a sound (u, v) from a fi- nite set of sounds. The labeled graph is a formal model of a person speaking Problems for Chapter 15 409 a restricted language. Each path in the graph starting from a distinguished ver- tex Vo E 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 dis- tinguished vertex vo and a sequence s (o1.02, , k Of sounds from returns a path in G that begins at vo 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. (Hint: You may find concepts from Chapter 22 useful.) Now, suppose that every edge (u. v) E E has an associated nonnegative proba- bility p(u, v) of traversing the edge (u. v) 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 probabil ities of its edges. We can view the probability of a path beginning at Vo as the probability that a "random walk" beginning at vo 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 prob- able path starting at vo and having label s Analyze the running time of your algorithm