Problem $1$

Problem $1.$ Consider a modified version of the string alignment $($aka edit distance$)$ problem that we saw in

class. The allowed operations are: insert, delete, substitute, and swap. Note that the swap operation is new

compared to what we covered in class. $($Also$,$ a no$-$op$,$ which is free, as in class.$)$

The swap operation replaces any two adjacent letters by swapping them. For example, performing a swap

on there could result in htere $($by swapping the first two letters$),$ tehre $($by swapping the second two letters$),$

three $($by swapping the er in the middle$),$ or theer $($by swapping the last two letters.

Given two strings x and y$,$ let

T$[$i$,$ j$]=$ minimum number of operations to transform the prefix x$[1..$i$]$ into the prefix y$[1..$j$].$

Your job is to write down a recurrence for this dynamic programming table. Make sure to include your base

cases and justify your recurrence.

As a starting point, we have included the recurrence from class for the simpler version of string alignment we

did in class; if you choose to start from this recurrence, you will have to edit it appropriately.