Reference no: EM1368833
We can use dynamic programming on a directed graph G = (V, E) for speech recognition. Each edge (u, v) E is labeled with a sound σ(u, v) 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 v0 V corresponds to a possible sequence of sounds produced by the model. The label of a directed path is defined 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 v0 and a sequence s = σ1, σ2, ..., σk of characters from Σ, returns a path in G that begins at v0 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, v) E has also been given an associated nonnegative probability 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 probabilities of its edges. We can view the probability of a path beginning at v0 as the probability that a "random walk" beginning at v0 will follow the specified path, where the choice of which edge to take at a vertex u is made probabilistically 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 v0 and having label s. Analyze the running time of your algorithm.
|
Explain the carrier challenged reardon''s standing to sue
: Explain The carrier challenged Reardon's standing (right) to sue claiming that the original contract said Reardon had no liability to pay for the merchandise until after it was received and sold by Reardon.
|
|
Discussion on merger consideration
: With lower values for gasoline than a couple of years before will Americans start spending again? If they do, what will they spend the savings on Vacations?
|
|
What is sports car acceleration
: A sports car moving at constant speed travels 90 m in 4.9s. If it then brakes and comes to a stop in 4s, what is its acceleration? Express the answer in terms of g's, where g = 9.80 m/s2. (Take the positive direction to be direction of travel.)
|
|
Show the components of an effective training program
: Developing training, Needs Assessment and HR and what are the components of an effective training program?
|
|
Explain efficient algorithm for edge-labeled graph
: Explain efficient algorithm that, provided edge-labeled graph G with distinguished vertex v0 and sequence s = σ1, σ2, ..., σk of characters from Σ, returns path in G which begins at v0.
|
|
Negotiation situation using different strategies
: Describe a negotiation situation that employs different negotiation strategies and describe the negotiation processes
|
|
Make an aggregate demand and aggregate supply graph
: The data given below shows the situation in 2010 and 2011 if Fed does not use the monetary policy,
|
|
What is the unit vector in the direction of block
: A 0.6 kg block of ice is sliding by you on a very slippery floor at 3.5 m/s. As it goes by, you give it a kick perpendicular to its path. Your foot is in contact with ice block for 0.0035 seconds.
|
|
Explain how you would build rapport with your audience
: Explain how you would build rapport with your audience in a business presentation and What motivational strategies have you used
|