Data Structure Multiple Choice Questions on “Edit Distance Problem”.
1. Which of the following methods can be used to solve the edit distance problem?
a) Recursion
b) Dynamic programming
c) Both dynamic programming and recursion
d) Greedy Algorithm
Answer: c
Clarification: Both dynamic programming and recursion can be used to solve the edit distance problem.
2. The edit distance satisfies the axioms of a metric when the costs are non-negative. Answer: a 3. Which of the following is an application of the edit distance problem? Answer: d 4. In which of the following cases will the edit distance between two strings be zero? 5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string. Answer: a 6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings? Answer: b 7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings? Answer: b 8. Consider the following dynamic programming implementation of the edit distance problem: Which of the following lines should be added to complete the above code? Answer: d 9. What is the time complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings? a) O(1) Answer: c 10. What is the space complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings? a) O(1) Answer: c 11. What is the output of the following code? a) 1 12. What is the value stored in arr[2][2] when the following code is executed? a) 1 Answer: b 13. What is the output of the following code? a) 1 Answer: a
a) True
b) False
Clarification: d(s,s) = 0, since each string can be transformed into itself without any change.
d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
d(s1, s2) = d(s2, s1)
d(s1, s3) <= d(s1, s2) + d(s2, s3)
Thus, the edit distance satisfies the axioms of a metric.
a) Approximate string matching
b) Spelling correction
c) Similarity of DNA
d) Approximate string matching, Spelling Correction and Similarity of DNA
Clarification: All of the mentioned are the applications of the edit distance problem.
a) When one string is a substring of another
b) When the lengths of the two strings are equal
c) When the two strings are equal
d) The edit distance can never be zero
Answer: c
Clarification: The edit distance will be zero only when the two strings are equal.
a) True
b) False
View Answer
Clarification: Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.
a) 3
b) 4
c) 5
d) 6
Clarification: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.
a) 0
b) 4
c) 2
d) 3
Clarification: The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.#include
a) arr[i-1][j] = min
b) arr[i][j-1] = min
c) arr[i-1][j-1] = min
d) arr[i][j] = min
Clarification: The line arr[i][j] = min completes the above code.#include
b) O(m + n)
c) O(mn)
d) O(n)
Clarification: The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).#include
b) O(m + n)
c) O(mn)
d) O(n)
Clarification: The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).#include
b) 2
c) 3
d) 4
Answer: d
Clarification: The program prints the edit distance between the strings “abcd” and “defg”, which is 4.#include
b) 2
c) 3
d) 4
Clarification: The value stored in arr[2][2] when the above code is executed is 2.#include
b) 2
c) 3
d) 4
View Answer
Clarification: The code prints the edit distance between the two strings, which is 1.