A palindrome is a sequence that is the same as its reverse. For example, the word

"RACECAR" is a palindrome.

For this problem we will define an almost palindrome to be a sequence that can be

transformed into its reverse with $2$ or fewer character additions, deletions, replacements,

or swaps. A character swap swaps two adjacent characters.

For instance "MARJORAM" can be reversed by swapping the $\text{'}$J$\text{'}$ and the $\text{'}$O$\text{'}.$ In addition,

"FOOLPROOF" can be reversed by replacing the $\text{'}$R$\text{'}$ with and $\text{'}L\text{'}$ and vice versa. Finally,

the word "BONOBO" can be reversed by deleting the final $\text{'}$O$\text{'}$ and reinserting it at the

beginning.

Devise a dynamic programming algorithm that will determine the number of edits

necessary to to transform a sequence into its reverse.

a$)$ State this problem with formal input and output conditions.

b$)$ State a self$-$reduction for this problem.

c$)$ State a dynamic programming algorithm based off of your self$-$reduction that

computes the minimum number of edits to transform a sequence into its reverse.

d$)$ Use your algorithm to determine the minimum number of edits to transform

"MARJORAM", "FOOLPROOF" and "BONOBO" into their reverses. Show your

work.