Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

Multiple choice question for engineering

Set 1

1. Which of the following methods can be used to solve the edit distance problem?
a) Recursion
b) Dynamic programming
c) Both dynamic programming and recursion
d) None of the mentioned

View Answer

Answer: c [Reason:] Both dynamic programming and recursion can be used to solve the edit distance problem.

2. The edit distance satisfies the axioms of a metric when the costs are non-negative.
a) True
b) False

View Answer

Answer: a [Reason:] d(s,s) = 0, since each string can be transformed into itself without any change. d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation. d(s1, s2) = d(s2, s1) d(s1, s3) <= d(s1, s2) + d(s2, s3) Thus, the edit distance satisfies the axioms of a metric.

3. Which of the following is an application of the edit distance problem?
a) Approximate string matching
b) Spelling correction
c) Similarity of DNA
d) All of the mentioned

View Answer

Answer: d [Reason:] All of the mentioned are the applications of the edit distance problem.

4. In which of the following cases will the edit distance between two strings be zero?
a) When one string is a substring of another
b) When the lengths of the two strings are equal
c) When the two strings are equal
d) The edit distance can never be zero

View Answer

Answer: c [Reason:] The edit distance will be zero only when the two strings are equal.

5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
a) True
b) False

View Answer

Answer: a [Reason:] Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.

6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
a) 3
b) 4
c) 5
d) 6

View Answer

Answer: b [Reason:] “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.

7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
a) 0
b) 4
c) None of the mentioned
d) Cannot be determined

View Answer

Answer: b [Reason:] The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.

8. Consider the following dynamic programming implementation of the edit distance problem:

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
_____________;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "defg";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[i-1][j] = min
b) arr[i][j-1] = min
c) arr[i-1][j-1] = min
d) arr[i][j] = min

View Answer

Answer: d [Reason:] The line arr[i][j] = min completes the above code.

9. What is the time complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings?
a) O(1)
b) O(m + n)
c) O(mn)
d) None of the mentioned

View Answer

Answer: c [Reason:] The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

10. What is the space complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(m + n)
c) O(mn)
d) None of the mentioned

View Answer

Answer: c [Reason:] The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

11. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "defg";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}

a) 1
b) 2
c) 3
d) 4

View Answer

Answer: d [Reason:] The program prints the edit distance between the strings “abcd” and “defg”, which is 4.

12. What is the value stored in arr[2][2] when the following code is executed?

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "defg";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}

a) 1
b) 2
c) 3
d) 4

View Answer

Answer: b [Reason:] The value stored in arr[2][2] when the above code is executed is 2.

13. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "pqrstuv", s2[] = "prstuv";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}

a) 1
b) 2
c) 3
d) 4

View Answer

Answer: a [Reason:] The code prints the edit distance between the two strings, which is 1.

Set 2

1. The following sequence is a fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a) Recursion
b) Dynamic programming
c) A single for loop
d) All of the mentioned

View Answer

Answer: d [Reason:] Each of the above mentioned methods can be used to find the nth fibonacci term.

2. Consider the recursive implementation to find the nth fibonacci number:

int fibo(int n)
if n <= 1
return n
return __________

Which line would make the implementation complete?
a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)

View Answer

Answer: d [Reason:] Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by: fibo(n) = fibo(n-1) + fibo(n-2).

3. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n2)
c) O(n!)
d) Exponential

View Answer

Answer: d [Reason:] The recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). So, the time complexity is given by: T(n) = T(n – 1) + T(n – 2) Approximately, T(n) = 2 * T(n – 1) = 4 * T(n – 2) = 8 * T(n – 3) : : : = 2k * T(n – k) This recurrence will stop when n – k = 0 i.e. n = k Therefore, T(n) = 2n * O(0) = 2n Hence, it takes exponential time. It can also be proved by drawing the recursion tree and counting the number of leaves.

4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) + fibonacci(3)	+ fibonacci(3) + fibonacci(2)
:
:
:

Which property is shown by the above function calls?
a) Memoization
b) Optimal substructure
c) Overlapping subproblems
d) Greedy

View Answer

Answer: c [Reason:] From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

5. What is the output of the following program?

#include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n;
return fibo(n-1) + fibo(n-2);
}
int main()
{   
int r = fibo(50000);
printf("%d",r); 
return 0;
}

a) 1253556389
b) 5635632456
c) Garbage value
d) Runtime error
e) Compile time error

View Answer

Answer: d [Reason:] The value of n is 50000. The function is recursive and it’s time complexity is exponential. So, the function will be called almost 250000 times. Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous. Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program. So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing runtime error.

