Instead of adding the two base cases for only two elements (eg: AA, AB) at 8:02, something of the following sort would be more elegant.... LP( i, j ) = 0 if j < i. In this case, the other conditions will automatically evaluate to 2 or 1 for the case AA or AB respectively.
Hi cupidvogel, in both the algorithms you need to just store at each places, the decision points that would help you to find the longest increasing and longest palindromic subsequence, it woulkd be good exercise for you
a more easy to implement strategy could go this way: just reverse the string ..say str1="XAYBZBA" then reverse of str1 is str2="ABZBYAX" ..then finding the LCS(str1,str2) gives you the longest palindrome subsequence..reversing wouldnt bring a big change to the tight bounds..
By visual inspection LP(2,7) is 3, "BZB". This algorithm seems to return the length of the longest subsequence with matching terminii. When moving both ends in there should be a check if the new terminii are equal before adding 2.
Surabh, i think the recursion equation can be simplified. I dont think you need the two separate cases for j = i + 1. If you just define LP(i,j) = 0 for i > j, then the rest of the conditions should give the right answer for the j = i + 1 case.
Great lecture, thanks. Quick question though - what's the solution for an input string like "ABCDBA", using this algorithm ? I believe the recursive calls would go something like this - LP("ABCDBA") = = 2 + LP("BCDB") // LP(i+1, j-1) + 2, if X[i] == X[j] = 2 + 2 + LP("CD") // ^^ = 2 + 2 + 1 // LP(i, j) = 1, if j = i+1 && X[i] != X[j] = 5 I'm clearly missing something here. Appreciate any hints.
Mandeep Condle don't consider them as consecutive for example "AACCAYC" you would match first left most A with first rightmost A, second A has no match and then the C's. Dont match the C's with the C on the extreme right as that is not considered once you have chosen A.
Here when X[i] != X[j] then L[i][j] = max(L[i+1][j], L[i][j-1]). But during memoization when we run a loop, at the point when we reach L[i][j] we dont know the value of L[i+1][j]. How should we proceed?
i am sorry for my ignorance, when you say it is 5, i believe it is the length of the palindromic sequence which is 5. Looking at the string, I only see BZB as the maximum length palindromic sequence. Can you please name the subsequence of length 5 here? Appreciate your clarification. thanks!
but this is just the recurrence relation, it is not a dynamic programming solution. It doesn't use bottom up or memoization. because u will again solve (3,6) subproblem when it has already been solved
Instead of adding the two base cases for only two elements (eg: AA, AB) at 8:02, something of the following sort would be more elegant.... LP( i, j ) = 0 if j < i. In this case, the other conditions will automatically evaluate to 2 or 1 for the case AA or AB respectively.
Hi cupidvogel, in both the algorithms you need to just store at each places, the decision points that would help you to find the longest increasing and longest palindromic subsequence, it woulkd be good exercise for you
a more easy to implement strategy could go this way: just reverse the string ..say str1="XAYBZBA" then reverse of str1 is str2="ABZBYAX" ..then finding the LCS(str1,str2) gives you the longest palindrome subsequence..reversing wouldnt bring a big change to the tight bounds..
Beautiful presentation with example!
Thank you sir!
By visual inspection LP(2,7) is 3, "BZB". This algorithm seems to return the length of the longest subsequence with matching terminii. When moving both ends in there should be a check if the new terminii are equal before adding 2.
I think the algo is for non-consecutive charachters palindrome
Surabh, i think the recursion equation can be simplified. I dont think you need the two separate cases for j = i + 1. If you just define LP(i,j) = 0 for i > j, then the rest of the conditions should give the right answer for the j = i + 1 case.
you need to see the other condition, this is true given X[i] == X[j] so if this condition is true then the recurrence relation is true
Great lecture, thanks. Quick question though - what's the solution for an input string like "ABCDBA", using this algorithm ?
I believe the recursive calls would go something like this -
LP("ABCDBA") =
= 2 + LP("BCDB") // LP(i+1, j-1) + 2, if X[i] == X[j]
= 2 + 2 + LP("CD") // ^^
= 2 + 2 + 1 // LP(i, j) = 1, if j = i+1 && X[i] != X[j]
= 5
I'm clearly missing something here. Appreciate any hints.
Mandeep Condle don't consider them as consecutive for example "AACCAYC" you would match first left most A with first rightmost A, second A has no match and then the C's. Dont match the C's with the C on the extreme right as that is not considered once you have chosen A.
thank you sir,.....can I know how to find the whole palindrom, as this gives only count not string?
Here when X[i] != X[j] then L[i][j] = max(L[i+1][j], L[i][j-1]). But during memoization when we run a loop, at the point when we reach L[i][j] we dont know the value of L[i+1][j]. How should we proceed?
it must be O(n) when using Dynamic Programming. However the presenter forgot to mention about memorizing the solution of already computed sub-problem.
i am sorry for my ignorance, when you say it is 5, i believe it is the length of the palindromic sequence which is 5. Looking at the string, I only see BZB as the maximum length palindromic sequence. Can you please name the subsequence of length 5 here? Appreciate your clarification. thanks!
what is the time complexity of the this algorithm?
Is the brute force algorithm order of n.2^n or order of n^3 ? Can you elaborate ?
but this is just the recurrence relation, it is not a dynamic programming solution. It doesn't use bottom up or memoization. because u will again solve (3,6) subproblem when it has already been solved
Actually no need of solving again,as you are storing the result in a table.Just implement it such that the line which finds max comes at last.
You should write code in all your programmng interview questions, so we can see and test.
I felt it's better if he doesn't write it. Coding is the least we can do on our own, after the algo is known.
yes thats correct , it was kind of slip of tongue :)
returning the palindromic subsequence?...this algorithm only returns the length
lp(i,j)=lp(i+1,j-1)+2, wrong. lp(i+1,j-1) may not be palindrome.
It would be less than n
I guess