Q6. DP6 Efficient (Memory) Table size of Matrix Chain Multipilcation of Matrix A1 to AN: O(n^2) B. O(n^2/2) C. O(n) None of these

Please explain this question and answer

hello @KetanPandey

In this question , they are asking what table size is sufficient to solve mcm problem.

and answer should be N^2/2

check this example->
image

Q1. DP1 predict the complexity of the code: vector<vector > v(100,vector (100,-1) ); int func(int n,int m) { if((n==0)||(m==0)) { return 0; } else { if(dp[m][n]!=-1) { return dp[m][n]; } else { return func(n-1,m-2)+func(n-2,m-1); } } }.Please explain this question

U are saying answer is O(n^2/2) but we can’t declare such an arrar,we will have to declare an array of O(n^2) size.so this should be the answer

have u studied vector?

it will be O(nm)
because here we will have n
m distinct dp states and for each state we are working O(1)
so in total nm * 1 -> O(nm)

Q4. DP4 predict the complexity of the code: vector<vector > dp(100,vector (100,-1) ); int func(int n,int m) { lli x; if((n==0)||(m==0)) { return 0; } else { if(dp[m][n]!=-1) { return dp[m][n]; } else { dp[n][m]= func(n-1,m-2)+func(n-2,m-1); return dp[n][m]; } } } O(n^2) O(n logn) O(2^n) O(n^3).Please explain this one.I think answer should beO(nlogn)

Q8. DP8 Given two sequences A and B, what will be the length of the longest subsequence present in both of them if we define L[m][n] , LCS of strings A[1….m] and B [1……n] ? L[i][j]=L[i-1][j-1]+1 , when A[i]==B[j] L[i][j]=(abs(L[i-1][j]-L[i][j-1])+L[i][j-1]+L[i-1][j]) /2 , when A[i]!=B[j] L[i][j]=max(L[i-1][j],L[i]][j-1]) , when A[i]!=B[j] All of these

Q9. DP9 Given an array A consisting of n integers , we define beauty of the array as maximum sum of some contiguous elements with performing atmost one operation which is , you can multiply any subarray with ‘x’ but only once. What will be the maximum subarray sum for this input N=5,x=-2 A=[-3,8,-2,1,-6] (Bonus :: Can you write the effiicient code for it ?) 0 22 24 12

Q10. DP10 Given two strings , what could be the best complexity that you can solve in , the K-ordered LCS of the given strings ? A k-ordered LCS is defined to be the LCS of two sequences if you are allowed to change at most k elements in the first sequence to any value you wish to. Defining N and M as the length of the given strings respectively. O(NMlogk) O(NMk) O(N*M) O(NklogM)

Yes I have studied vector

I don’t think we are going in each state because ans=func(n-1,m-2)+func(n-2,m-1)
In dry run ,it is clearly seen that we are not going in each state.we are just going in some selected states so the complexity should not be O(n^2) rather it should be O(nlogn)

all these questions are dp problem in itself and to understand the time complexities of these question first u need to understand their solution .
so first study these problems and thier solution before attempting this quiz

a) LCS
b) optimal game stratergy
c) K - order LCS

in that MCM problem we can use array of vectors intead of 2d array to save space

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.