6. What is the space complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

View Answer

Answer: a [Reason:] The recursive implementation doesn’t store any values and calculates every value from scratch. So, the space complexity is O(1).

7. Consider the following code to find the nth fibonacci term:

int fibo(int n)
if n == 0
return 0 
else
prevFib = 0
curFib = 1
for i : 1 to n-1
nextFib = prevFib + curFib
__________
__________
return curFib

Complete the above code.
a) prevFib = curFib
curFib = curFib
b) prevFib = nextFib
curFib = prevFib
c) prevFib = curFib
curFib = nextFib
d) none of the mentioned

View Answer

Answer: c [Reason:] The lines, prevFib = curFib and curFib = nextFib, make the code complete.

8. What is the time complexity of the ABOVE for loop method used to compute the nth fibonacci term ?
a) O(1)
b) O(n)
c) O(n2)
d) Exponential

View Answer

Answer: b [Reason:] To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

9. What is the space complexity of the ABOVE for loop method used to compute the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) Exponential

View Answer

Answer: a [Reason:] To calculate the nth term, we just store the previous term and the current term and then calculate the next term using these two terms. It takes a constant space to store these two terms and hence O(1) is the answer.

10. What will be the output when the following code is executed?

#include<stdio.h>
int fibo(int n)
{
if(n==0)
return 0;
int i;
int prevFib=0,curFib=1;
for(i=1;i<=n-1;i++)
{
int nextFib = prevFib + curFib;
prevFib = curFib;
curFib = nextFib;
}
return curFib;
}
int main()
{
int r = fibo(10);  
printf("%d",r);
return 0;
}

a) 34
b) 55
c) Compile error
d) Runtime error

View Answer

Answer: b [Reason:] The output is the 10th fibonacci number, which is 55.

11. Consider the following code to find the nth fibonacci term using dynamic programming:

1.int fibo(int n)
2.   int fibo_terms[100000]  //arr to store the fibonacci numbers
3.   fibo_terms[0] = 0
4.   fibo_terms[1] = 1
5.		
6.   for i: 2 to n
7.	 fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.   return fibo_terms[n]

Which property is shown by line 7 of the above code?
a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) None of the mentioned

View Answer

Answer: a [Reason:] We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.

12. Consider the following code to find the nth fibonacci term using dynamic programming:

1.int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Which technique is used by line 7 of the above code?
a) Greedy
b) Recursion
c) Memoization
d) None of the mentioned

View Answer

Answer: c [Reason:] Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.

13. What is the time complexity of the ABOVE dynamic programming implementation used to compute the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) Exponential

View Answer

Answer: b [Reason:] To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

14. What is the space complexity of the ABOVE dynamic programming implementation used to compute the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) Exponential

View Answer

Answer: b [Reason:] To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.

15. What will be the output when the following code is executed?

#include<stdio.
int fibo(int n)
{
int i;
int fibo_terms[100];
fibo_terms[0]=0;
fibo_terms[1]=1;
for(i=2;i<=n;i++)
fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
return fibo_terms[n];
}
int main()
{
int r = fibo(8);
printf("%d",r);
return 0;
}

a) 34
b) 55
c) Compile error
d) 21

View Answer

Answer: d [Reason:] The program prints the 8th fibonacci term, which is 21.

Set 3

1. Kadane’s algorithm is used to find ____________
a) Longest increasing subsequence
b) Longest palindrome subsequence
c) Maximum sub-array sum
d) All of the mentioned

View Answer

Answer: c [Reason:] Kadane’s algorithm is used to find the maximum sub-array sum for a given array.

2. Kadane’s algorithm uses which of the following techniques?
a) Divide and conquer
b) Dynamic programming
c) Recursion
d) All of the mentioned

View Answer

Answer: b [Reason:] Kadane’s algorithm uses dynamic programming.

3. For which of the following inputs would Kadane’s algorithm produce the CORRECT output?
a) {0,1,2,3}
b) {-1,0,1}
c) {-1,-2,-3,0}
d) All of the mentioned

View Answer

Answer: d [Reason:] Kadane’s algorithm works if the input array contains at least one non-negative element. All the array inputs have at least one non-negative element. So, Kadane’s algorithm will produce the right output for all of the mentioned inputs.

4. For which of the following inputs would Kadane’s algorithm produce a WRONG output?
a) {1,0,-1}
b) {-1,-2,-3}
c) {1,2,3}
d) {0,0,0}

View Answer

Answer: b [Reason:] Kadane’s algorithm doesn’t work for all negative numbers. So, the answer is {-1,-2,-3}.

5. Complete the following code for Kadane’s algorithm:

