JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Top down with Memoization - complexity | Reply
Top down with Memoization complexity –
The purpose of this article is to analyze the complexity of algorithms written using top down approach.
Most of the problems can inherently be described using top down recursion. The complexity of algorithm however makes it far from usable in practical scenarios. Such kind of algorithms shows the exponential complexity and might need some kind of specialized solution to bring the hardness of solution from exponential to polynomial complexity. To describe one such case let’s take an example of one moderate problem. The problem is as described below and is another variation of well known LCS (Longest common subsequence problem). The purpose of taking problem with moderate complexity is to provide the audience with some challenge to come to conclusion and work out solution which is close enough for practical use. The problem is also different from what most of the readers have seen elsewhere. The problem is as given below -
A subsequence is palindromic if it is the same whether read left to right or right to left. For
Instance, the sequence
A;C; G; T; G; T;C; A; A; A; A; T;C;G has many palindromic subsequences, including A;C; G;C;A and A; A; A;A (on the other hand, the subsequence A;C; T is not palindromic). Devise an algorithm that takes a sequence x[1 : : : n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n2).

So as a layman programmer the problem seems to be recursive and solved with some recursive scheme.
Let’s call the Longest Palindrome Sequence as LPS. So given a string Aij, the solution looks like below -


Ai = Aj -- 2 + LPS(i+1, j-1)
LPS(i, j) = Max
Ai != Aj -- Max(LPS(i, j-1), LPS( i+1, j))

The algorithm can easily be reproduced in any available language which supports recursion.

So our naïve algorithm looks like

int LPS(i, j) {
if (I ==j) return 1;
If (Ai == Aj) {
return 2 + LPS(i+1, j-1);
} else {
return Max(LPS(i, j-1), LPS( i+1, j));
}
}
The solution by far looks correct. But can it be used practically for any good use. The exponential complexity of above algorithm might make it even difficult for strings of moderate lengths. If we closely look at the solution we see the depth of the recursion increases exponentially. So given string of length k, the complexity of above algorithm is 2 ^ k, since every problem is divided into 2 new problems.
And worse thing is same problem is repeating itself. So the total complexity in worst case when there is no palindrome in the problem string is (2* 2 ^ K).

To make it more clear consider substring I, j. The problem I +1, j and I, j-1 has I + 1, j -1 common problems. Is there a way to avoid processing the same problems? Can we make use of computation which we have already done? A minute’s reflection will tell yes we could.
Below shows how we could do this. Read M as matrix in below code of length I, j.

int LPS(i, j) {
int lcs;
if (I ==j) return 1;
If (M[i][j] == -1) {
If (Ai == Aj) {
lcs = 2 + LPS(i+1, j-1);
} else {
lcs = return Max(LPS(i, j-1), LPS( i+1, j));
}
M[i][j] = lcs;
}
Return M[i][j];
}

The above algorithm is memoization and reduces the complexity of problem by half. The above solution skips computing similar problems.

There is yet another solution to above problem which reduces the complexity to polynomial time.
As most of us know it’s a bottom up approach using Dynamic Programming.

The solution is given below and self explanatory. M is matrix where we store results for previous computations.


F Mk,I  Ak != Ai  Mk,i-1
i = 0, n Ak = Ai  2 + Mk+1, i-1
j = 0, i
k = j, i

Read F as for each. For the above algorithm the complexity is n ^ 3. The table is constructed bottom up. For ex A0, A0..Aj, A0 – An. So if you know Mi, j-1 you know M I, j.
Do we need more explanation to code above thing? I guess no.

The complexity can further be reduced to n ^ 2 If we reverse the same string and run LCS over the two strings. Since complexity of LCS (Largest common ancestor is n ^ 2).
RSS