Question

Time and space complexity of dynamic programming. Our dynamic programming algorithm for computing the edit distance between strings of length m and n creates a table of size $\mathit{n}\mathbf{\times }\mathit{m}$and therefore needs O (mn) time and space. In practice, it will run out of space long before it runs out of time. How can this space requirement be reduced?

1. Show that if we just want to compute the value of the edit distance (rather than the optimal sequence of edits), then only O(n) space is needed, because only a small portion of the table needs to be maintained at any given time.
2. Now suppose that we also want the optimal sequence of edits. As we saw earlier, this problem can be recast in terms of a corresponding grid-shaped dag, in which the goal is to find the optimal path from node (0,0) to node (n,m). It will be convenient to work with this formulation, and while we’re talking about convenience, we might as well also assume that is a power of 2.
   Let’s start with a small addition to the edit distance algorithm that will turn out to be very useful. The optimal path in the dag must pass through an intermediate node $\left(k,\frac{m}{2}\right)$ for some k; show how the algorithm can be modified to also return this value k.
3. Now consider a recursive scheme:
   Procedure find-path$\left((0,0)\to (n,m)\right)$
   Compute the value kabove
   find-path $\left((0,0)\to \left(k,\frac{m}{2}\right)\right)$
   find-path $\left(\left(k,\frac{m}{2}\right)\to \left(n,m\right)\right)$
   concatenate these two paths, with kin the middle.
   Show that this scheme can be made to run inO (mn) time and O(n) space.

Short answer

This space can be reduced by calculating the values of the adjacent cells in the table and the space complexity will be reduced to O(n).

1. By considering the value of the adjacent square, the edit distance value can be computed in the given space complexity.
2. Yes, the algorithm can be modified as follows,
   $$\begin{gathered} K(i,0)=i \\ ifj>\frac{n}{2} \\ ifE(i,j)=E(i-1,j)+1 \\ k\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}\right) \\ elseifE(i,j)=E(i,j-1)+1 \\ K\left(i,j-\frac{n}{2}\right)=K\left(i,j-\frac{n}{2}-1\right) \\ ElseifE(i,j)=E(i-1,j-1)+diff(i,j) \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}-1\right) \end{gathered}$$
   this scheme can be made to run in O(mn) time and O(n) space.
3. The given scheme can be made to run in O(mn) time and O(n) space because of the size and the difficulty of the algorithm.

Step-by-step solution

Explain space complexity and how the space requirement can be reduced.

Space Complexity for any algorithm defines the total space that is required or used by that algorithm, for different sizes of the input.

To create any variable there required some space for the algorithm to run. All the space that is required by the algorithm is collectively known as the Space Complexity of the algorithm.

In the dynamic programming algorithm for computing the edit distance between strings of length m and n creates a table of size and therefore needs O(mn) time and space. In practice, it will run out of space long before it runs out of time. This space can be reduced by calculating the values of the adjacent cells in the table and the space complexity will be reduced to O(n).

Show that the value of the edit distance can be computed.

(a)

Consider the Figure 6.4 in the text book, the calculation of a certain cell only needs the values of the upper left, upper and left cells of the cell. Considering the values of the adjacent cells in three directions, the current row and the previous row will be saved.

The state values are enough and they can be stored in a rolling array and the space complexity is O(n).

Therefore, By considering the value of the adjacent square, the edit distance value can be computed in the given space complexity.

Show how the algorithm can be modified to also return this value k.

(b)

Consider the edit-distance algorithm to calculate the path from the node (0,0) to node (n,m). The optimal path in the dag must pass through an intermediate node $\left(k,\frac{m}{2}\right)$ for some k. In the algorithm swap n and m, which means represents rows and n represents listed rows. The rolling array K with $\frac{n}{2}+1$ columns to store the values of k.

The modified edit-distance algorithm is as follows.

$$\begin{gathered} K(i,0)=i \\ ifj>\frac{n}{2} \\ ifE(i,j)=E\left(i-1,j\right)+1 \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}\right) \\ elseifE(i,j)=E(i,j-1)+1 \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}-1\right) \\ ElseifE(i,j)=E(i-1,j-1)+diff(i,j) \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}-1\right) \end{gathered}$$

Show that the given scheme can be made to run in O(mn) time and O(n) space.

(c)

Consider that the given scheme is the recurrence relation, the time complexity is as follows,

$\begin{array}{rcl}T(m,n)& =& O\left(mn\right)+\frac{1}{2}O\left(mn\right)+\frac{1}{4}O\left(mn\right)+\frac{1}{8}O\left(mn\right)...\\ & =& O\left(mn\right)\end{array}$

The time complexity is still O(mn), the constant is due to that the size of the algorithm is doubles and the difficulty of the algorithm implementation has also been greatly improved.

Therefore, it has been shown that the given scheme can be made to run in O(mn) time and O(n) space.