#include<stdio.h>
int max_num(int a, int b)
{ 
if(a > b)
return a; 
return b;
}
int kadane_algo(int *arr, int len)
{	
int ans, sum, idx;
ans =0;
sum =0;
for(idx =0; idx < len; idx++)
{
sum = max_num(0,sum + arr[idx]);
ans = ___________;
}
return ans;
}
int main()
{
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3},len=7;
int ans = kadane_algo(arr,len);
printf("%d",ans);
return 0;
}

a) max_num(sum, sum + arr[idx])
b) sum
c) sum + arr[idx].
d) max_num(sum,ans)

View Answer

Answer: d [Reason:] The maximum of sum and ans, is stored in ans. So, the answer is max_num(sum, ans).

6. What is the time complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

View Answer

Answer: b [Reason:] The time complexity of Kadane’s algorithm is O(n) because there is only one for loop which scans the entire array exactly once.

7. What is the space complexity of Kadane’s algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

View Answer

Answer: a [Reason:] Kadane’s algorithm uses a constant space. So, the space complexity is O(1).

8. What is the output of the following implementation of Kadane’s algorithm?

#include<stdio.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int kadane_algo(int *arr, int len)	
{
int ans, sum, idx;
ans =0;
sum =0;
for(idx =0; idx < len; idx++)
{
sum = max_num(0,sum + arr[idx]);
ans = max_num(sum,ans);
}
return ans;
}
int main()
{
int arr[] = {2, 3, -3, -1, 2, 1, 5, -3}, len = 8;
int ans = kadane_algo(arr,len);
printf("%d",ans);
return 0;
}

a) 6
b) 7
c) 8
d) 9

View Answer

Answer: d [Reason:] Kadane’s algorithm produces the maximum sub-array sum, which is equal to 9.

9. What is the output of the following implementation of Kadane’s algorithm?

#include<stdio.h>
int max_num(int a, int b)
{  
if(a > b)
return a;
return b;
}
int kadane_algo(int *arr, int len)	
{
int ans, sum, idx;
ans =0;
sum =0;
for(idx =0; idx < len; idx++)
{
sum = max_num(0,sum + arr[idx]);
ans = max_num(sum,ans);
}
return ans;
}
int main()
{
int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8;
int ans = kadane_algo(arr,len);
printf("%d",ans);
return 0;
}

a) 1
b) -1
c) -2
d) None of the mentioned

View Answer

Answer: d [Reason:] Kadane’s algorithm produces a wrong output when all the elements are negative. The output produced is 0.

10. Consider the following implementation of Kadane’s algorithm:

1. #include<stdio.h>
2. int max_num(int a, int b)
3. {
4.     if(a > b)
5.	 return a;
6.     return b;
7. }
8. int kadane_algo(int *arr, int len)	
9. {
10.      int ans = 0, sum = 0, idx;
11.	 for(idx =0; idx < len; idx++)
12.	 {
13.		sum = max_num(0,sum + arr[idx]);
14.		ans = max_num(sum,ans);
15.	 }
16.	 return ans;
17. }
18. int main()
19. {
20. 	  int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8;
21.       int ans = kadane_algo(arr,len);
22.	  printf("%d",ans);
23.	  return 0;
24. }

What changes should be made to the Kadane’s algorithm so that it produces the right output even when all array elements are negative?

	Change 1 = Line 10: int sum = arr[0], ans = arr[0]
Change 2 = Line 13: sum = max_num(arr[idx],sum+arr[idx])

a) Only Change 1 is sufficient
b) Only Change 2 is sufficient
c) Both Change 1 and Change 2 are necessary
d) None of the mentioned

View Answer

Answer: c [Reason:] Both change 1 and change 2 should be made to Kadane’s algorithm so that it produces the right output even when all the array elements are negative.

Set 4

1. Which of the following methods can be used to solve the longest common subsequence problem?
a) Recursion
b) Dynamic programming
c) Both recursion and dynamic programming
d) None of the mentioned

View Answer

Answer: c [Reason:] Both recursion and dynamic programming can be used to solve the longest subsequence problem.

2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
a) 9
b) 8
c) 7
d) 6

View Answer

Answer: c [Reason:] The longest common subsequence is “PRTPQRS” and its length is 7.

3. Which of the following problems can be solved using the longest subsequence problem?
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) None of the mentioned

View Answer

Answer: b [Reason:] To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.

4. Longest common subsequence is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

View Answer

Answer: b [Reason:] Longest common subsequence is an example of 2D dynamic programming.

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)

View Answer

