Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
A
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
View Answer
A
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.
View Answer
A
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.
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
B
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
View Answer
A
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
View Answer
C