CS5800-Homework 5 Solved

1             Exercise 15.2-1
We define the cost of an optimal solution recursively in terms of the optimal solutions to subproblems. For the matrix-chain multiplication problem, we pick as our subproblems the problems of determining the minimum cost of parenthesizing AiAi+1...Aj for 1 ≤ i ≤ j ≤ n. Let m[i,j] be the minimum number of scalar multiplications needed to compute the matrix Ai..j. Our definition for the minimum cost of parenthesizing the product AiAi+1...Aj becomes

                                                          (0,                                                                      if i = j

m[i,j] =

                                                                    min {m[i,k] + m[k + 1,j] + pi−1pkpj},          if i < j

i≤k<j

The m[i,j] values give the costs of optimal solutions to subproblems, but they do not provide all the information we need to construct an optimal solution. To help us do so, we define s[i,j] to be a value of k at which we split the product AiAi+1...Aj in an optimal parenthesization. That is, s[i,j] equals a value k such that m[i,j] = m[i,k] + m[k + 1,j] + pi−1pkpj.

Instead of computing the optimal cost recursively, we compute it by using a tabular, bottom-up approach. We shall implement the tabular, bottom-up method in the procedure MATRIX-CHAIN-ORDER, which appears below. This procedure assumes that matrix Ai has dimensions pi−1 × pi for i = 1,2,...,n. Its input is a sequence p =< p0,p1,,,,,pn > where p.length = n + 1. The procedure uses an auxiliary table m[1..n,1..n] for storing the m[i,j] costs and another auxiliary table s[1..n − 1,2..n] that records which index of k achieved the optimal cost in computing m[i,j].

We shall use the table s to construct an optimal solution. In order to implement the bottom-up approach, we must determine which entries of the table we refer to when computing m[i,j]. Thus, the algorithm should fill in the table m in a manner that corresponds to solving the parenthesization problem on matrix chains of increasing length. .

 

Pseudocode 1 Find optimal parenthesization of a matrix-chain product

1: function Matrix-chain-order(p)

2:               n ← p.length − 1
 
3:
let m[1..n,1..n] and s[1..n − 1,2..n] be new tables
 
4:
for i = 1 to n do
 
5:
m[i,i] ← 0
 
6:
end for
 
7:
for l = 2 to n do
▷ l is the chain length
8:
for i = 1 to n − l + 1 do
 
9:
j ← i + l − 1
 
10:
m[i,j] ←∞
 
11:
for k = i to j − 1 do
 
12:
q = m[i,k] + m[k + 1,i] + pi−1pkpj
 
13:
if q < m[i,j] then
 
14:
m[i,j] ← q
 
15:
s[i,j] ← k
 
16:
end if
 
17:
end for
 
18:
end for
 
19:
end for
 
20:            return m and n

21: end function

22:

23: function Print-optimal-parens(s,i,j)

24:              if i == j then

25:                   print ”A”

26:          else

27:                   print ”(”

28:                            Print-optimal-parens(s,i,s[i,j])

29:                            Print-optimal-parens(s,s[i,j] + 1,j)

30:                   print ”)”

31:           end if

32: end function
 
For sequence of {5,10,3,12,5,50,6}, let p0 = 5,p1 = 10,p2 = 3,p4 = 5,p5 = 50,p6 = 6.

The corresponding matrix: A1 = 5 × 10,A2 = 10 × 3,A3 = 3 × 12,A4 = 12 × 5,A5 = 5 × 50,A6 = 50 × 6. According to the previous algorithm, for all m[i,j] = 0, we have:

m[1,2] = m[1,1] + m[2,2] + p0p1p2 = 0 + 5 × 10 × 3 = 150

...

The m-table and s-table are shown as follows:           .

                                     6      0

                                                                                                                                                                   5   5

                                     5   1500      0

                                                                                                                                                                   4   4   4

                                     4   1860  3000     0

                                                                                                                                                                   3   4   4   3

        m-table     = 3    1770   930    180     0                                 s-table    =

                                                                                                                                                                   2   2   2   2   2

                                     2   1950  2430   330  360     0

                                                                                                                                                                   1   2   4   2   2   1

                                     1   2010  1655   405  330   150   0

                                                                                                                                                                    i    6   5   4   3   2    j

                                      i       6         5        4       3       2     1   j

According to the s − table, the optimal parenthesization is (A1A2)((A3A4)(A5A6))

2             Exercise 15.3-2
1..16

 

1..1          2..23..3         4..45..5         6..67..7         8..8 9..9      10..1011..11   12..1213..13   14..1415..15 16..16

An optimal problem must have for dynamic programming to apply is that the space of subproblems must be ”small” in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems. Typically, the total number of distinct subproblems is a polynomial in the input size. When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion. Dynamic programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table when it can be looked up when needed, using constant time per lookup. The MERGE-SORT procedure does not have overlapping subproblems, that is, all nodes of the recursion tree are distinct. Since we cannot reuse the results of recursive, the dynamic programming cannot improve the efficiency.

3             Exercise 15.3-5
The optimal substructure of section 15.1 whose recursion is shown below:

rn = max(pi + rn−i)

1≤i≤n

Now, we are going to apply this recursion directly to this problem. Cut a rod of length n, assuming that the first cut is length i. When solving the subproblem, that is, when cutting rod of length n − i, it is assumed that the number of short rod of length i cut is exactly the maximum li. Hence, in the cutting scheme of the whole rod, there are li +1 short rods of length i, which exceeds the maximum limit of li. Therefore, applying this recursion directly may result in a solution that does not meet the constraints.

In other words, when solving the subproblem, that is, when cutting rod of length n − i, the number of short rods of length i cut cannot exceeds li − 1 (minus 1 is because a short rod with length i has been cut before solving the subproblem). Therefore, the subproblem is not only smaller than the original problem, but the constraints are also changed. It leads to a problem that even if a subproblem of the same size is solved, different results will be produced due to different constraints, that is, a subproblem of the same size may need to be solved multiple times due to the change of constraints. This does not conform to the principle of optimal substructure ”the same subproblem only needs to be solved once”.

4             Problem 15-5
4.1           a)
Assume that the optimal cost for transferring x[1..i] where 0 ≤ i ≤ m to y[1..j] where 0 ≤ j ≤ n, and x[1..0],y[1..0] is null.

