Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q171: The value of k in the matrix chain multiplication algorithm can be determined by which of the following methods?
- A: Guessing
- B: The best of all possible splits
- C: Trial and error
- D: Following a specific order
View Answer
B
Q172: What is the final cost for multiplying the five matrices in the provided example?
- A: 120
- B: 88
- C: 160
- D: 263
View Answer
C
Q173: The matrix m[i, j] will be filled using which method?
- A: Top-down approach
- B: Bottom-up approach
- C: Recursive function
- D: Iterative method
View Answer
B
Q174: The optimal multiplication order for the matrices A1, A2, A3, A4, and A5 can be represented as which of the following?
- A: (A1A2)(A3(A4A5))
- B: ((A1A2)(A3A4))
- C: ((A1(A2A3))(A4A5))
- D: (A1(A2A3A4A5))
View Answer
C
Q175: What is the main goal of the 0/1 Knapsack Problem?
- A: Maximize weight
- B: Minimize weight
- C: Maximize value
- D: Minimize value
View Answer
C
Q176: In the 0/1 Knapsack Problem, fractional items are:
- A: Allowed
- B: Not allowed
- C: Only for cheap items
- D: Only for expensive items
View Answer
B
Q177: The time complexity of the brute-force solution for the 0/1 Knapsack Problem is:
- A: O(n)
- B: O(n^2)
- C: O(2^n)
- D: O(n log n)
View Answer
C
Q178: Which of the following constraints is NOT a part of the 0/1 Knapsack Problem?
- A: Weight limit
- B: Maximum number of items
- C: Maximum value of items
- D: Weight of individual items
View Answer
C
Q179: In the dynamic programming approach, what does V[i, j] represent?
- A: The maximum value for the first i items and weight j
- B: The weight of the items
- C: The total number of items
- D: The total value of all items
View Answer
A
Q180: What does the Principle of Optimality state in the context of the 0/1 Knapsack Problem?
- A: Optimal solutions can be built from suboptimal ones.
- B: Optimal solutions cannot be built from smaller problems.
- C: Optimal solutions can be constructed from optimal solutions of smaller problems.
- D: There are no optimal solutions.
View Answer
C