There are a number of other notions of edit distance available. For instance, we can allow, in addition to insertions and deletions, the following operations:
i. Mutation, where one symbol is replaced by another symbol. Note that a mutation can always be performed by an insertion followed by a deletion, but if we allow mutations, then this change counts for only 1, not 2, when computing the edit distance.
ii. Transposition, where two adjacent symbols have their positions swapped. Like a mutation, we can simulate a transposition by one insertion followed by one deletion, but here we count only 1 for these two steps.
Repeat Exercise 3.5.7 if edit distance is defined to be the number of insertions, deletions, mutations, and transpositions needed to transform one string into another.
Exercise 3.5.7
Find the edit distances (using only insertions and deletions) between the following pairs of strings.