case 1: if i > 0 and j > 0

Thinking of the last operation from x[1..i] transfer to y[1..j], there has six possible options. Note that some operations can only be performed if conditions are met.

1.     Copy

Conditions: x[i] = y[i]

Costs: d1[i,j] = cost(copy) + c[i − 1,j − 1]

2.     Replace

It is necessary to assume that the cost of replace is greater than the cost of copy. Otherwise, we could use replace instead of copy so that copy will never be user at all.

Conditions: x[i] ̸= y[i]

Costs: d2[i,j] = cost(replace) + c[i − 1,j − 1]

3.     Delete

Conditions: None

Costs: d3[i,j] = cost(delete) + c[i − 1,j]

4.     Insert

Conditions: None

Costs: d4[i,j] = cost(insert) + c[i,j − 1]

5.     Twiddle

Conditions: i ≤ 2,j ≤ 2,x[i − 1] = y[j],x[i] = y[j − 1]

Costs: d5[i,j] = cost(twiddle) + c[i − 2,j − 21]

6.     Kill

Kill can only be the last operation, so there must have i = m and j = n and the transformation-operation before kill is x[1..k] to y[1..n] where 0 ≤ k ≤ m. Note that if the kill operation is executed, the number of characters processed by the x needs to be record.

Conditions: i = m,j = n

Costs: d6[i,j] = min {cost(kill) + c[k,n]}

0≤k≤m

The processing costs of the above six operations are calculated respectively, and the one with the minimum is selected as the optimal cost:

                                                                              c[i,j] =       min {dk[i,j]}

1≤k≤m6

Case 2: if i = 0 or j = 0

1.     i = 0, that is, x[1..0] to y[1..j]

Since x[1..0] is empty, we only can make j insert operation to get y[1..j]

c[0,j] = j ∗ cost(insert)

2.     j = 0, that is, x[1..i] to y[1..0]

Since y[1..0] is empty, if i < m or n > 0, we only can make i delete operation; if i = m and n = 0, then the kill operation can be performed in one step or delete operation can be performed in m steps, take the one with lowest cost.

 0

c

= 0

Algorithm 2 Dynamic programming algorithm that finds the edit distance

 

Input: Sequence X, sequence Y, m(the length of X), n(the length of Y), the cost of each operation

