Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 6
Q161:
The base cases in the dynamic programming approach are used to fill which part of the E matrix?
A. The first row and first column
B. The middle of the matrix
C. The last row and last column
D. The entire matrix
Correct Answer:
A
Chapter: 6
Q162:
Which of the following statements about the edit distance is TRUE?
A. The edit distance is always zero for identical strings.
B. Edit distance can only be calculated for two strings.
C. Edit distance ignores character order.
D. None of the above
Correct Answer:
A
Chapter: 6
Q163:
If an algorithm has a time complexity of Θ(n^2), it means that:
A. The algorithm's running time increases quadratically with the input size.
B. The algorithm's running time remains constant regardless of input size.
C. The algorithm's running time increases linearly with the input size.
D. The algorithm's running time decreases with the input size.
Correct Answer:
A
Chapter: 6
Q164:
In the context of dynamic programming, what is the significance of arrows in the E matrix?
A. They indicate how each cell was computed.
B. They show the final result of the matrix.
C. They represent random choices made during computation.
D. They are not significant.
Correct Answer:
A
Chapter: 6
Q165:
If there are n matrices to multiply, how many ways can they be parenthesized?
A. 1
B. P(n-1)
C. P(n)
D. P(n-1)^2
Correct Answer:
A
Chapter: 6
Q166:
An edit script is generated by following paths from which cells?
A. E[0,0] to E[m,n]
B. E[m,n] to E[0,0]
C. E[i,j] to E[0,0]
D. None of the above
Correct Answer:
A
Chapter: 6
Q167:
What is the purpose of dynamic programming in the context of chain matrix multiplication?
A. To find the maximum product
B. To simplify matrix addition
C. To optimize the order of matrix multiplication
D. To eliminate matrices
Correct Answer:
A
Chapter: 6
Q168:
What does m[i, j] represent in the dynamic programming formulation?
A. The maximum number of multiplications
B. The minimum number of multiplications needed to compute Ai..j
C. The number of matrices in the chain
D. The order of multiplication
Correct Answer:
B
Chapter: 6
Q169:
In the recursive rule for chain matrix multiplication, what does the term pi−1pkpj represent?
A. The cost of multiplying the resulting matrices
B. The dimensions of the matrices involved
C. The number of matrices to be multiplied
D. The number of operations required for addition
Correct Answer:
A
Chapter: 6
Q170:
The algorithm for computing the minimum cost of chain matrix multiplication uses how many nested loops?
A. One
B. Two
C. Three
D. Four
Correct Answer:
C
Chapter: 6
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
Correct Answer:
B
Chapter: 6
Q172:
What is the final cost for multiplying the five matrices in the provided example?
A. 120
B. 88
C. 160
D. 263
Correct Answer:
C
Chapter: 6
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
Correct Answer:
B
Chapter: 6
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))
Correct Answer:
C
Chapter: 6
Q175:
What is the main goal of the 0/1 Knapsack Problem?
A. Maximize weight
B. Minimize weight
C. Maximize value
D. Minimize value
Correct Answer:
C
Chapter: 6
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
Correct Answer:
B
Chapter: 6
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)
Correct Answer:
C
Chapter: 6
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
Correct Answer:
C
Chapter: 6
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
Correct Answer:
A
Chapter: 6
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.
Correct Answer:
C