The Levenshtein distance is a metric for measuring the difference between two strings. In$-$

bformally, the Levenshtein distance between two strings is the minimum number of single$-$

character edits $($insertions$,$ deletions, or substitutions$)$ required to change one string into the

other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered

this distance in $1965.$

The Levenshtein distance between two strings a and b $($of length $|$a$|$ and $|$b$|,$ respectively$)$ is

given by lev$($a$,$ b$)$ as follows:

lev$($a$,$ b$)=$

$$

$$

$$

$|$a$|$ if $|$b$|=0,$

$|$b$|$ if $|$a$|=0,$

lev$($tail$($a$),$ tail$($b$))$ if head$($a$)=$ head$($b$),$

$1+$ min

$$

$$

$$

lev$($tail$($a$),$ b$)$

lev$($a$,$ tail$($b$))$

lev$($tail$($a$),$ tail$($b$))$

otherwise

where the tail$($x$)$ of some string x is all but the first character of x$,$ and head$($x$)$ is the first

character of x$.$

In a design document, outline the design and implementation strategy for a recursive assem$-$

bly procedure called lev $($and any additional helper functions as needed$)$ that computes the

Levenshtein distance between two null$-$terminated character strings as described above.

Write, and test using QEMU, the RISC$-$V assembly procedure lev. Also, write a main

program to test your procedure. The program should prompt the user to input two strings $($you can assume that the strings will be at most $40$ characters each, not including the zero byte delimiter$),$ call the function, display the result of the function, and finally terminate. Your code must use the $$standard$$ conventions covered in class for passing parameters, returning results, and using the stack.