CS5800-Homework 6 Solved

1             Jars on a ladder problem
1.1
We could consider this problem by using dynamic programming. When the first jar is drooped in ith rung, if the jar break then we don’t need to consider [i+1,n]th rung and we only have k−1 jars now. We shall user MinT(i−1,k−1)+1 to express the minimum number of dropping trials has to make from 1 to n − 1 rung; Otherwise, if the jar not break in ith rung, then we don’t consider [1,i]th rung any more, and we still have k jars left. Thus. the minimum number of dropping trails has to make is MinT(n − i,k) + 1 where 1 ≤ i ≤ n. Therefore, in different cases the minimum number of dropping trails is:



n rungs and k jars left : MinT(n − i,k) + 1

 dropping on the ith rung and jar break : MinT(n.k)

dropping on the ith rung and jar not break : MinT(n − i,k)

Thus, q could be expressed as:

q = MinT(n.k) = min {max[MinT(i − 1,k − 1),MinT(n − i,k)] + 1}

1≤i≤n

and MinT(n,1) = n,MinT(0,k) = 0

1.2
Assume that MaxR(k,q) = the highest ladder size n doable with k jars and maximum q trails. When we drop the jar from rung, if the jar break then we need to use k − 1 jars to get the highest ladder in q − 1 trials: MaxR(k − 1,q − 1). Otherwise, we need to use k jars to get the highest ladder in q − 1 trails:

MaxR(k,q − 1). Therefore, MaxR(1,q) = MaxR(k − 1,q − 1) + MaxR(k,q − 1) + 1.

1.3
 

Pseudocode 1 Bottom-up non-recursive computation

1: function MinT(n,k)

