[Solved] The edit distance satisfies the axioms of a metric when the costs are non-negative.

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
The edit distance satisfies the axioms o...

Q.	The edit distance satisfies the axioms of a metric when the costs are non-negative.
A.	true
B.	false
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.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

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.
Which of the following methods can be used to solve the edit distance problem?
Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
Manhattan distance is an alternative way to define a distance between two points.
The shortest distance between a line and a point is achieved when?
What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)?
What is the distance between the lines 3x- 4y+7=0 and 3x-4y+5=0?
Which of the following is similar to Euclidean distance?