Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
A
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
View Answer
A
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
View Answer
A
Q144: What is the complexity of the original recursive Fibonacci algorithm?
- A: Θ(φ^n)
- B: Θ(n)
- C: Θ(log n)
- D: Θ(n^2)
View Answer
A
Q145: Dynamic programming avoids ______.
- A: Recursion
- B: Repetition
- C: Iteration
- D: All of the above
View Answer
B
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
View Answer
A
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
View Answer
A
Q148: In the DP approach, how is the solution typically built?
- A: Bottom-up
- B: Top-down
- C: Sideways
- D: Inside-out
View Answer
A
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
View Answer
A
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
View Answer
A