# 演算法作業 五

###### tags: `演算法`

1. Suppose that in the rod-cutting problem of Section 15.1, we also had limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, …, n$. Show that the optimal-substructure property described in Section 15.1 no longer holds.

Answer:
假設$l_i$全部都是1，代表任何長度都不能再切割，那rod-cutting problem就沒辦法由自己的子問題當中挑選最佳的兩個子問題出來組成自己的答案。
子問題之間會互相影響。所以optimal structure不存在

2. Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities:

Answer:
the cost is 3.12
the structure is

5
/ \
2 7
/\ /
1 3 6
\
4

code:

    

    #include <iostream>
    #define size 8

    using namespace std;

    int s[size][size];

    inline void print_opt_bst(int start, int end) {
        cout << "start " << start << " end " << end << endl;
        cout << s[start][end] << endl;

        if (start < end) {
            if (s[start][end] - 1 >= start)
                print_opt_bst(start, s[start][end] - 1);
            if (end >= s[start][end])
                print_opt_bst(s[start][end] + 1, end);
        }

    }

    int main()
    {
        double p[size];
        double q[size];
        double E[size][size],w[size][size];

        //initialize
        cin >> q[0];
        for (int i = 1; i < size; i++) {
            cin >> p[i] >> q[i];
        }

        for (int i = 1; i < size; i++) {
            E[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];
            s[i][i] = i;
        }
        //compute the optimal bst
        for (int l = 1; l < size; l++) {
            for (int i = 1; i < size - l+1; i++) {
                int j = i + l-1;
                double temp;
                E[i][j] = 1e10;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int k = i; k <= j; k++) {
                    temp = E[i][k - 1] + E[k + 1][j] + w[i][j];
                    if (temp < E[i][j]) {
                        E[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
        }

        cout << "the cost is " << E[1][size - 1] << endl;
        cout << "the structure is" << endl;
        print_opt_bst(1, size - 1);


        return 0;
    }

3. Given two sequences x[1..m] and y[1..n] and set of transformationoperation costs, the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y. Describe a dynamic-programming algorithm that finds the edit distance from x[1..m] to y[1..n] and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm.
**transformation-operations**
• **Insert** a character into x
• **Delete** a character from x
• **Replace** a character from x by another character
• **Twiddle** two adjacent characters from x

Answer:
我使用一個表格D來記錄dp的過程，D[i][j]代表從x[1...i]改變到y[1...j]所需要的最短edit distance。從D[i][j]移動到D[i+1][j]代表刪除x中一個字元的動作，從D[i][j]移動到D[i][j+1]代表新增一個字元進入x，從D[i][j]移動到D[i+1][j+1]代表置換x中的一個字元，如果直接從D[i][j]移動到D[i+2][j+2]，代表x[i]=y[j-1]且x[i-1]=y[j]，可以將x[i-1]和x[i]進行twiddle。

**初始值:**$D_{0i}=i$、$D_{i0}=i$
**遞迴式:** $c_i、c_d、c_r、c_t$ 分別代表Insert、Delete、Replace、Twiddle的cost。

$D_{ij}=\begin{cases}
D_{(i-1)(j-1)} \ \ if \ \ x_i==y_j \\
min(D_{(i-1)j}+c_d,D_{i(j-1)}+c_i,D_{(i-1)(j-1)}+c_r,D_{(i-2)(j-2)}+c_t) \ if \ i>1 \ and \ j>1 \ and \ x_i==y_{j-1} \ and \ x_{i-1}==y_j \\
min(D_{(i-1)j}+c_d, D_{i(j-1)}+c_i, D_{(i-1)(j-1)}+c_r)\\
\end{cases}$

**解答:**$D_{mn}$

**Pseudo code:**

    input: x[],y[],m,n //m is the length of x, n is the length of y
    
    EditDis(x[],y[],m,n){
        D[m+1][n+1];
        D[0][0]=0;
        
        //init
        x[0]='\0';//將x,y的第0個字元都設為不存在
        y[0]='\0';
        for i = 1:n
            D[0][i]=i;
        for i = 1:m
            D[i][0]=i;
        
        for i = 1:m
            for j = 1:n
                if x[i]==y[j]
                    D[i][j]=D[i-1][j-1];
                else if i>1 and j>1 and x[i]==y[j-1] and x[i-1]==y[j]
                    D[i][j]=
                    min(D[i-1][j]+C_d,D[i][j-1]+C_i,D[i-1][j-1]+C_r,D[i-2][j-2]+C_t);
                else
                    D[i][j]=
                    min(D[i-1][j]+C_d,D[i][j-1]+C_i,D[i-1][j-1]+C_r);
        
        return D[m][n];
    }
    

4. Find out all LCS of《BADBCBA》and《ABACDBC》

Answer:
BADBC
使用dp來解此題，並將每個可以組成LCS的字元儲存在一陣列s[i][j]當中，使用BFS來重新建構出所有可能的LCS。

5. An algorithm to solve the LCS problem of two strings X and Y has space complexity O(|X||Y|) typically.
**a.** Design an algorithm to find the length of LCS of two string X and Y just using only 2⋅min(|X|,|Y|) cells for working space.
**b.** Design an algorithm to find the length of LCS of two string X and Y just using only 1+min(|X|,|Y|) cells for working space.

Answer:

a. 使用一個陣列c大小為2*min(|X|,|Y|)來儲存計算結果，c[i][j]表示當中的元素，其中index j的範圍是0~min(|X|,|Y|)，如果j=0那c[i][0]=0，index i 的範圍則是0和1，所以整個陣列的空間是2*min(|X|,|Y|)
**初始值:** $c_{0i}=0$ c的第一列一開始全部都是0
**遞迴式:** $c_{ij}=\begin{cases}
0 \ \ if \ j=0\\
c_{(i-1)(j-1)}+1 \ if \ x_i=y_j\\
max(c_{i(j-1)},c_{(i-1)j}) \ if \ x_i!=y_j\\
\end{cases}$
**解答:** 在所有計算完成後，答案會儲存在c[1][min(|X|,|Y|)]當中
**pseudo code:**

    input: X,Y
    LCS_LENGTH(X,Y){
        len=min(X.length,Y.length);
        times=max(X.length,Y.length);
        c[2][len+1];
        
        //init
        c[0][0]=0;
        c[1][0]=0;
        for i = 1:len
            c[0][i]=0;
        x=longer_s(X,Y);//x為較長的那個字串
        y=shorter_s(X,Y);//y為較短的那個字串
        
        for i = 1:times
            for j = 1:len
                if x[i]==y[j]
                    c[1][j]=c[0][j-1]+1;
                else
                    c[1][j]=max(c[1][j-1],c[0][j])
            SWAP(c[0],c[1]);//將c的第一列與第二列互換     
        
        return c[1][len]
    }

b. 為了達到題目要求之空間複雜度，我設計一算法使用一個一維陣列c[min(X.length,Y.length)+1]
**初始值:** $c_i=0 \ for \ all \ i$
**遞迴式:** 在每一次計算到c[i]的時候都先用一個變數temp將c[i]計算前的數值存起來，算到c[i+1]的時候就會使用到temp變數。
以下$x_i、y_j$不一定是使用輸入原本的X、Y，以下式子中的x代表的是X跟Y當中比較長的字串，y則是短的那個。

$c_{i}=\begin{cases}
0 \ \ if \ i=0\\
temp+1 \ if \ x_i=y_j\\
max(c_i,c_{i-1}) \ if \ x_i!=y_j\\
\end{cases}$
**解答:** 最後的解會在c[min(X.length,Y.length)]中
**pseudo code**

    input: X,Y
    LCS_LENGTH(X,Y){
        len=min(X.length,Y.length);
        times=max(X.length,Y.length);
        c[len+1];
        //init
        for i = 0:len
            c[i]=0;
        x=longer_s(X,Y);
        y=shorter_s(X,Y);
        
        for i=1:times
            temp=c[0];
            for j = 1:len
                temp2=c[j];
                if x[i]==y[j]
                    c[j]=temp+1;
                else
                    c[j]=max(c[j],c[j-1]);
                    
                temp=temp2;
        
        return c[len]
    }

6. String Alignment
Let $σ$ be an alphabet set, $β$ denote the blank character in $σ$, and a measure function $F: σ×σ → R$. Where $F$ is defined as followings, for any $x$ and $y$ in $σ$, $F(x, y)<0$ if $x≠y$ and $F(x, y)>0$ if $x=y$; whereas $F(β,β)=-∞$. Given $X$ and $Y$ be two strings of $σ*$, let $X’$ and $Y’$ denote two new strings made by inserting some $β$ into $X$ and $Y$ respectively. The similarity of $X$ and $Y$ is defined by measuring the maximal value of $∑ 𝐹(𝑎𝑖̇, 𝑏𝑖) \ 𝑎𝑖𝜖𝑋 \ , \ 𝑏𝑖𝜖𝑌$ among all possible $X’$ and $Y’$.
a. Design an algorithm to find the similarity of $X$ and $Y$.
b. Design an algorithm that describe where the blank characters are inserted to get the similarity.

Answer:

a.
我使用一個陣列c[x.length+1][y.length+1]來儲存dp的計算過程，x[i]==y[j]，代表c[i][j]是c[i-1][j-1]+F(x[i],y[j])，如果x[i]!=y[j]，則要看此時i跟j誰較大，如果i較小，代表x當前代表的子字串較短，則將$β$插入x當中直到x和y長度相同，從c[i-1][j]移動到c[i][j]代表將x[i]和$β$配對，從c[i][j-1]移動到c[i][j]代表將y[j]和$β$配對，從c[i-1][j-1]移動到c[i][j]代表將x[i]和y[j]進行配對。
**初始值:** $c_{00}=0、c_{01}=F(y_1,β)、c_{10}=F(x_1,β)、c_{0i}=c_{0(i-1)}+F(y_i,β)、c_{i0}=c_{(i-1)0}+F(x_i,β)$
**遞迴式:** $c_{ij}=\begin{cases}
c_{(i-1)(j-1)}+F(x_i,y_j) \ if \ x_i==y_j\\
max(c_{(i-1)j}+F(x_i,β), c_{i(j-1)}+F(y_j,β), c_{(i-1)(j-1)}+F(x_i,y_j)) \ if \ x_i!=y_j\\
\end{cases}$

**解答:** 結果會儲存在c[x.length][y.length]當中
**pseudo code**

    input:X,Y
    funct(X,Y){
        m=X.length;
        n=Y.length;
        c[m+1][n+1];
        //init
        c[0][0]=0;//負無窮大
        c[0][1]=F(Y[1],β);
        for i = 2:n
            c[0][i]=c[0][i-1]+F(Y[i],β);
        c[1][0]=F(X[1],β);
        for i = 2:m
            c[i][0]=c[i-1][0]+F(X[i],β);
        
        for i = 1:m
            for j = 1:n
                if x[i]==y[j]
                    c[i][j]=c[i-1][j-1]+F(x[i],y[j]);
                else
                    c[i][j]=
                    max(c[i-1][j]+F(x[i],β),c[i][j-1]+F(y[j],β),c[i-1][j-1]+F(x[i],y[j]));
        
        return c[m][n];
    }

b.
加開一個陣列r[][]來儲存插入空白的地方，如果x字串的第i個字元對應到y字串的第j個字元，那r[i][j]='n'，如果x字串對應到空白字元，代表y的第j個位置被插入了一個空白字元，那r[i][j]='y'，相反則是r[i][j]='x'

    input:X,Y
    global variable:r[][]
    funct(X,Y){
        m=X.length;
        n=Y.length;
        c[m+1][n+1];
        //init
        c[0][0]=0;//負無窮大
        c[0][1]=F(Y[1],β);
        for i = 2:n
            c[0][i]=c[0][i-1]+F(Y[i],β);
        c[1][0]=F(X[1],β);
        for i = 2:m
            c[i][0]=c[i-1][0]+F(X[i],β);
            
        for i = 1:m
            for j = 1:n
                if x[i]==y[j]
                    c[i][j]=c[i-1][j-1]+F(x[i],y[j]);
                else
                    c[i][j]=max(c[i-1][j]+F(x[i],β),c[i][j-1]+F(y[j],β),c[i-1][j-1]+F(x[i],y[j]));
                if c[i][j]==c[i-1][j]+F(x[i],β)
                    r[i][j]='y';
                else if c[i][j]=c[i][j-1]+F(y[j],β)
                    r[i][j]='x';
                else
                    r[i][j]='n';
                
        return c[m][n];
    }
    
    Print_String_X(X,i,j){
        if i==0 and j==0
            return;
        if r[i][j]=='n'
            Print_String_X(X,i-1,j-1);
            print X[i];
        else if r[i][j]=='x'
            Print_String_X(X,i,j-1);
            print '_';
        else
            Print_String_X(X,i-1,j);
            print X[i];
    }
    
    Print_String_Y(Y,i,j){
        if i==0 and j==0
            return
        if r[i][j]=='n'
            Print_String_Y(Y,i-1,j-1);
            print Y[j];
        else if r[i][j]=='y'
            Print_String_Y(Y,i-1,j);
        else
            Print_String_Y(Y,i,j-1);
            print Y[j];    
    }

7. Give pseudocode to reconstruct an LCS from the completed c table and the original sequences $X = <𝑥_1, 𝑥_2,…,𝑥_𝑚>$ and $Y = <𝑦_1, 𝑦_2,…,𝑦_𝑛>$ in $O(m + n)$ time,without using the b table.

Answer:

    input:X,Y
    global variable: c[X.length+1][Y.length+1]
    LCS_LEN(X,Y){
        m=X.length;
        n=Y.length;
        for i = 1:m
            c[i][0]=0;
        for i = 1:n
            c[0][i]=0;
        for i = 1:m
            for j = 1:n
                if X[i]==Y[j]
                    c[i][j]=c[i-1][j-1]+1;
                else
                    c[i][j]=max(c[i-1][j],c[i][j-1]);
    }
    
    Print_LCS(X,i,j){
        if i==0 or j==0
            return
        if c[i-1][j-1]==(c[i][j]-1)
            Print_LCS(X,i-1,j-1);
            print X[i];
        else if c[i-1][j]==c[i][j]
            Print_LCS(X,i-1,j);
        else
            Print_LCS(X,i,j-1);
    }