8 practice sets · Page 1 of 1
Which of the following lines should be added to complete the above code?
arr[i-1][j] = min
arr[i][j-1] = min
arr[i-1][j-1] = min
arr[i][j] = min
Correct Answer: D — arr[i][j] = min
Explanation:
The line arr[i][j] = min completes the above code.
Consider the two strings ""(empty string) and "abcd". What is the edit distance between the two strings?
0
4
2
3
Correct Answer: B — 4
Explanation:
The empty string can be transformed into "abcd" by inserting "a", "b", "c" and "d" at appropriate positions. Thus, the edit distance is 4.
Consider the strings "monday" and "tuesday". What is the edit distance between the two strings?
3
4
5
6
Correct Answer: B — 4
Explanation:
"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.
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.
True
False
Correct Answer: A — True
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.
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
Correct Answer: C — When the two strings are equal
Explanation:
The edit distance will be zero only when the two strings are equal.
Which of the following is an application of the edit distance problem?
Approximate string matching
Spelling correction
Similarity of DNA
Approximate string matching, Spelling Correction and Similarity of DNA
Correct Answer: D — Approximate string matching, Spelling Correction and Similarity of DNA
Explanation:
All of the mentioned are the applications of the edit distance problem.
The edit distance satisfies the axioms of a metric when the costs are non-negative.
True
False
Correct Answer: A — True
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 methods can be used to solve the edit distance problem?
Recursion
Dynamic programming
Both dynamic programming and recursion
Greedy Algorithm
Correct Answer: C — Both dynamic programming and recursion
Explanation:
Both dynamic programming and recursion can be used to solve the edit distance problem.
