Data Structure Questions and Answers-Edit Distance Problem
Click on any option to know the CORRECT ANSWERS
Which of the following methods can be used to solve the edit distance problem?
Both dynamic programming and recursion
None of the mentioned
Question 1 Explanation:
Both dynamic programming and recursion can be used to solve the edit distance problem.
The edit distance satisfies the axioms of a metric when the costs are non-negative.
Question 2 Explanation:
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.
Which of the following is an application of the edit distance problem?
Approximate string matching
Similarity of DNA
All of the mentioned
Question 3 Explanation:
All of the mentioned are the applications of the edit distance problem.
In which of the following cases will the edit distance between two strings be zero?
When one string is a substring of another
When the lengths of the two strings are equal
When the two strings are equal
The edit distance can never be zero
Question 4 Explanation:
The edit distance will be zero only when the two strings are equal.
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.
Question 5 Explanation:
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.
There are 5 questions to complete.