3. (From Problem 8-1 in the Textbook.) The simple edit distance algorithm assign

Question

3. (From Problem 8-1 in the Textbook.) The simple edit distance algorithm assigns a cost of I to an insertion and to a deletion. But another type of edit is to transpose (or swap) two items that are next to each other in the original sequence. A transposition has a cost of 2 in the original sense for a transposition to have a cost of 1. Expiain how to modify the simple edit distance algorithm to make the cost algorithm, a deletion followed by an insertion. However, it can make of a transposition equal to 1 instead of 2 Continued on reverse!)

Explanation / Answer

Solution:

Note: The exact algorithm is not shared here so I am explaining in general terms, about how to make it happen.

In the transponsition operation previously it was taking two operations with the cost of 2, which is one inerstion and one deletion.

But what we can do is to make the transposition happen is

we can copy a value in a variable named temp, and then insert it on the other one (the second place) and then the other value (from second to the first) will be inserted on the other (in the first place.).

so only insertion operation will happen, which will decrease the cost of transposition to 2.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.