Output: The array of optimal cost C, the array of the last opeartion op, the number of processed character p

1: function Edit-distance(X,Y,m,n,cost)
2:                create 2 new 2-D arrays C[0..m,0..n] and op[0..m,0..n]

3:             create a new 1-D array d[1..6]

4:              C[0,0] ← 0

5:             op[0,0] ← 0

6:               for j = 1 to n do

7:
C[0,j] ← j ∗ cost[4]
▷ insert
8:
op[0,j] ← 4
 
9:
end for
 
10:
for i = 1 to m do
 
11:
C[i,0] ← j ∗ cost[3]
▷ delete
12:
op[i,0] ← 3
 
13:
end for
 
14:
if n = 0 and cost(kill) < C[m,0] then
 
15:
C[m,0] ← cost[6]
 
16:
op[i,0] ← 6
 
17:
p ← 0
 
18:
end if
 
19:
for i = 1 to m do
 
20:
for j = 1 to n do
 
21:
for k = 1 to 6 do
 
22:
d[k] ←∞
 
23:
end for
 
24:
if X[i] = Y [j] then
 
25:
d[1] = cost[1] + C[i − 1,j − 1]
▷ copy
26:
else
 
27:
d[2] = cost[2] + C[i − 1,j − 1]
▷ replace
28:
end if
 
29:
d[3] = cost[3] + C[i − 1,j]
▷ delete
30:
d[4] = cost[4] + C[i,j − 1]
▷ insert
31:
if i ≥ 2 and j ≥ 2 and X[i − 1] = Y [j] and X[i] = Y [j − 1] then
 
32:
d[5] = cost[5] + C[i − 2,j − 2]
▷ twiddle
33:
end if
 
34:
if i = m and j = n then
 
35:
for k = 0 to m − 1 do
 
36:
if cost[6] + C[k,n] < d[6] then
 
37:
d[6] = cost[6] + C[k,n]
▷ kill
38:                                                  p = k

39:                                          end if

40:                                   end for

41:                           end if

42:                             C[i,j] ←∞

43:                            for k = 1 to 6 do

44:                                     if d[k] < C[i,j] then

45:                                            C[i,j] ← d[k]

46:                                           op[i,j] ← k

47:                                  end if

48:                           end for

49:                   end for

50:           end for

51:              return C,OP and p

52: end function

 

Pseudocode 3 Print the operation

 

Input: The array op, the number of processed character p, i(the length of X), j(the length of Y)

1: function Print-operation(op,p,i,j)
2:               If op[i,j] = 0 return

3:               Else if op[i,j] = 1

4:                                Print-operation(op,p,i − 1,j − 1)
5:                       print copy     i → j

6:               Else if op[i,j] = 2

7:                                Print-operation(op,p,i − 1,j − 1)
8:                        print replace     i → j

9:               Else if op[i,j] = 3

10:                             Print-operation(op,p,i − 1,j)
11:                     print delete    i

12:             Else if op[i,j] = 4

13:                             Print-operation(op,p,i,j − 1)
14:                      print insert     j

15:             Else if op[i,j] = 5

16:                              Print-operation(op,p,i − 2,j − 2)
17:                     print twiddle       i − 1 → j,i → j − 1

18:           Else

19:                             Print-operation(op,p,p,j)
20:                      print kill    p

21: end function

 

The running time of the algorithm is O(mn).

4.2           b)
The DNA alignment problem can be transfermed into an edit distance problem by the following method:

If x′[i] = y′[j] and neither is a space, it is same as copy operation, the score(copy) =

+1

If x′[i] ̸= y′[j] and neither is a space, it is same as replace operation, the score(replace) = −1

If x′[i] = space, it is same as insert operation, the score(insert) = −2

If y′[i] = space, it is same as delete operation, the score(delete) = −2

The twiddle and kill operations cannot be used. The pseudocode is mostly same. Besides, the edit distance problem is to minimize the cost, while the problem of two DNA sequences is to maximize the score.

5             Cross-country road-trip problem
Since the problem is similar with chess board problem, we use the Dynamic programming. Table of costs given as a matrix pij;i = 1 : n,j = 1 : n

C[i,j] = minimum cost from row 1 to cell [i,j] and C[i,j] = pij if i = 1                       .

 

1: C[1,j] = P1j for all j

2: for i = 2 to n do

