CSCE 629 Homework 1 Name Tian JinUIN 524005877 1 1 Textbook page 370 Exercise 15 1 2 Show by means of a coun terexample that the following greedy strategy does not always determine an optimal way to cut rods Defi ne the density of a rod of length i to be pi i that is its value per inch The greedy strategy for a rod of length n cuts off a fi rst piece of length i where 1 i n having maximum density It then continues by applying the greedy strategy to the remaining piece of length n i Solution First let s analyze this rod cut problem in general Input 1 a rode of length n an integer 2 for i 1 2 n a rod of length i has a price pi3 density of a rod of length i is pi i Output how to cut the rod so that the total price is maximum If we defi ned k as the left most cut then the rod cutting problem has a recursive function rn max k 1 n pk rn k I am now giving a counterexample for the greedy strategy Assuming that the price and density listed as following table length i12345 price pi114243640 density pi i17898 Set the given length as 5 If we use the greedy strategy we fi rst choose to cut the rod at the length of 4 because the density of length 4 is maximum which is 9 Then we will get 2 parts length 4 and length 1 The total price of this condition is 36 1 37 However the best way to cut the rod is cutting the rod to have two parts length 2 and length 3 which has a maximum price 14 24 38 So it seems that the greedy strategy does not always determine an optimal way to cut rods 2 2 Textbook page 408 Problem 15 7 Viterbi algorithm 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 fi nite 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 We defi ne the label of a directed path to be the concatenation of the labels of the edges on that path a Describe an effi cient algorithm that given an edge labeled graph G with distinguished vertex v0and a sequence s h 1 2 ki of sounds from returns a path in G that begins at v0and has s as its label if any such path 1 exists Otherwise the algorithm should return NO SUCH PATH Analyze the running time of your algorithm Hint You may fi nd concepts from Chapter 22 useful Now suppose that every edge u v E has 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 defi ned 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 specifi ed 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 v0and having label s Analyze the running time of your algorithm Solution a In order to understand clearly we fi rstly need to fi gure out the input and the output We need to use dynamic programming to solve this problem Input a graph G V E which contains following elements 1 vertex v02 a string s composed of some characters in alphabet Output fi nd whether there is a path from v0labeled with s For example if a b c d e f g v0 1 and s ecf Consider the given path I created myself See Figure 1 and it has a path 1 5 4 3 labeled with s Figure 1 The given graph G From the Chapter 22 we can learn that in the expression of G V E the V denotes the vertices and E represents all the edges Part I My Idea 1 state I defi ne a state as isaPath i x which means that starting from the vertex v0 whether it has a path to vertex x through all the edges s 2 h 1 2 ii isaPath i x true if thereisapathsatisfied isaPath i x false if thereisnopathsatisfied 1 2 initialize It is obvious that isaPath 0 v0 true and for x 6 v0 isaPath 0 v false 3 function isaPath i x isaPath i 1 y if E y x i isaPath i x false otherwise 2 where E y x denotes that the edge value between vertex x and vertex y 4 result according to the question we need to check isaPath k v as the result After tracing back we can know what the exact path Part II Present algorithm in pseudo code ISAPATH i x 1if i 0 2return true 3else for x 6 v0 4ISAPATH 0 v false 5for 0 i k 6if E y x i 7ISAPATH i x ISAPATH i 1 y 8else ISAPATH false 9return ISAPATH k v Part III Prove correctness Looking back at the example I gave Initially it is obvious that isaPath 0 1 true Then we can start to calcu late the following value Because E 1 5 e then isaPath 1 5 isaPath 0 1 true Because E 5 4 c then isaPath 2 4 isaPath 1 5 true Because E 4 3 f then isaPath 3 3 isaPath 2 4 true Finally we get the result isaPath 3 3 After tracing back we can know the exact path is 1 5 4 3 Part IV Time complex