Design And Analysis Of Algorithms Set 11

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 11

Q1 | What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?
  • o(1)
  • o(2n)
  • o(n)
  • o(n2)
Answer: o(2n)
Explaination:
in the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. this takes exponential time.
Q2 | For every non-empty string, the length of the longest palindromic subsequence is at least one.
  • true
  • false
Answer: true
Explaination:
a single character of any string can always be considered as a palindrome and its length is one.
Q3 | Longest palindromic subsequence is an example of                              
  • greedy algorithm
  • 2d dynamic programming
  • 1d dynamic programming
  • divide and conquer
Answer: 2d dynamic programming
Explaination:
longest palindromic subsequence is an example of 2d dynamic programming.
Q4 | Which of the following methods can be used to solve the edit distance problem?
  • recursion
  • dynamic programming
  • both dynamic programming and recursion
  • greedy algorithm
Answer: both dynamic programming and recursion
Explaination:
both dynamic programming and recursion can be used to solve the edit distance problem.
Q5 | The edit distance satisfies the axioms of a metric when the costs are non-negative.
  • true
  • false
Answer: true
Explaination:
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.
Q6 | 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.
  • true
  • false
Answer: true
Explaination:
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.
Q7 | Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
  • 3
  • 4
  • 5
  • 6
Answer: 4
Explaination:
“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.
Q8 | Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
  • 0
  • 4
  • 2
  • 3
Answer: 4
Explaination:
the empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. thus, the edit distance is 4.
Q9 | What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
  • o(1)
  • o(n+m)
  • o(mn)
  • o(nlogm)
Answer: o(mn)
Explaination:
the time complexity of the wagner–fischer algorithm is o(mn).
Q10 | Which of the following is NOT a Catalan number?
  • 1
  • 5
  • 14
  • 43
Answer: 43
Explaination:
catalan numbers are given by: (2n!)/((n+1)!n!).
Q11 | Which of the following methods can be used to find the nth Catalan number?
  • recursion
  • binomial coefficients
  • dynamic programming
  • recursion, binomial coefficients, dynamic programming
Answer: recursion, binomial coefficients, dynamic programming
Explaination:
all of the mentioned methods can be used to find the nth catalan number.
Q12 | Which of the following implementations of Catalan numbers has the smallest time complexity?
  • dynamic programming
  • binomial coefficients
  • recursion
  • all have equal time complexity
Answer: binomial coefficients
Explaination:
The time complexities are as follows:Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).
Q13 | Which of the following methods can be used to solve the assembly line scheduling problem?
  • recursion
  • brute force
  • dynamic programming
  • all of the mentioned
Answer: all of the mentioned
Explaination:
all of the above mentioned methods can be used to solve the assembly line scheduling problem.
Q14 | What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?
  • o(1)
  • o(n)
  • o(n2)
  • o(2n)
Answer: o(2n)
Explaination:
in the brute force algorithm, all the possible ways are calculated which are of the order of 2n.
Q15 | In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
  • 0
  • 1
  • 2
  • 3
Answer: 2
Explaination:
in the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.
Q16 | What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
  • o(1)
  • o(n)
  • o(n2)
  • o(n3)
Answer: o(n)
Explaination:
the time complexity of the above dynamic programming implementation of the assembly line scheduling problem is o(n).
Q17 | 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?
  • greedy algorithm
  • recursion
  • dynamic programming
  • both recursion and dynamic programming
Answer: both recursion and dynamic programming
Explaination:
dynamic programming and recursion can be used to solve the problem.
Q18 | In which of the following cases the minimum no of insertions to form palindrome is maximum?
  • string of length one
  • string with all same characters
  • palindromic string
  • non palindromic string
Answer: non palindromic string
Explaination:
in string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. to convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.
Q19 | 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.
  • true
  • false
  • answer: b
  • 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” by inserting “a” and “b”. the number of insertions is two, which is equal to length minus one.
Answer: false
Explaination:
the string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. thus, only one insertion is required.
Q20 | Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
  • 0
  • 1
  • 2
  • 3
Answer: 0
Explaination:
the given string is already a palindrome. so, no insertions are required.
Q21 | 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
  • coin change problem
  • knapsack problems
Answer: longest common subsequence problem
Explaination:
a variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.
Q22 | Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
  • brute force
  • recursion
  • dynamic programming
  • brute force, recursion, dynamic programming
Answer: brute force, recursion, dynamic programming
Explaination:
brute force, recursion and dynamic programming can be used to find the submatrix that has the maximum sum.
Q23 | In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
  • when all the elements are negative
  • when all the elements are positive
  • when some elements are positive and some negative
  • when diagonal elements are positive and rest are negative
Answer: when all the elements are negative
Explaination:
when all the elements of a matrix are positive, the maximum sum rectangle is the 2d matrix itself.
Q24 | Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
  • 3
  • 6
  • 12
  • 18
Answer: 12
Explaination:
since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.
Q25 | Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
  • 0
  • -1
  • -7 d) -12
Answer: -1
Explaination:
since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. the sum of elements of the maximum sum rectangle is -1.
Previous Next