ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
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
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
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
"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
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
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
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
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
Both dynamic programming and recursion can be used to solve the edit distance problem.
