Design and Analysis of Algorithms MCQ Questions and answers

A

Admin • 833K Points
Coach

Q. 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)

A

Admin • 833K Points
Coach

Q. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

(A) greedy algorithm
(B) recursion
(C) dynamic programming
(D) both recursion and dynamic programming

A

Admin • 833K Points
Coach

Q. In which of the following cases the minimum no of insertions to form palindrome is maximum?

(A) string of length one
(B) string with all same characters
(C) palindromic string
(D) non palindromic string

Show Answer Discuss Share

A

Admin • 833K Points
Coach

Q. In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.

(A) true
(B) false
(C) answer: b
(D) explanation: in the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. for example, consider the string “abc”. the string can be converted to “abcba

A

Admin • 833K Points
Coach

Q. 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

A

Admin • 833K Points
Coach

Q. 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) knapsack problems

A

Admin • 833K Points
Coach

Q. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?

(A) brute force
(B) recursion
(C) dynamic programming
(D) brute force, recursion, dynamic programming

A

Admin • 833K Points
Coach

Q. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

(A) when all the elements are negative
(B) when all the elements are positive
(C) when some elements are positive and some negative
(D) when diagonal elements are positive and rest are negative

A

Admin • 833K Points
Coach

Q. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

(A) 3
(B) 6
(C) 12
(D) 18

A

Admin • 833K Points
Coach

Q. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?

(A) 0
(B) -1
(C) -7
(D) -12

Design and Analysis of Algorithms MCQs with answers Page - 39

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

Q. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

Q. In which of the following cases the minimum no of insertions to form palindrome is maximum?

Q. In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.

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

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

Q. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?

Q. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

Q. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

Q. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?

Add MCQ in this Category

Browse Categories