Re: [algogeeks] DP problems
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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] DP problems
U have two dimensions for the table ( has O(n^2) entries.) and to check
whether string is palindrome or not it will take O(n) . So it is O(n^3)
solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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] DP problems
Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com wrote:
U have two dimensions for the table ( has O(n^2) entries.) and to check
whether string is palindrome or not it will take O(n) . So it is O(n^3)
solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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] DP problems
Hi all!
Well, I agree with Shashwat in that Kumar is wrong with his solution. For
example a string kumarxyzramuk will tell you why.
I have a solution which runs in O(n*n) time. It is top-down dynamic
programming approach. Let me know if you don't understand something or if
there is some glitch in the solution. I think it is correct.
Link to the C++ code - http://ideone.com/Qzs990
On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote:
Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
U have two dimensions for the table ( has O(n^2) entries.) and to check
whether string is palindrome or not it will take O(n) . So it is O(n^3)
solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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] DP problems
Yes i agree that my recurrence relation is wrong. I have checked it some
inputs, it did not work. But i think the brute force solution is possible
in O(n^3) solution. We have O(n^2) combination of end points. we can check
for the maximum possible even length palin string in O(n). So that will
give O(n^3). Anyone has solution about O(n^2)?
On 5 June 2014 22:25, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Hi all!
Well, I agree with Shashwat in that Kumar is wrong with his solution. For
example a string kumarxyzramuk will tell you why.
I have a solution which runs in O(n*n) time. It is top-down dynamic
programming approach. Let me know if you don't understand something or if
there is some glitch in the solution. I think it is correct.
Link to the C++ code - http://ideone.com/Qzs990
On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote:
Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
U have two dimensions for the table ( has O(n^2) entries.) and to check
whether string is palindrome or not it will take O(n) . So it is O(n^3)
solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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] DP problems
Dude! That is what I just posted. Also your logic is wrong, Palindrome
thing is just not working. Think for a while on this problem.
On Thu, Jun 5, 2014 at 11:18 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
Yes i agree that my recurrence relation is wrong. I have checked it some
inputs, it did not work. But i think the brute force solution is possible
in O(n^3) solution. We have O(n^2) combination of end points. we can check
for the maximum possible even length palin string in O(n). So that will
give O(n^3). Anyone has solution about O(n^2)?
On 5 June 2014 22:25, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Hi all!
Well, I agree with Shashwat in that Kumar is wrong with his solution. For
example a string kumarxyzramuk will tell you why.
I have a solution which runs in O(n*n) time. It is top-down dynamic
programming approach. Let me know if you don't understand something or if
there is some glitch in the solution. I think it is correct.
Link to the C++ code - http://ideone.com/Qzs990
On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote:
Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
U have two dimensions for the table ( has O(n^2) entries.) and to check
whether string is palindrome or not it will take O(n) . So it is O(n^3)
solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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] DP problems
U need not get an exact palindrome. u will start comparing from both the
end points till they are equal and does not cross each other. So that
should be possible in linear time right. I did not get ur code exactly and
u have written O(n*n) so i have got the doubt.
On 5 June 2014 23:22, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Dude! That is what I just posted. Also your logic is wrong, Palindrome
thing is just not working. Think for a while on this problem.
On Thu, Jun 5, 2014 at 11:18 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
Yes i agree that my recurrence relation is wrong. I have checked it some
inputs, it did not work. But i think the brute force solution is possible
in O(n^3) solution. We have O(n^2) combination of end points. we can check
for the maximum possible even length palin string in O(n). So that will
give O(n^3). Anyone has solution about O(n^2)?
On 5 June 2014 22:25, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
Hi all!
Well, I agree with Shashwat in that Kumar is wrong with his solution.
For example a string kumarxyzramuk will tell you why.
I have a solution which runs in O(n*n) time. It is top-down dynamic
programming approach. Let me know if you don't understand something or if
there is some glitch in the solution. I think it is correct.
Link to the C++ code - http://ideone.com/Qzs990
On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote:
Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
U have two dimensions for the table ( has O(n^2) entries.) and to
check whether string is palindrome or not it will take O(n) . So it is
O(n^3) solution.
I have checked it manually for some inputs, and it works.
On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:
I am not too sure about your O (N^3) solution even. Can you link the
working code ?
On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
wrote:
This is a very good collection of DP problems.
I want the answers for problem 2(e)
and problem 14.
for problem 14 the recurrence relation
that i have is
T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2 if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else
But this is O(n^3) solution. Could not
find out solution of order O(n^2).
If someone knows please share the answers for them.
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
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] DP problems
Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- 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] DP problems
And now I get what you meant when you said palindrome. You should have explained that if that was not exact palindrome So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- 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] DP problems
If i get u correctly, this is the recurrence relation ( i feel this makes many people to understand the solution rather than looking at the code) T[i..j] indicates the length of longest even length palin string ( not exactly palin but i think u know what i am saying) with i as begin and j as ending point. T[i,j] = 0 if i=j T[i+1,j-1]+1 if s[i]==s[j] 0else And u find max value in the table which is the answer So time complexity = space complexity = O(n^2). Correct me if i am wrong On 5 June 2014 23:44, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: And now I get what you meant when you said palindrome. You should have explained that if that was not exact palindrome So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- 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] DP problems
T[i][j] = 0 (i 0 || j =n || i = j || s[i] != s[j]) T[i][j] = 1 + T[i-1][j+1] On Fri, Jun 6, 2014 at 12:19 AM, kumar raja rajkumar.cs...@gmail.com wrote: If i get u correctly, this is the recurrence relation ( i feel this makes many people to understand the solution rather than looking at the code) T[i..j] indicates the length of longest even length palin string ( not exactly palin but i think u know what i am saying) with i as begin and j as ending point. T[i,j] = 0 if i=j T[i+1,j-1]+1 if s[i]==s[j] 0else And u find max value in the table which is the answer So time complexity = space complexity = O(n^2). Correct me if i am wrong On 5 June 2014 23:44, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: And now I get what you meant when you said palindrome. You should have explained that if that was not exact palindrome So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- 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. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- 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.
