1. Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?
Correct : D. peter ingerman
2. What happens when the value of k is 0 in the Floyd Warshall Algorithm?
Correct : B. 0 intermediate vertex
3. Using logical operator’s instead arithmetic operators saves time and space.
Correct : A. true
4. The time taken to compute the transitive closure of a graph is Theta(n2).
Correct : B. false
5. If a problem can be broken into subproblems which are reused several times, the problem possesses property.
Correct : A. overlapping subproblems
6. 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.
Correct : A. true
7. A greedy algorithm can be used to solve all the dynamic programming problems.
Correct : B. false
8. In dynamic programming, the technique of storing the previously calculated values is called
Correct : C. memoization
9. When a top-down approach of dynamic programming is applied to a problem, it usually
Correct : B. decreases the time complexity and increases the space complexity
10. Which of the following problems is NOT solved using dynamic programming?
Correct : D. fractional knapsack problem
11. Which of the following problems should be solved using dynamic programming?
Correct : C. longest common subsequence
12. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
Correct : D. exponential
13. What is the space complexity of the recursive implementation used to find the nth fibonacci term?
Correct : A. o(1)
14. return fibo_terms[n]
Correct : B. o(n)
15. 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
Correct : B. dynamic programming
16. 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?
Correct : D. 100
17. 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?
Correct : D. o(s*n)
18. You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?
Correct : B. 2
19. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
Correct : B. o(1)
20. Kadane’s algorithm is used to find
Correct : C. maximum sub-array sum
21. Kadane’s algorithm uses which of the following techniques?
Correct : B. dynamic programming
22. For which of the following inputs would Kadane’s algorithm produce a WRONG output?
Correct : B. {-1,-2,-3}
23. What is the time complexity of Kadane’s algorithm?
Correct : B. o(n)
24. What is the space complexity of Kadane’s algorithm?
Correct : A. o(1)
25. 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
Correct : D. recursion, dynamic programming, brute force
26. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
Correct : B. false
27. 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?
Correct : D. brute force, dynamic programming and recursion
28. 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?
Correct : D. o(2n)
29. For every rod cutting problem there will be a unique set of pieces that give the maximum price.
Correct : B. false
30. For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
Correct : A. true
31. 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.
Correct : B. false
32. What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?
Correct : B. o(n)
33. The Knapsack problem is an example of
Correct : B. 2d dynamic programming
34. Which of the following problems is equivalent to the 0-1 Knapsack problem?
Correct : B. 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
35. The 0-1 Knapsack problem can be solved using Greedy algorithm.
Correct : B. false
36. Which of the following methods can be used to solve the matrix chain multiplication problem?
Correct : D. dynamic programming, brute force, recursion
37. 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?
Correct : A. 18000
38. 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?
Correct : D. exponential
39. Which of the following methods can be used to solve the longest common subsequence problem?
Correct : C. both recursion and dynamic programming
40. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
Correct : C. 7
41. Which of the following problems can be solved using the longest subsequence problem?
Correct : B. longest palindromic subsequence
42. Longest common subsequence is an example of
Correct : B. 2d dynamic programming
43. What is the time complexity of the brute force algorithm used to find the longest common subsequence?
Correct : D. o(2n)
44. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?
Correct : D. fgmna
45. Which of the following methods can be used to solve the longest palindromic subsequence problem?
Correct : D. dynamic programming, recursion, brute force
46. Which of the following is not a palindromic subsequence of the string “ababcdabba”?
Correct : D. adba
47. For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?
Correct : D. some strings of length two
48. What is the length of the longest palindromic subsequence for the string “ababcdabba”?
Correct : B. 7
49. What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?
Correct : B. o(2n)
50. For every non-empty string, the length of the longest palindromic subsequence is at least one.
Correct : A. true
51. Longest palindromic subsequence is an example of
Correct : B. 2d dynamic programming
52. Which of the following methods can be used to solve the edit distance problem?
Correct : C. both dynamic programming and recursion
53. The edit distance satisfies the axioms of a metric when the costs are non-negative.
Correct : A. true
54. 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.
Correct : A. true
55. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
Correct : B. 4
56. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
Correct : B. 4
57. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
Correct : C. o(mn)
58. Which of the following is NOT a Catalan number?
Correct : D. 43
59. Which of the following methods can be used to find the nth Catalan number?
Correct : D. recursion, binomial coefficients, dynamic programming
60. Which of the following implementations of Catalan numbers has the smallest time complexity?
Correct : B. binomial coefficients
61. Which of the following methods can be used to solve the assembly line scheduling problem?
Correct : D. all of the mentioned
62. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?
Correct : D. o(2n)
63. In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
Correct : C. 2
64. What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
Correct : B. o(n)
65. 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?
Correct : D. both recursion and dynamic programming
66. In which of the following cases the minimum no of insertions to form palindrome is maximum?
Correct : D. non palindromic string
67. 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.
Correct : B. false
68. Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
Correct : A. 0
69. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
Correct : B. longest common subsequence problem
70. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
Correct : D. brute force, recursion, dynamic programming
71. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
Correct : A. when all the elements are negative
72. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
Correct : C. 12
73. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
Correct : B. -1
74. The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
Correct : C. kadane’s algorithm
75. Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?
Correct : D. dynamic programming, recursion, brute force
76. In which of the following cases, it is not possible to have two subsets with equal sum?
Correct : C. when the sum of elements is odd
77. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
Correct : D. o(2n)
78. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
Correct : A. 16
79. You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
Correct : D. brute force, recursion and dynamic programming
80. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?
Correct : B. f*f*f…n times
81. 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?
Correct : C. 216
82. You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?
Correct : C. 2
83. There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?
Correct : C. n
84. 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?
Correct : D. n*f
85. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?
Correct : A. 0
86. 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)?
Correct : C. 2
87. Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?
Correct : D. nth catalan number
88. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?
Correct : A. nth catalan number
89. Which of the following is true?
Correct : B. kruskal’s algorithm can also run on the disconnected graphs
90. Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
Correct : C. (a-d)(d-c)(d-b)(d-e)
91. Fractional knapsack problem is also known as
Correct : B. continuous knapsack problem
92. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
Correct : C. greedy algorithm
93. What is the objective of the knapsack problem?
Correct : A. to get maximum total value in the knapsack
94. Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
Correct : D. in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
95. Time complexity of fractional knapsack problem is
Correct : A. o(n log n)
96. Fractional knapsack problem can be solved in time O(n).
Correct : A. true
97. Find the maximum value output assuming items to be divisible.
Correct : A. 60
98. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
Correct : A. true
99. The main time taking step in fractional knapsack problem is
Correct : C. sorting
100. Find the maximum value output assuming items to be divisible and nondivisible respectively.