Answer: d [Reason:] The time complexity of the brute force algorithm used to find the longest common subsequence is O(2n).

6. Consider the following dynamic programming implementation of the longest common subsequence problem:

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2;
len1 = strlen(str1);
len2 = strlen(str2);
int arr[len1 + 1][len2 + 1];
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
______________;
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = " abcedfg", str2[] = "bcdfh";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}

Which of the following lines completes the above code?
a) arr[i][j] = 1 + arr[i][j].
b) arr[i][j] = 1 + arr[i – 1][j – 1].
c) arr[i][j] = arr[i – 1][j – 1].
d) arr[i][j] = arr[i][j].

View Answer

Answer: b [Reason:] The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.

7. What is the time complexity of the above dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?
a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)

View Answer

Answer: d [Reason:] The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

8. What is the space complexity of the above dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?
a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)

View Answer

Answer: d [Reason:] The space complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

9. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2;
len1 = strlen(str1);
len2 = strlen(str2);
int arr[len1 + 1][len2 + 1];
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}

a) 3
b) 4
c) 5
d) 6

View Answer

Answer: b [Reason:] The program prints the length of the longest common subsequence, which is 4.

10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?
a) hgmq
b) cfnq
c) bfmq
d) all of the mentioned

View Answer

Answer: d [Reason:] The length of the longest common subsequence is 4 and all of the mentioned subsequences are the longest common subsequences with length 4.

11. What is the value stored in arr[2][3] when the following code is executed?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2;
len1 = strlen(str1);
len2 = strlen(str2);
int arr[len1 + 1][len2 + 1];
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}

a) 1
b) 2
c) 3
d) 4

View Answer

Answer: a [Reason:] The value stored in arr[2][3] is 1.

12. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2;
len1 = strlen(str1);
len2 = strlen(str2);
int arr[len1 + 1][len2 + 1];
for(i = 0; i <= len1; i++)
arr[i][0] = 0;
for(i = 0; i <= len2; i++)
arr[0][i] = 0;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len1][len2];
}
int main()
{
char str1[] = "abcd", str2[] = "efgh";
int ans = lcs(str1,str2);
printf("%d",ans);
return 0;
}

a) 3
b) 2
c) 1
d) 0

View Answer

Answer: d [Reason:] The program prints the length of the longest common subsequence, which is 0.

Set 5

1. The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using __________
a) Recursion
b) Dynamic programming
c) Brute force
d) All of the mentioned

View Answer

Answer: e [Reason:] The longest increasing subsequence problem can be solved using all of the mentioned methods.

2. Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}

View Answer

Answer: d [Reason:] The longest increasing subsequence is {-10, 9, 10, 13, 14}.

3. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6

View Answer

Answer: d [Reason:] The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.

4. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
a) True
b) False

View Answer

Answer: b [Reason:] For a given sequence, it is possible that there is more than one subsequence with the longest length. Consider, the following sequence: {10,11,12,1,2,3}: There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

5. The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6

View Answer

Answer: d [Reason:] Each array element individually forms a longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.

6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
a) O(n)
b) O(n2)
c) O(n!)
d) O(2n)

View Answer

Answer: d [Reason:] The time required to find all the subsequences of a given sequence is 2n, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2n).

7. Complete the following dynamic programming implementation of the longest increasing subsequence problem:

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len];  // array to store the lengths of the longest increasing subsequence 
LIS[0]=1;
for(i = 1; i < len; i++)
{ 
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
___________;  
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}

a) tmp_max = LIS[j].
b) LIS[i] = LIS[j].
c) LIS[j] = tmp_max
d) tmp_max = LIS[i].

View Answer

Answer: a [Reason:] tmp_max is used to store the maximum length of an increasing subsequence for any ‘j’ such that: arr[j] < arr[i] and 0 < j < i. So, tmp_max = LIS[j] completes the code.

8. What is the time complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?
a) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)

View Answer

Answer: c [Reason:] The time complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n2).

9. What is the space complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?
a) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)

View Answer

Answer: b [Reason:] The above dynamic programming implementation uses space equal to the length of the sequence. So, the space complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n).

10. What is the output of the following program?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len];  // array to store the lengths of the longest increasing subsequence 
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j];
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}

a) 3
b) 4
c) 5
d) 6

View Answer

Answer: d [Reason:] The program prints the length of the longest increasing subsequence, which is 6.

11. What is the value stored in LIS[5] after the following program is executed?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len];  // array to store the lengths of the longest increasing subsequence 
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j];
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}

a) 2
b) 3
c) 4
d) 5

View Answer

Answer: c [Reason:] The value stored in LIS[5] after the program is executed is 4.