3:               for j = 1 to n do

4:                                C[i,j] ← pij + min(C[i − 1,j − 1],C[i − 1,j],C[i − 1,j + 1])

5:                       y ← xi + 1

6:             end for

7: end for

8: return C

 

After the array C computed, we will trace the solution. Find the minimum column j = argmin(C[m,:]) on the last row, output the cell C[n,j] .

 

1: i ← n

2: while i > 1 do

3:                      jbelow ← argmin(C[i − 1,j − 1],C[i − 1,j],C[i − 1,j + 1])

4:               output cell C[i − 1,jbelow]

5:              i ← i − 1

6:              j ← jbelow

7: end while

 

Since the outer loop has n iterations, inner loop has n iterations, and we also have 3 comparisons that is constant time, our algorithm total running time is

Θ(n2).

6             Exercise 15.4-5
Assume that the sequence of n numbers is X = {x0,x1,...,xn}, makes a copy of X called Y and sorted T by increasing order Y = {y0,y1,...,yn}. It stores the c[i,j] values in a table c[0..n,0..n] and it computes the entries in row-major order(That is, the procedure fills in the first row of c from left to right, then the second row, and so on). The procedure also maintains the table b[1..n,1..n] to help us construct an optimal solution. Intuitively, b[i,j] points to the optimal subproblem solution chosen when computing c[i,j]. The procedure returns the b and c tables; c[n,n] contains the length of an longest monotonically increasing subsequence of X.

As in the matrix-chain multiplication problem, our recursive solution to the LIS problem involves establishing a recurrence for the value of an optimal solution. If either i = 0 or j = 0, one of the sequence has length 0, and so the LIS has length

0. The optimal substructure of the LIS problem gives the recursive formula



0, 

c[i,j] =         c[i − 1,j − 1] + 1,

max(c[i,j − 1],c[i − 1,j]),
if i = 0 or j = 0 if i,j > 0 and xi = yj if i,j > 0 and xi ̸= yj
.

 

Algorithm 4 Find the longest monotonically increasing subsequence

 

1: function LIS-length(X,Y )
2:               let b[1..n,1..n] and c[0..n,0..n] be new tables

3:               for i = 1 to n do

4:                     c[i,0] ← 0

5:             end for

6:               for j = 0 to n do

7:                      c[0,j] ← 0

8:             end for

9:               for i = 1 to n do

10: for j = 1 to n do 11: if xi == yi then

12:                                      c[i,j] ← c[i − 1,j − 1] + 1

13:                                    b[i,j] =↖

14:                          else

15:                                      if c[i − 1,j] ≥ c[i,j − 1] then

16:                                             c[i,j] ← c[i − 1,j]

17:                                           b[i,j] =↑

18:                                  else

19:                                             c[i,j] ← c[i,j − 1]

20:                                            b[i,j] =←

21:                                  end if

22:                           end if

23:                   end for

24:           end for

25:            return c and b

26: end function

 

The b table returned by LIS-Length enables us to quickly construct an LIS of X = {x0,x1,...,xn} and Y = {y0,y1,...,yn}. We simply begin at v[n,n] and trace through the tbale by following the arrows. Whenever we encounter a ”↖” in entry b[i,j], it implies that xi = yj is an element of the LIS that Lis-Length found. With this method, we encounter the elements of this LIS in the proper, forward order. The initial call is PRINT − LIS(b,X,i,j). .

 

Algorithm 5 Print the longest monotonically increasing subsequence

1: function Print-LIS(b,X,i,j)

2:                  if i == 0 or j == 0 then return
3:
end if
4:
if b[i,j] == ” ↖ ” then
5:
Print-LIS(b,X,i − 1,j − 1)
6:
print xi
7:
else
8:
if b[i,j] == ” ↑ ” then
9:
Print-LIS(b,X,i − 1,j)
10:
else
11:
Print-LIS(b,X,i,j − 1)
12:
end if
13:           end if

14: end function
The LIS-Length is based on an exponential-time recursive algorithm to compute the length of an LIS of sequences, so the LIS-Length takes Θ(n2) time, since each table entry takes Θ(1) time to compute.

The procedure of PRINT-LIS takes time O(n + n) = O(2n), since it decrements at least one of i and j in each recursive call.

Therefore, the running time of LIS problem is Θ(n2).