Design And Analysis Of Algorithms Set 9

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 9

Q1 | Floyd- Warshall algorithm was proposed by                          
  • robert floyd and stephen warshall
  • stephen floyd and robert warshall
  • bernad floyd and robert warshall
  • robert floyd and bernad warshall
Answer: robert floyd and stephen warshall
Explaination:
floyd- warshall algorithm was proposed by robert floyd in the year 1962.
Q2 | Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?
  • robert floyd
  • stephen warshall
  • bernard roy
  • peter ingerman
Answer: peter ingerman
Explaination:
the modern formulation of floyd-warshall algorithm as three nested for- loops was proposed by peter ingerman in the year 1962.
Q3 | What happens when the value of k is 0 in the Floyd Warshall Algorithm?
  • 1 intermediate vertex
  • 0 intermediate vertex
  • n intermediate vertices
  • n-1 intermediate vertices
Answer: 0 intermediate vertex
Explaination:
when k=0, a path from vertex i to vertex j has no intermediate vertices at all. such a path has at most one edge and hence dij(0) = wij.
Q4 | Using logical operator’s instead arithmetic operators saves time and space.
  • true
  • false
Answer: true
Explaination:
in computers, logical operations on single bit values execute faster than arithmetic operations on integer words of data.
Q5 | The time taken to compute the transitive closure of a graph is Theta(n2).
  • true
  • false
Answer: false
Explaination:
the time taken to compute the transitive closure of a graph is theta(n3).
Q6 | If a problem can be broken into subproblems which are reused several times, the problem possesses                           property.
  • overlapping subproblems
  • optimal substructure
  • memoization
  • greedy
Answer: overlapping subproblems
Explaination:
overlapping subproblems is the property in which value of a subproblem is used several times.
Q7 | 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.
  • true
  • false
Answer: true
Explaination:
dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. so, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.
Q8 | A greedy algorithm can be used to solve all the dynamic programming problems.
  • true
  • false
Answer: false
Explaination:
a greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may not result into a globally optimal solution. hence, a greedy algorithm cannot be used to solve all the dynamic programming problems.
Q9 | In dynamic programming, the technique of storing the previously calculated values is called                        
  • saving value property
  • storing value property
  • memoization
  • mapping
Answer: memoization
Explaination:
memoization is the technique
Q10 | When a top-down approach of dynamic programming is applied to a problem, it usually                            
  • decreases both, the time complexity and the space complexity
  • decreases the time complexity and increases the space complexity
  • increases the time complexity and decreases the space complexity
  • increases both, the time complexity and the space complexity
Answer: decreases the time complexity and increases the space complexity
Explaination:
the top-down approach uses the memoization technique which stores the previously calculated values. due to this, the time complexity is decreased but the space complexity is increased.
Q11 | Which of the following problems is NOT solved using dynamic programming?
  • 0/1 knapsack problem
  • matrix chain multiplication problem
  • edit distance problem
  • fractional knapsack problem
Answer: fractional knapsack problem
Explaination:
the fractional knapsack problem is solved using a greedy algorithm.
Q12 | Which of the following problems should be solved using dynamic programming?
  • mergesort
  • binary search
  • longest common subsequence
  • quicksort
Answer: longest common subsequence
Explaination:
the longest common subsequence problem has both, optimal substructure and overlapping subproblems. hence, dynamic programming should be used the solve this problem.
Q13 | What is the time complexity of the recursive implementation used to find the nth fibonacci term?
  • o(1)
  • o(n2)
  • o(n!)
  • exponential
Answer: exponential
Explaination:
the recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). so, the time complexity is given by:
Q14 | What is the space complexity of the recursive implementation used to find the nth fibonacci term?
  • o(1)
  • o(n)
  • o(n2)
  • o(n3)
Answer: o(1)
Explaination:
the recursive implementation doesn’t store any values and calculates every value from scratch. so, the space complexity is o(1).
Q15 | return fibo_terms[n]
  • o(1)
  • o(n)
  • o(n2)
  • exponential
Answer: o(n)
Explaination:
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.
Q16 | return fibo_terms[n]
  • o(1)
  • o(n)
  • o(n2)
  • exponential
Answer: o(n)
Explaination:
to calculate the nth term, we
Q17 | You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using
  • greedy algorithm
  • dynamic programming
  • divide and conquer
  • backtracking
Answer: dynamic programming
Explaination:
the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can
Q18 | Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
  • 14
  • 10
  • 6
  • 100
Answer: 100
Explaination:
using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. but, the optimal answer is two coins {3,3}. similarly, four coins {4,4,1,1} will be selected to make a sum of 10. but, the optimal answer is three coins {4,3,3}. also, five coins {4,4,4,1,1} will be selected to make a sum of 14. but, the optimal answer is four coins {4,4,3,3}. for a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.
Q19 | You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
  • o(n)
  • o(s)
  • o(n2)
  • o(s*n)
Answer: o(s*n)
Explaination:
the time complexity is o(s*n).
Q20 | You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
a sum of 7 can be achieved by using a minimum of two coins {3,4}.
Q21 | What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
  • o(n)
  • o(1)
  • o(n!)
  • o(n2)
Answer: o(1)
Explaination:
the divide and conquer algorithm uses a constant space. so, the space complexity is o(1).
Q22 | Kadane’s algorithm is used to find
  • longest increasing subsequence
  • longest palindrome subsequence
  • maximum sub-array sum
  • longest decreasing subsequence
Answer: maximum sub-array sum
Explaination:
kadane’s algorithm is used to find the maximum sub-array sum for a given array.
Q23 | Kadane’s algorithm uses which of the following techniques?
  • divide and conquer
  • dynamic programming
  • recursion
  • greedy algorithm
Answer: dynamic programming
Explaination:
kadane’s algorithm uses dynamic programming.
Q24 | For which of the following inputs would Kadane’s algorithm produce a WRONG output?
  • {1,0,-1}
  • {-1,-2,-3}
  • {1,2,3}
  • {0,0,0}
Answer: {-1,-2,-3}
Explaination:
kadane’s algorithm doesn’t work for all negative numbers. so, the answer is {-1,-2,-3}.
Q25 | What is the time complexity of Kadane’s algorithm?
  • o(1)
  • o(n)
  • o(n2)
  • o(5)
Answer: o(n)
Explaination:
the time complexity of kadane’s algorithm is o(n) because there is only one for loop which scans the entire array exactly once.
Previous Next