2:                 let f[0..n + 1,0..k + 1] be a new 2D table
3:
Initialize the table f and f[0][0] = 0
4:
for i = 1 to n + 1 do
5:
f[i][1] ← i
6:
end for
7:
for j = 1 to k + 1 do
8:
f[1][j] ← 1
9:
end for
10:
for i = 2 to n + 1 do
11:
for j = 2 to k + 1 do
12:
for m = 1 to i + 1 do
13:
f[i][j] = min(f[i][j],max(f[m − 1][j − 1],f[i − m][j]) + 1
14:
end for
15:
end for
16:
end for
17:           return f[n][k]

18: end function
1.4
 

Algorithm 2 Top-down recursive using memorization

 

1: function MinT(n,k)

2:                 let f[0..n + 1,0..k + 1] be a new 2D table

3:                 return Helper(n,k)

4: end function

5:

6: function Helper(n,k)

7:                 if n == 0 or n == 1 then

8:                     return n

9:             end if

10:             if k == 1 then

11:                   return n

12:           end if

13:              if f[n][k]! = NULL then

14:                   return f[n][k]

15:           end if

16:             res ←∞

17:             for i = 1 to n + 1 do

18:          q = max(Helper(i − 1,k − 1),Helper(n − i,k) + 1) 19:  res = min(res,q)

20:           end for

21:            return f[n][k] = res

22: end function

 

1.5
 

Algorithm 3 Auxiliary structure to determine the optimal sequence of drops

1: function Trace(n,k)

2:                let dp[0..n + 1,0..k + 1] be a new 2D table
3:
Initialize the dp table
4:
i ← 0
5:
while dp[i][k] < n do
6:
i + +
7:
for j = 1 to k + 1 do
8:
dp[i][j] = dp[i − 1][j] + dp[i − 1][j − 1] + 1
9:
end for
10:
end while
11:          return i 12: end function
2             Problem 15.2 Longest palindrome subsequence
Assume that the sequence of n numbers is X = {x0,x1,...,xn}, makes a copy of X and then reverse the copy called Y = {y0,y1,...,yn}. Procedure LPS-Length takes X and Y as inputs. 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.

As in the matrix-chain multiplication problem, our recursive solution to the LPS 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 LPS 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 palindrome subsequence

1: function LPS-length(X,Y )

2:               n ← X.length
3:
let b[1..n,1..n] and c[0..n,0..n] be two new tables
4:
for i = 1 to n do
5:
c[i,0] ← 0
6:
end for
7:
for j = 0 to n do
8:
c[0,j] ← 0
9:
end for
10:
for i = 1 to n do
11:
for j = 1 to n do
12:
if xi == yi then
13:
c[i,j] ← c[i − 1,j − 1] + 1
14:
b[i,j] =↖
15:
else
16:
if c[i − 1,j] ≥ c[i,j − 1] then
17:
c[i,j] ← c[i − 1,j]
18:
b[i,j] =↑
19:
else
20:
c[i,j] ← c[i,j − 1]
21:
b[i,j] =←
22:
end if
23:
end if
24:
end for
25:
end for
26:            return c and b

27: end function
The b table returned by LPS-Length enables us to quickly construct an LPS of X. We simply begin at v[n,n] and trace through the table by following the arrows. Whenever we encounter a ”↖” in entry b[i,j], it implies that xi = yj is an element of the longest palindrome sequence that LPS-Length found. With this method, we encounter the elements of this LPS of X. The initial call is PRINT − LPS(b,X,X.length,X.length).

 

Algorithm 5 Print the longest palindrome subsequence

 

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

2:                  if i == 0 or j == 0 then return

3:             end if

4:                  if b[i,j] == ” ↖ ” then

5:                             Print-LPS(b,X,i − 1,j − 1)

6:                     print xi

7:             else

8:                         if b[i,j] == ” ↑ ” then

9:                                    Print-LPS(b,X,i − 1,j)

10:                  else

11:                                  Print-LPS(b,X,i,j − 1)

12:                   end if

13:           end if

14: end function

 

The running time of the procedure is Θ(n2), since each table entry takes Θ(1) time to compute. The procedure of PRINT-LPS takes time O(n + n) = O(2n), since it decrements at least one of i and j in each recursive call.

Therefore, we can solve the palindrome problem in time O(n2).

3             Exercise 15.4-6
Assume that we have a sequence S and its the longest monotonically increasing subsequence is S′, then the last element of S′ of length n is at least as large as the last element of S′ of length n − 1. Each time we iterate over S, we only need to do the following to find S′:

1.      If x is larger than all elements of S′, that is x can be placed at the end of S′, then append x to the S′ and increase the length of S′ by 1.

2.      If S′[i − 1] < x ≤ s′[i], that is x needs to replace the preceding number greater than x in order to ensure that S′ are an increasing sequence.

 

Algorithm 6 O(nlgn)-time to find the longest monotonically increasing subsequence

1: function LIS(S)

2:               n = S.length
3:
S′[0] ←−1
4:
for i = 0 to n do
5:
if S[i] > S′[−1] then
6:
S′.append(S[i])
7:
else
8:
Use binary search to replace the preceding number greater than x
9:
end if
10:
end for
11:          return S′ 12: end function
Therefore, the total running time is O(nlgn).

4             Problem 15-4 Printing neatly
Since single word cannot be printed separately, we assume that the length of word k does not exceed the number of characters that can be contained in a line, that is lk ≤ M where k = 1,2,...,n. For any line, assuming that it begins with the word i and end with word j, the number of spaces left at the end of the line is

j

e(i,j) = M − j + i −Xlk

k=1

we denote line−cubes(i,j) as the sum of the cubes of the numbers of extra space characters at the end of a line. If e(i,j) < 0, that means a line cannot contain all words through i to j, so it is not appropriate. If e(i,j) ≥ 0 and j = n, that means this line is last, so line − cubes(i,j) = 0 since the last line is not necessary to calculate the sum of cubes. If e(i,j) ≥ 0 and j < n, that means it is not last line, so line − cubes(i,j) = (e(i,j))3. Thus, we obtains:



                                                                                            ∞,                 e(i,j) < 0



                                            line − cubes(i,j) =       0,                    e(i,j) ≥ 0 and j = n

                                                                                       (e(i,j))3,        e(i,j) ≥ 0 and j < n

Assuming that the optimal solution of the sum if cubes of extra space characters at the ends of all lines is cubes(j) from first word to word j. If j < n, then we don’t count the last line. If we assume that word i is the beginning of the last line where 1 ≤ i ≤ j, then the cube is line − cubes(i,j) and other words 1 − i − 1 is cubes(i − 1). Thus, we obtains:

 

 

Algorithm 7 Print a paragraph of n words neatly on a printer

 

1: function Neatly-Print(l,n,M)

2:                let e[1..n,1..n] and line − cubes[1..n,1..n] be two new tables

3:             let cubes[0..n] and p[1..n] be two new arrays

4:               for i = 1 to n do

5:                         e(i,j) = M − li

6:                        for j = i + 1 to n do

7:                                  e(i,j) = e(i,j − 1) − li − 1

8:                     end for

9:             end for

10:             for i = 1 to n do

11:                     for j = 1 to n do

12:                             if e(i,j) < 0 then

13:                                     line − cubes(i,j) = ∞

14:                          else

15:                                     if j = n then

16:                                             line − cubes(i,j) = 0

17:                                  else

18:                                              line − cubes(i,j) = (e(i,j))3

19:                                  end if

20:                           end if

21:                   end for

22:           end for

23:           cubes(0) = 0

24:             for j = 1 to n do

25:                    cubes(j) = ∞

26:                     for i = 1 to j do

27:                                if line − cubes(i,j) + cubes(i − 1) < cubes(j) then

28:                                       cubes(j) = line − cubes(i,j) + cubes(i − 1)

29:                                    p(j) = i

30:                           end if

31:                   end for

32:           end for

33:           return cubes(n)

34: end function

 

Since NEATLY − PRINT include two double loops and one single loop, the running time is O(n2)

5             Problem 15-10 Planning an investment strategy
5.1
There are three cases:

1.     Move your money every year

In this case, it is obvious that you should choose the investment with the highest return rate each year to maximize your 10-year total amount.

2.     Do not move your money every year

Suppose that the 10-year total amount of money of choosing the first investment product is E1, choosing the second investment product is E2, ..., and choosing the nth investment product is En. If we choose two investment product k1 and k2, then the 10-year total amount must be the weighted sum of Ek1 and Ek2 which is not greater than the biggest one of Ek1 and Ek2. In this case, only choose one investment product each year which can maximize the return.

3.     Some years move the money and some years not

If we consider some years which move the money as consecutive years, then it will be regarded as a subproblem like case 1.If we consider some years which do not move the money as consecutive years, then it will be regarded as a subproblem like case 2.

Therefore, there exists an optimal investment strategy that, in each year, puts all the money into a single investment.

5.2
e[i,j] denote that the maximized total earning before jth year if we choose ith investment product in jth year. Analysis of dp[i][j] needs to consider two cases:

1.     Do not move the money in jth year

In this case, we must choose ith investment product in (j − 1)th year.

dp1[i][j] = (dp[i][j − 1] − f1) ∗ rij

2.     Move the money in jth year

In this case, we can select any investment product except ith investment product. Of course, we need to select the product which can maximize our total amount of money before jth year.

dp2 = max (dp[k][j] − f2) ∗ rij and k ̸= i

1≤k≤n

The dp[i][j] should choose the biggest one between case 1 and case 2, that is

dp[i][j] = max{dp1[i][j],dp2[i][j]}

Therefore, the problem of planning your optimal investment strategy exhibits optimal substructure since the maximizing returns in jth year depends on the maximizing returns in (j − 1)th year.

5.3
 

Algorithm 8 Optimal investment strategy

 

1: function Invest-strategy(r,n,c)

2:               let e[1..n,1..10] and p[1..n,2..10]be two new 2D tables

3:               for i = 1 to n do

4:                      e[i,1] = c ∗ ri1

5:             end for

6:               for j = 2 to 10 do

7:                       for i = 1 to n do

8:                                 e[i,j] = (e[i,j − 1] − f1) ∗ rij

9:                              p[i,j] ← i

10:                            for k = 1 to n do

11:                                         if k ̸= i then t = (e[k,j − 1] − f2) ∗ rij

12:                                            if t > e[i,j] then

13:                                                   e[i,j] = t

14:                                                   p[i,j] ← k

15:                                          end if

16:                                  end if

17:                           end for

18:                   end for

19:           end for

20:           max ← e[1,10]

21:           s10 ← 1

22:             for k = 1 to n do

23:                     if e[k,10] > max then

24:                           max = e[k,10]

25:                           s10 ← k

26:                   end if

27:           end for

28: return e,p and s10 29: end function

30:

31: function Print-investment(p,j,s)

32:             if j > 0 then

33:                            if j > 1 then Print-investment(p,j,s)

34:                   end if

35:                   print s

36:           end if

37: end function

 

The running time is O(n2).

5.4
When there has a limitation on the amount you can invest, the amount you have to invest in the next year becomes relevant. If we have an optimal investment strategy, that means we have to solve the subproblem for every possible initial amount of money. Since the limitation of a single investment, we have to make multiple investments so the optimal substructure no longer exists.