Design And Analysis Of Algorithms Set 10

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 10

Q1 | What is the space complexity of Kadane’s algorithm?
  • o(1)
  • o(n)
  • o(n2)
  • none of the mentioned
Answer: o(1)
Explaination:
kadane’s algorithm uses a constant space. so, the space complexity is
Q2 | 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
  • recursion
  • dynamic programming
  • brute force
  • recursion, dynamic programming, brute force
Answer: recursion, dynamic programming, brute force
Explaination:
the longest increasing subsequence problem can be solved using all of the mentioned methods.
Q3 | For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
  • true
  • false
Answer: false
Explaination:
for a given sequence, it is possible that there is more than one subsequence with the longest length.
Q4 | Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
  • brute force
  • dynamic programming
  • recursion
  • brute force, dynamic programming and recursion
Answer: brute force, dynamic programming and recursion
Explaination:
brute force, dynamic programming and recursion can be used to solve the rod cutting problem.
Q5 | Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
  • o(n2)
  • o(n3)
  • o(nlogn)
  • o(2n)
Answer: o(2n)
Explaination:
the brute force implementation finds all the possible cuts. this takes o(2n) time.
Q6 | For every rod cutting problem there will be a unique set of pieces that give the maximum price.
  • true
  • false
Answer: false
Explaination:
consider a rod of length 3. the prices are {2,3,6} for lengths {1,2,3} respectively. the pieces {1,1,1} and {3} both give the maximum value of 6.
Q7 | For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
  • true
  • false
Answer: true
Explaination:
consider the array {1,2,3,4,5}. it is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.
Q8 | For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
  • true
  • false
Answer: false
Explaination:
consider the array {1,0,2,3,4}.
Q9 | What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?
  • o(1)
  • o(n)
  • o(n2)
  • o(5)
Answer: o(n)
Explaination:
the space complexity of the above dynamic programming implementation is o(n).
Q10 | The Knapsack problem is an example of
  • greedy algorithm
  • 2d dynamic programming
  • 1d dynamic programming
  • divide and conquer
Answer: 2d dynamic programming
Explaination:
knapsack problem is an example of 2d dynamic programming.
Q11 | Which of the following problems is equivalent to the 0-1 Knapsack problem?
  • you are given a bag that can carry a maximum weight of w. you are given n items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value
  • you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized
  • you are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum s. you have to find the minimum number of coins required to get the sum s
  • you are given a suitcase that can carry a maximum weight of 15kg. you are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value
Answer: you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized
Explaination:
in this case, questions are used instead of items. each question has a score which is same as each item having a value.
Q12 | The 0-1 Knapsack problem can be solved using Greedy algorithm.
  • true
  • false
Answer: false
Explaination:
the knapsack problem cannot be solved using the greedy algorithm.
Q13 | Which of the following methods can be used to solve the matrix chain multiplication problem?
  • dynamic programming
  • brute force
  • recursion
  • dynamic programming, brute force, recursion
Answer: dynamic programming, brute force, recursion
Explaination:
dynamic programming, brute force, recursion methods can be used to solve the matrix chain multiplication problem.
Q14 | Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?
  • 18000
  • 12000
  • 24000
  • 32000
Answer: 18000
Explaination:
the minimum number of multiplications are 18000. this is the case when the matrices are parenthesized as (p*q)*r.
Q15 | Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?
  • o(n!)
  • o(n3)
  • o(n2)
  • exponential
Answer: exponential
Explaination:
the time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th catalan number which is exponential.
Q16 | Which of the following methods can be used to solve the longest common subsequence problem?
  • recursion
  • dynamic programming
  • both recursion and dynamic programming
  • greedy algorithm
Answer: both recursion and dynamic programming
Explaination:
both recursion and dynamic programming can be used to solve the longest subsequence problem.
Q17 | Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
  • 9
  • 8
  • 7
  • 6
Answer: 7
Explaination:
the longest common subsequence is “prtpqrs” and its length is 7.
Q18 | Which of the following problems can be solved using the longest subsequence problem?
  • longest increasing subsequence
  • longest palindromic subsequence
  • longest bitonic subsequence
  • longest decreasing subsequence
Answer: longest palindromic subsequence
Explaination:
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.
Q19 | Longest common subsequence is an example of                          
  • greedy algorithm
  • 2d dynamic programming
  • 1d dynamic programming
  • divide and conquer
Answer: 2d dynamic programming
Explaination:
longest common subsequence is an example of 2d dynamic programming.
Q20 | What is the time complexity of the brute force algorithm used to find the longest common subsequence?
  • o(n)
  • o(n2)
  • o(n3)
  • o(2n)
Answer: o(2n)
Explaination:
the time complexity of the brute force algorithm used to find the longest common subsequence is o(2n).
Q21 | Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?
  • hgmq
  • cfnq
  • bfmq
  • fgmna
Answer: fgmna
Explaination:
the length of the longest common subsequence is 4. but ‘fgmna’ is not the longest common subsequence as its length is 5.
Q22 | Which of the following methods can be used to solve the longest palindromic subsequence problem?
  • dynamic programming
  • recursion
  • brute force
  • dynamic programming, recursion, brute force
Answer: dynamic programming, recursion, brute force
Explaination:
dynamic programming, recursion, brute force can be used to solve the longest palindromic subsequence problem.
Q23 | Which of the following is not a palindromic subsequence of the string “ababcdabba”?
  • abcba
  • abba
  • abbbba
  • adba
Answer: adba
Explaination:
‘adba’ is not a palindromic sequence.
Q24 | For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?
  • a string that is a palindrome
  • a string of length one
  • a string that has all the same letters(e.g. aaaaaa)
  • some strings of length two
Answer: some strings of length two
Explaination:
a string of length 2 for eg: ab is not a palindrome.
Q25 | What is the length of the longest palindromic subsequence for the string “ababcdabba”?
  • 6
  • 7
  • 8
  • 9
Answer: 7
Explaination:
the longest palindromic subsequence is “abbabba” and its length is 7.
Previous Next