edited by
1,013 views
2 votes
2 votes
we are given two strings: String S of length n and string T of length m for the
LCS problem, we have produced the following exponential time recursive
program.
LCM (S, n, T, m)
{ if (n == 0||m == 0) return 0
if (S[n] == T[m]) result t = 1 + LCS (S, n – 1, T, m – 1);
else result = max (LCS (S, n – 1, T, m), LCS (S, n, T, m – 1));
return result;
}
then the number of times that LCS (S, 1, T, 1) is recursively called equals
________

plz solve?
edited by

3 Answers

0 votes
0 votes
Here both the length of the strings are 1 so

if both elements of the two strings are same the 2 calls
else 1 call will be made.
0 votes
0 votes
I think permutations can be following considering dynamic programming approach:
1) LCS(n, 1) where value of 'n' goes on decreasing

2) LCS(1, m) where value of 'm' goes on decreasing

But if tree like hierarchy is considered to find out total calls made, then any value of 'm' and 'n' will have the call LCS(1,1)

So it would be O(n.m) I think
edited by
0 votes
0 votes
n-1 are total element in rows

M-1 are total element in column

(n-1)+(m-1))!/(n-1)!*(m-1)!

=(n+m-2)!/(n-1)!*(m-1)!

=(n+m-2)Cn-1 or (n+m-2)Cm-1

Related questions

3 votes
3 votes
2 answers
2
Arnab Bhadra asked Jun 27, 2017
578 views
Question no 11.
2 votes
2 votes
1 answer
3
Rustam Ali asked Sep 2, 2016
893 views
Avoid the any syntax error ,if there is:What will be the output of the following code ? #inlcude<stdio.h void myfun(int i) { if(i>0) { myfun(i-1); printf("%d",i); myfun(i...
1 votes
1 votes
1 answer
4
Tariq Husain Khan asked Aug 23, 2016
312 views
what is the time complexity of best algo that decides whether a given directed graph represented as adjacency matrix contains a sink or not? solve and plz explain how?