Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 6
Q141:
What is the base case for converting an empty string to a string of j characters in edit distance?
A. E(0, j) = j
B. E(j, 0) = j
C. E(i, 0) = i
D. E(i, j) = 0
Correct Answer:
A
Chapter: 6
Q142:
Which of the following is an example of an application of edit distance?
A. Spelling correction
B. Sorting algorithms
C. Binary search
D. Tree traversal
Correct Answer:
A
Chapter: 6
Q143:
What mathematical concept is used to describe the relationship between characters in the edit distance?
A. Optimal substructure
B. Recursion
C. Iteration
D. None of the above
Correct Answer:
A
Chapter: 6
Q144:
What is the complexity of the original recursive Fibonacci algorithm?
A. Θ(φ^n)
B. Θ(n)
C. Θ(log n)
D. Θ(n^2)
Correct Answer:
A
Chapter: 6
Q145:
Dynamic programming avoids ______.
A. Recursion
B. Repetition
C. Iteration
D. All of the above
Correct Answer:
B
Chapter: 6
Q146:
What are the two steps in developing a dynamic programming algorithm?
A. Formulate problem recursively and build solution from bottom up
B. Formulate problem iteratively and build solution from top down
C. Build a tree and evaluate the leaves
D. None of the above
Correct Answer:
A
Chapter: 6
Q147:
What is the purpose of the dynamic programming approach in recursion?
A. To simplify complex problems
B. To create infinite loops
C. To reduce memory usage
D. To increase code complexity
Correct Answer:
A
Chapter: 6
Q148:
In the DP approach, how is the solution typically built?
A. Bottom-up
B. Top-down
C. Sideways
D. Inside-out
Correct Answer:
A
Chapter: 6
Q149:
Which of the following describes how the E matrix is filled?
A. Row by row
B. Column by column
C. Diagonal only
D. Randomly
Correct Answer:
A
Chapter: 6
Q150:
What does the edit distance algorithm primarily calculate?
A. The minimum number of operations needed to transform one string into another
B. The longest common substring
C. The maximum length of a string
D. None of the above
Correct Answer:
A
Chapter: 6
Q151:
If a cell E[i,j] has a down arrow from E[i-1,j], what does it signify?
A. The minimum was found using E[i-1,j]
B. The minimum was found using E[i,j-1]
C. The minimum was found using E[i-1,j-1]
D. The cell is empty
Correct Answer:
A
Chapter: 6
Q152:
An edit script can be extracted by following a unique path from which cells?
A. E[0,0] to E[m,n]
B. E[0,0] to E[0,n]
C. E[i,j] to E[m,n]
D. None of the above
Correct Answer:
A
Chapter: 6
Q153:
How many entries are in the E matrix for the edit distance problem?
A. Θ(n)
B. Θ(n^2)
C. Θ(log n)
D. Θ(n^3)
Correct Answer:
B
Chapter: 6
Q154:
Matrix multiplication is:
A. Associative but not commutative
B. Commutative but not associative
C. Neither associative nor commutative
D. Both associative and commutative
Correct Answer:
A
Chapter: 6
Q155:
In the example with matrices A1, A2, and A3, which multiplication order is more efficient?
A. ((A1A2)A3)
B. A1(A2A3)
C. Both orders are equally efficient
D. Neither order is efficient
Correct Answer:
B
Chapter: 6
Q156:
What does the result of multiplying a p × q matrix with a q × r matrix yield?
A. A p × r matrix
B. A q × r matrix
C. A p × q matrix
D. A r × p matrix
Correct Answer:
A
Chapter: 6
Q157:
The number of different ways of parenthesizing n items is related to which mathematical concept?
A. Catalan numbers
B. Fibonacci numbers
C. Factorials
D. Prime numbers
Correct Answer:
A
Chapter: 6
Q158:
The total number of multiplications for multiplying matrices A1 (5×4), A2 (4×6), and A3 (6×2) in the order ((A1A2)A3) is:
A. 180
B. 88
C. 120
D. 72
Correct Answer:
A
Chapter: 6
Q159:
Dynamic programming can solve problems that involve:
A. Overlapping subproblems
B. Linear relationships
C. Static data
D. None of the above
Correct Answer:
A
Chapter: 6
Q160:
When applying dynamic programming, what does Θ(n^2) imply about time complexity?
A. Quadratic time complexity
B. Linear time complexity
C. Logarithmic time complexity
D. Constant time complexity
Correct Answer:
A