Re: [algogeeks] Breaking a string problem (Dynamic programming)
Hi Raja, You can store positions cuts in a separate 2d array ( say C[i][j] ) similar to S[i,j] to store optimal cut position for string running from index i to j and use recursion to print cut positions. -Thanks Bujji On Thu, Oct 17, 2013 at 3:21 AM, kumar raja rajkumar.cs...@gmail.comwrote: I have find out the minimum cost using the recurrence relation S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i=kj. But i could not find a way to print optimal cut sequence.Any pointers? On 16 October 2013 23:13, atul anand atul.87fri...@gmail.com wrote: Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Breaking a string problem (Dynamic programming)
Don't you think it would give same answer for any value of k as S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i=kj. Ultimately all are getting sum up. For example S[i,j] = j - i +1 + min ( k-i+1 + j-(k+1) + ... ) which gives s[i,j] = j-i +1 + min ( j-i -1 + ... ). So it does not depend on the value of k. I think the recurrence relation should be s[i,j] = ( j - i +1) + (j - k) + min ( s[i,k]+s[k+1,j]) for all i=kj, it also suits the example you gave of 20 char str gets divided at position 3 means 20 + (20 -3.) = 37. On Thu, Oct 17, 2013 at 3:51 PM, kumar raja rajkumar.cs...@gmail.comwrote: I have find out the minimum cost using the recurrence relation S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i=kj. But i could not find a way to print optimal cut sequence.Any pointers? On 16 October 2013 23:13, atul anand atul.87fri...@gmail.com wrote: Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Breaking a string problem (Dynamic programming)
I have find out the minimum cost using the recurrence relation S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i=kj. But i could not find a way to print optimal cut sequence.Any pointers? On 16 October 2013 23:13, atul anand atul.87fri...@gmail.com wrote: Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Breaking a string problem (Dynamic programming)
Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
