Design And Analysis Of Algorithms Set 12 MCQs

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)