Wagner-Fischer algorithm is used to find ____________

Edit distance between two strings

Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

Minimum number of jumps problem

Longest common subsequence problem

In which of the following cases will the number of insertions to form a palindrome be minimum?

String with all same characters

Which of the following lines should be added to complete the “if(op[k] == '&')” part of the above code?

True[row][col] += True[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

True[row][col] += False[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

True[row][col] += True[row][pos] * True[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

True[row][col] += True[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

True[row][col] += False[row][pos] * True[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

Which of the following is/are applications of Catalan numbers?

Counting the number of Dyck words

Counting the number of expressions containing n pairs of parenthesis

Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines

111 + Mcqs in Dynamic Programming in Data Structures and Algorithms Page 1 McqOptions

1.	When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.
A.	True
B.	False
Answer» B. False

Discussion

2.	What is the time complexity of the above dynamic programming implementation of the minimum number of insertions to form a palindrome problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

3.	Which of the following numbers is the 6th Catalan number?
A.	14
B.	429
C.	132
D.	None of the mentioned
Answer» E.

Discussion

4.	What is the time complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

5.	The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
A.	Hirschberg's algorithm
B.	Needleman-Wunsch algorithm
C.	Kadane's algorithm
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

6.	Consider the expression T \| F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?
A.	0
B.	1
C.	2
D.	3
Answer» C. 2

Discussion

7.	When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.
A.	True
B.	False
Answer» B. False

Discussion

8.	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)
Answer» B. O(n)

Discussion

9.	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
Answer» C. None of the mentioned

Discussion

10.	Which of the following implementations of Catalan numbers has the largest space complexity(Don't consider the stack space)?
A.	Dynamic programming
B.	Binomial coefficients
C.	Recursion
D.	All of the mentioned
Answer» B. Binomial coefficients

Discussion

11.	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}
Answer» C. {1,2,3}

Discussion

12.	Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
A.	0
B.	1
C.	2
D.	3
Answer» B. 1

Discussion

13.	What is the time complexity of Kadane's algorithm?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» C. O(n2)

Discussion

14.	What is the space complexity of the above dynamic programming implementation of the maximum sum rectangle problem?
A.	O(row*col)
B.	O(row)
C.	O(col)
D.	O(rowcolcol)
Answer» C. O(col)

Discussion

15.	What is the space complexity of the ABOVE recursive implementation?
A.	O(1)
B.	O(logn)
C.	O(nlogn)
D.	O(n!)
Answer» B. O(logn)

Discussion

16.	What is the time complexity of the Wagner-Fischer algorithm where “m” and “n” are the lengths of the two strings?
A.	O(1)
B.	O(n+m)
C.	O(mn)
D.	O(nlogm)
Answer» D. O(nlogm)

Discussion

17.	What is the space complexity of the above dynamic programming implementation of the minimum number of insertions to form a palindrome problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

18.	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)
Answer» E.

Discussion

19.	Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
A.	0
B.	1
C.	2
D.	3
Answer» D. 3

Discussion

20.	What is the time complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
A.	O(n)
B.	O(logn)
C.	O(nlogn)
D.	O(n2)
Answer» B. O(logn)

Discussion

21.	What is the space complexity of the ABOVE dynamic programming implementation of the rod cutting problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(2n)
Answer» C. O(n2)

Discussion

22.	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
Answer» E.

Discussion

23.	Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
A.	9
B.	8
C.	7
D.	6
Answer» D. 6

Discussion

24.	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)
Answer» C. O(n2)

Discussion

25.	What is the space complexity of the above dynamic programming implementation of the matrix chain problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(n3)
Answer» D. O(n3)

Discussion

26.	Wagner-Fischer algorithm is used to find ____________
A.	Longest common subsequence
B.	Longest increasing subsequence
C.	Edit distance between two strings
D.	All of the mentioned
Answer» D. All of the mentioned

Discussion

27.	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
Answer» D. None of the mentioned

Discussion

28.	What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
A.	O(n)
B.	O(n2)
C.	O(n3)
D.	O(n4)
Answer» E.

Discussion

29.	What is the space complexity of the naive method used to find the maximum sub-array sum in an array containing n elements?
A.	O(n2)
B.	O(1)
C.	O(n3)
D.	O(n)
Answer» C. O(n3)

Discussion

30.	Kadane's algorithm uses which of the following techniques?
A.	Divide and conquer
B.	Dynamic programming
C.	Recursion
D.	All of the mentioned
Answer» C. Recursion

Discussion

31.	You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?
A.	27
B.	36
C.	216
D.	81
Answer» D. 81

Discussion

32.	Wagner-Fischer is a ____________ algorithm.
A.	Brute force
B.	Greedy
C.	Dynamic programming
D.	Recursive
Answer» D. Recursive

Discussion

33.	Which of the following is NOT a Catalan number?
A.	1
B.	5
C.	14
D.	43
Answer» E.

Discussion

34.	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
Answer» C. O(n2)

Discussion

35.	Which of the following implementations of Catalan numbers has the smallest time complexity?
A.	Dynamic programming
B.	Binomial coefficients
C.	Recursion
D.	All of the mentioned
Answer» C. Recursion

Discussion

36.	Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?
A.	0
B.	1
C.	2
D.	3
Answer» C. 2

Discussion

37.	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)
Answer» E.

Discussion

38.	Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
A.	Minimum number of jumps problem
B.	Longest common subsequence problem
C.	Coin change problem
D.	None of the mentioned
Answer» C. Coin change problem

Discussion

39.	What is the space complexity of the above dynamic programming implementation of the Knapsack problem?
A.	O(n)
B.	O(n + w)
C.	O(nW)
D.	O(n2)
Answer» D. O(n2)

Discussion

40.	There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?
A.	1
B.	f*f
C.	n*n
D.	n*f
Answer» E.

Discussion

41.	What is the time complexity of the ABOVE dynamic programming implementation of the rod cutting problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(2n)
Answer» D. O(2n)

Discussion

42.	What is the time complexity of the above dynamic programming implementation of the maximum sum rectangle problem?
A.	O(row*col)
B.	O(row)
C.	O(col)
D.	O(rowcolcol)
Answer» E.

Discussion

43.	What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
A.	O(n)
B.	O(1)
C.	O(n!)
D.	O(n2)
Answer» C. O(n!)

Discussion

44.	In which of the following cases will the number of insertions to form a palindrome be minimum?
A.	String of length one
B.	String with all same characters
C.	Palindromic string
D.	All of the mentioned
Answer» E.

Discussion

45.	What is the space complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
A.	O(n)
B.	O(1)
C.	O(n!)
D.	O(n2)
Answer» B. O(1)

Discussion

46.	Which of the following lines should be added to complete the “if(op[k] == '&')” part of the above code?
A.	True[row][col] += False[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
B.	True[row][col] += True[row][pos] * True[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];
C.	True[row][col] += True[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
D.	True[row][col] += False[row][pos] * True[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];
Answer» C. True[row][col] += True[row][pos] * False[pos+1][col]; False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

Discussion

47.	Which of the following is/are applications of Catalan numbers?
A.	Counting the number of Dyck words
B.	Counting the number of expressions containing n pairs of parenthesis
C.	Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines
D.	All of the mentioned
Answer» E.

Discussion

48.	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)
Answer» D. O(nlogn)

Discussion

49.	What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(n3)
Answer» C. O(n2)

Discussion

50.	What is the space complexity of Kadane's algorithm?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» B. O(n)

Discussion

Explore topic-wise MCQs in Data Structures and Algorithms.

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.

What is the time complexity of the above dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

Which of the following numbers is the 6th Catalan number?

What is the time complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?

The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?

Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.

What is the space complexity of the recursive implementation used to find the nth fibonacci term?

Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

Which of the following implementations of Catalan numbers has the largest space complexity(Don't consider the stack space)?

For which of the following inputs would Kadane's algorithm produce a WRONG output?

Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?

What is the time complexity of Kadane's algorithm?

What is the space complexity of the above dynamic programming implementation of the maximum sum rectangle problem?

What is the space complexity of the ABOVE recursive implementation?

What is the time complexity of the Wagner-Fischer algorithm where “m” and “n” are the lengths of the two strings?

What is the space complexity of the above dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

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”?

Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

What is the time complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?

What is the space complexity of the ABOVE dynamic programming implementation of the rod cutting problem?

Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

What is the space complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?

What is the space complexity of the above dynamic programming implementation of the matrix chain problem?

Wagner-Fischer algorithm is used to find ____________

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?

What is the time complexity of the brute force implementation of the maximum sum rectangle problem?

What is the space complexity of the naive method used to find the maximum sub-array sum in an array containing n elements?

Kadane's algorithm uses which of the following techniques?

You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?

Wagner-Fischer is a ____________ algorithm.

Which of the following is NOT a Catalan number?

What is the space complexity of the ABOVE dynamic programming implementation used to compute the nth fibonacci term?

Which of the following implementations of Catalan numbers has the smallest time complexity?

Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?

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”?

Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

What is the space complexity of the above dynamic programming implementation of the Knapsack problem?

There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?

What is the time complexity of the ABOVE dynamic programming implementation of the rod cutting problem?

What is the time complexity of the above dynamic programming implementation of the maximum sum rectangle problem?

What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?

In which of the following cases will the number of insertions to form a palindrome be minimum?

What is the space complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?

Which of the following lines should be added to complete the “if(op[k] == '&')” part of the above code?

Which of the following is/are applications of Catalan numbers?

What is the time complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?

What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?

What is the space complexity of Kadane's algorithm?