Using the edit distance algorithm given on page $114$ in the textbook, draw and fill out the Edit table

used in it for the strings DARING and DISCARD.

Exercise Corner to Corner Path $($Th$,////...$

You are given an $nn$ table $p$ with natural numbers in each entry representing a profit. As with the

chessboard traversal problem discussed in class, the goal is to find a maximum profit path, subject to

these conditions:

The path must start in the upper left corner $($that is$,$ the square at position $1,1)$ and end at the

lower right corner $($position $n,n).$

A move from a square to the next on a path must go either to the right or down.

A path's profit is the total of the profits for the squares followed by the path.

Answer each of the following:

Define a function $q$ as a recurrence relation where $q(i,j)$ is the maximum profit attainable for

every path that ends at entry $i,j.$

As we've seen, one computes values for $q$ by using an $nn$ table called $q.$ For an

entry $q[i,j]$ in that table, specify which entries you need filled in before you can fill in $q[i,j].$

Specify an order for how to fill in the entries in $q$ given the previous answer.

Given the following values for the $p$ table, fill out the $q$ table. Write down the maximum

achievable path profit. Programs

Implement EDITDISTANCE $\frac{L}{l}/////////$

Implement in either Java $($version $12$ or later$)$ or Python $($version $3\mathrm{.}11$ or later$)$ the pseudocode for the

EDITDISTANCE method given on page $114$ of the textbook.

Your program must meet these requirements:

The file must be named either EditDistance.java or

editdistance.py$.$

Your name must appear in a comment at the top of program.

The program must contain a method called editDistance.

It must also contain a main section. For Java, that would be the main method. For Python, that

would be code at the bottom of the program at column $1.$

The program must take as command line parameters two strings, which are the strings for which

the edit distance is to be computed.

$,$ The program will print a line with your name, the two strings, and the edit distance table.

$,$ For Java programs, do NOT put in a package directive.

For Java programs, your code must be written so that I can compile it and run it using the

command line commands:

javac EditDistance.java

java EditDistance string$1$ string$2$

For Python programs, your code must be written so that I can run it using the command line

command: python

editdistance.py string$1$ string$2$

Here are some other important points and reminders:

To get any credit, the program must run without crashing. Points will be deducted for not

following all of the requirements listed above.

Please refer the images.