Design And Analysis Of Algorithms Set 12

On This Page

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

Q1 | The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
  • hirschberg’s algorithm
  • needleman-wunsch algorithm
  • kadane’s algorithm
  • wagner fischer algorithm
Q2 | 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?
  • dynamic programming
  • recursion
  • brute force
  • dynamic programming, recursion, brute force
Q3 | In which of the following cases, it is not possible to have two subsets with equal sum?
  • when the number of elements is odd
  • when the number of elements is even
  • when the sum of elements is odd
  • when the sum of elements is even
Q4 | What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
  • o(1)
  • o(n)
  • o(n2)
  • o(2n)
Q5 | What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
  • 16
  • 32
  • 64
Q6 | 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?
  • brute force
  • recursion
  • dynamic programming
  • brute force, recursion and dynamic programming
Q7 | 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?
  • n*n*n…f times
  • f*f*f…n times
  • n*n*n…n times
  • f*f*f…f times
Q8 | 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?
  • 27
  • 36
  • 216
  • 81
Q9 | 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?
  • 0
  • 1
  • 2
  • 3
Q10 | 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?
  • 1
  • f
  • n
  • n*f
Q11 | 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?
  • 1
  • f*f
  • n*n
  • n*f
Q12 | 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?
  • 0
  • 2
  • 4
  • 8
Q13 | 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)?
  • 0
  • 1
  • 2
  • 3
Q14 | Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?
  • n factorial
  • n square
  • n cube
  • nth catalan number
Q15 | 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?
  • nth catalan number
  • n factorial
  • n cube
  • n square
Q16 | Prim’s algorithm resembles Dijkstra’s algorithm.
  • true
  • false
Q17 | Which of the following is false about Prim’s algorithm?
  • it is a greedy algorithm
  • it constructs mst by selecting edges in increasing order of their weights
  • it never accepts cycles in the mst
  • it can be implemented using the fibonacci heap
Q18 | Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
  • (b-e)(g-e)(e-f)(d-f)
  • (b-e)(g-e)(e-f)(b-g)(d-f)
  • (b-e)(g-e)(e-f)(d-e)
  • (b-e)(g-e)(e-f)(d-f)(d-g)
Q19 | Which of the following is true?
  • prim’s algorithm can also be used for disconnected graphs
  • kruskal’s algorithm can also run on the disconnected graphs
  • prim’s algorithm is simpler than kruskal’s algorithm
  • in kruskal’s sort edges are added to mst in decreasing order of their weights
Q20 | Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
  • (a-c)(c-d)(d-b)(d-b)
  • (c-a)(a-d)(d-b)(d-e)
  • (a-d)(d-c)(d-b)(d-e)
  • (c-a)(a-d)(d-c)(d-b)(d-e)
Q21 | Fractional knapsack problem is also known as                      
  • 0/1 knapsack problem
  • continuous knapsack problem
  • divisible knapsack problem
  • non continuous knapsack problem
Q22 | Fractional knapsack problem is solved most efficiently by which of the following algorithm?
  • divide and conquer
  • dynamic programming
  • greedy algorithm
  • backtracking
Q23 | What is the objective of the knapsack problem?
  • to get maximum total value in the knapsack
  • to get minimum total value in the knapsack
  • to get maximum weight in the knapsack
  • to get minimum weight in the knapsack
Q24 | Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
  • in 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
  • both are the same
  • 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
  • in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
Q25 | Time complexity of fractional knapsack problem is                          
  • o(n log n)
  • o(n)
  • o(n2)
  • o(nw)