Let G be a graph whose vertices are the points of an(m+1)×(n+1) grid, i.e., vert

Question

Let G be a graph whose vertices are the points of an(m+1)×(n+1) grid, i.e., vertex (i, j)
corresponds to the point in the grid at row i and column j,0 <= i <= m and 0 <= j <= n.
A vertex (i, j) with 0 <= i <= m and 0 <=j <= n has the following edges coming into it in G:

(i) If i > 0 then there is a vertical edge of costD(ai) coming from the vertex (i 1, j);
(ii) if j > 0 then there is a horizontal edge of costI(bj) coming from the vertex (i, j 1);
(iii) If i > 0 and j > 0 then there is a diagonal edge comingfrom the vertex (i 1, j 1).

1) What is the graph-theoretic interpretation of the quantity C(i,j) in terms of paths in the graph G ?

2) What is the graph-theoretic interpretation of the quantity H(i,j) in terms of paths in the graph G ?

----------------Background andNotation------------------------------------------- Recall that this is the problem of finding a minimumcostsequence of operations on a given
string A = a1a2 . . . am thattransforms it into another given string B =b1b2 . . . bn.
The symbols in A and B are from an alphabet of constant size
(e.g., for lowercase English, the alphabet size is 26). The allowedtypes of operations are

(i) inserting a symbol x into A, whose cost is denoted by I(x);
(ii) deleting a symbol x from A, whose cost is denoted byD(x);
(iii) substituting in A a symbol y for a symbol x, whose cost isdenoted by S(x, y).

The I, D and S cost tables are given as part of the input, alongwith the two input strings A and B. The O(mn) time algorithmrelies on computing the entries of an (m+1) × (n + 1) table Cin which C(i, j), for 1<= i <=m and 1<=j<=n, is theminimum cost of transforming a1 . . . ai intob1 . . . bj .
C(0, j) is the minimum cost of transforming the empty string intob1 . . . bj , and C(i, 0) is the minimum
cost of transforming a1 . . . ai into theempty string. The crucial observations that made the O(mn) time
algorithm possible were the following equations. Equations forC

1. C(0, j) = I(b1) + I(b2) + ·· · + I(bj)
2. C(i, 0) = D(a1) + D(a2) + ·· · + D(ai)
3. C(i, j) = min{C(i, j 1) + I(bj),C(i 1, j) + D(ai),C(i 1, j 1) +S(ai, bj)}
computing C(m, n) can be done in O(mn) time and O(m+n) space. Wealso explained how,
if we use O(mn) space, we can compute in O(mn) time not only C(m,n) but also
the optimal sequence of operations that achieves that C(m, n)cost.
The purpose of this homework is to explore an O(m+n) spacealgorithm for finding the
optimal sequence of operations in O(mn) time Let G be a graph whose vertices are the points of an(m+1)×(n+1) grid, i.e., vertex (i, j)
corresponds to the point in the grid at row i and column j,0 <= i <= m and 0 <= j <= n.
A vertex (i, j) with 0 <= i <= m and 0 <=j <= n has the following edges coming into it in G:

(i) If i > 0 then there is a vertical edge of costD(ai) coming from the vertex (i 1, j);
(ii) if j > 0 then there is a horizontal edge of costI(bj) coming from the vertex (i, j 1);
(iii) If i > 0 and j > 0 then there is a diagonal edge comingfrom the vertex (i 1, j 1).

1) What is the graph-theoretic interpretation of the quantity C(i,j) in terms of paths in the graph G ?

2) What is the graph-theoretic interpretation of the quantity H(i,j) in terms of paths in the graph G ?

----------------Background andNotation------------------------------------------- Recall that this is the problem of finding a minimumcostsequence of operations on a given
string A = a1a2 . . . am thattransforms it into another given string B =b1b2 . . . bn.
The symbols in A and B are from an alphabet of constant size
(e.g., for lowercase English, the alphabet size is 26). The allowedtypes of operations are

(i) inserting a symbol x into A, whose cost is denoted by I(x);
(ii) deleting a symbol x from A, whose cost is denoted byD(x);
(iii) substituting in A a symbol y for a symbol x, whose cost isdenoted by S(x, y).

The I, D and S cost tables are given as part of the input, alongwith the two input strings A and B. The O(mn) time algorithmrelies on computing the entries of an (m+1) × (n + 1) table Cin which C(i, j), for 1<= i <=m and 1<=j<=n, is theminimum cost of transforming a1 . . . ai intob1 . . . bj .
C(0, j) is the minimum cost of transforming the empty string intob1 . . . bj , and C(i, 0) is the minimum
cost of transforming a1 . . . ai into theempty string. The crucial observations that made the O(mn) time
algorithm possible were the following equations. Equations forC

1. C(0, j) = I(b1) + I(b2) + ·· · + I(bj)
2. C(i, 0) = D(a1) + D(a2) + ·· · + D(ai)
3. C(i, j) = min{C(i, j 1) + I(bj),C(i 1, j) + D(ai),C(i 1, j 1) +S(ai, bj)}
computing C(m, n) can be done in O(mn) time and O(m+n) space. Wealso explained how,
if we use O(mn) space, we can compute in O(mn) time not only C(m,n) but also
the optimal sequence of operations that achieves that C(m, n)cost.
The purpose of this homework is to explore an O(m+n) spacealgorithm for finding the
optimal sequence of operations in O(mn) time

Explanation / Answer

Dear User,          1. Thegraph-theoretic interpretation of the quantity C(i, j) is thelength of the shortest path from the vertex(0,0) to                 vertex(i,j).          2. Thegraph-theoretic interpretation of the quantity H(i, j) is thelength of the shortest path from the vertex(i,j)  to              vertex(m,n).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.