---
# System prepended metadata

title: algorithm VI

---

---
title: algorithm VI
description: 第六次作業
---
# Group 2 
組員:王承隆、賴文宏、施宗佑、王昱翔、王柏喬、莊淳方、傅文宗

# Problem 1(done)
[CLRS 3 rd ] Exercise 15.2-1
- [x]完成[name=Joe]
- [x]複查[name=Zongyou]
## Topic
Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is 
$⟨5,10,3,12,5,50,6⟩$
## Solution


|       | $A_2$       | $A_3$                     | $A_4$                      | $A_5$                          | $A_6$                             |
| ----- |:----------- | -----------------         | ----------------------     | --------------------------     | --------------------------------- |
| $A_1$ | $A_1A_2$<br>=150 | $(A_1A_2)A_3$<br>=330| $(A_1A_2)(A_3A_4)$<br>=405 | $(A_1A_2)(A_3A_4)A_5$<br>=1655 | $(A_1A_2)((A_3A_4)(A_5A_6))$=2010 |
| $A_2$ | --------    | $A_2A_3$<br>=360          | $A_2(A_3A_4)$<br>=330      | $A_2((A_3A_4)A_5)$<br>=2430    | $A_2((A_3A_4)(A_5A_6))$<br>=1950  |
| $A_3$ | --------    | --------                  | $A_3A_4$<br>=180           | $(A_3A_4)A_5$<br>=930          | $(A_3A_4)(A_5A_6)$<br>=1770       |
| $A_4$ | --------    | --------                  | --------                   | $A_4A_5$<br>=3000              | $A_4(A_5A_6)$<br>=1860            |
| $A_5$ | --------    | --------                  | --------                   | --------                       | $A_5A_6$<br>=1500                 |

$(A_1A_2)((A_3A_4)(A_5A_6))=2010為最佳解$

$(5*10)(10*3)(3*12)(12*5)(5*50)(50*6)$
$\rightarrow((5*10)(10*3))((3*12)(12*5)(5*50)(50*6))$
$\rightarrow((5*10)(10*3))(((3*12)(12*5))((5*50)(50*6)))$

```c++=
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void printSolution(vector<vector<int>> s, int i, int j){
    if(i == j){
        cout << "A" << i;
        return;
    }
    cout << '(';
    printSolution(s, i, s[i][j]);
    printSolution(s, s[i][j] + 1, j);
    cout << ')';
}

//dim[0..n], m[1..n][1..n], s[1..n-1][2..n]
void minimalMultiplication(vector<int> dim){
	vector<vector<int>> m(dim.size(), vector<int> (dim.size(), 0)), s(dim.size(), vector<int> (dim.size(), 0));
	int i, j, k, min;
	//the length of subproduct
	for(i = 2;i < dim.size();i++){
		//left and right, jth to j + i - 1th matrix
		for(j = 1;j + i - 1 < dim.size();j++){
			min = INT_MIN;
			//the minimum of calcutlation of i matrices
			for(k = j;k < i + j - 1;k++){
				if(min > m[j][k] + m[k + 1][i + j - 1] + dim[j - 1]*dim[k]*dim[i + j - 1]){
					min = m[j][k] + m[k + 1][i + j - 1] + dim[j - 1]*dim[k]*dim[i + j - 1];
					s[j][i + j - 1] = k;
				}
			}
			m[j][i + j - 1] = min;
		}
	}
	printSolution(s, 1, dim.size() - 1);
	cout << " = " << m[1][dim.size() - 1] << endl;
}

int main(){
	vector<int> dim;
	int n;
	while(cin >> n)
		dim.push_back(n);

	minimalMultiplication(dim);
}
```
# Problem 2

## Topic
A mathematical expression is given without parentheses. Design an algorithm to
parenthesize the expression such that the value of the expression is maximized.
For example, consider the expression: 2+7 $\times$ 5. There are two ways to parenthesize
the expression 2+(7$\times$ 5) = 37 and (2+7)$\times$ 5 = 45, so in this case, your algorithm
should output the second expression. Here, you may assume the given expressions
contain only 3 kinds of binary operators ‘+’, ‘−’, and ‘$\times$’.

## Solution

```Pseudocode
calculate(number, sign, m, l, k, r)
    //number is an array of number, sign is an array of char [0 : n-1]
    //m is a 2-dimension array [0:n-1][0:n-1] 
    //l is left bound index, r is right bound index
    //k is the index of the position to separate
    int a,b
    if l==k do
        a = number[l]
    else 
        a = m[l][k]
    end if
    
    if k+1 == r d0
        b = number[r]
    else 
        b = m[k+1][r]
    end if
    
    if sign[k] == '+' do
        return a+b
    else if sign[k]=='-' do
        return a-b
    else if sign[k]== '*' do
        return a*b
    end if


printSolution(number, sign, s, int i, int j){
    //s is a 2-dimension array of solution [0:n-1][0:n-1] 
	if i == j do
		print (number[i]);
		return
	end if
	print('(')
	printSolution(number, sign, s, i, s[i][j]);
	print(sign[s[i][j]])
	printSolution(number, sign, s, s[i][j] + 1, j);
	print(')')
}

//number[0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
maxvalue(number, sign){
    number[0..n-1], sign[0..n-1][0..n-1],  m[0..n-1][0..n-1], s[0..n-2][1..n-1]
	int i, j, k, max, num;
	//the length of numbers
	for i from 2 to number.size() do
		//left and right, jth to j + i - 1th number
		for j from 0 to number.length()-i do
			max = INT_MIN
			//the maximum of calcutlation of i numbers
			for k  from j to i+j-2 do
                            num = calculate(number, sign, m, j, k, i+j-1)
                            if max < num do
				    max = num
				    s[j][i + j - 1] = k
			     end if
                       end for
			m[j][i + j - 1] = max
                end for
        end for
	printSolution(number, sign, s, 0, number.size() - 1)
	print('='m[0][number.size() - 1])
}
```
``` C++=
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int calculate( vector<int>number, vector<char>sign, vector<vector<int>> m, int l, int k, int r){
    int a,b;
    if(l==k)
        a = number[l];
    else 
        a = m[l][k];
    if(k+1==r)
        b = number[r];
    else 
        b = m[k+1][r];
    switch (sign[k]){
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        default: exit(1);
    }
}

void printSolution(vector<int> number, vector<char> sign, vector<vector<int>> s, int i, int j){
	if(i == j){
		cout << number[i];
		return;
	}
	cout << '(';
	printSolution(number, sign, s, i, s[i][j]);
	cout << sign[s[i][j]];
	printSolution(number, sign, s, s[i][j] + 1, j);
	cout << ')';
}

//number[0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
void maxvalue(vector<int> number, vector<char> sign){
	vector<vector<int>> m(number.size(), vector<int> (number.size(), 0)), s(number.size(), vector<int> (number.size(), 0));
	int i, j, k, max, num;
	//the length of numbers
	for(i = 2;i <= number.size();i++){
		//left and right, jth to j + i - 1th number
		for(j = 0;j + i - 1 < number.size();j++){
			max = INT_MIN;
			//the maximum of calcutlation of i numbers
			for(k = j;k < i + j - 1;k++){
                            num = calculate(number, sign, m, j, k, i+j-1);  
                            if(max < num){
				    max = num;
				    s[j][i + j - 1] = k;
			    }
			}
			m[j][i + j - 1] = max;
		}
	}
	printSolution(number, sign, s, 0, number.size() - 1);
	cout << " = " << m[0][number.size() - 1] << endl;
}

int main(){
    vector<int> number;
    vector<char> sign; 
    int n, number_length;
    char c;
    cin>>number_length;
	while(number_length--){
        cin>>n;
		number.push_back(n);
        if(number_length!=0){
            cin>>c;
            sign.push_back(c);
        }
    }
	maxvalue(number, sign);
}   
```
# Problem 3(done)
[CLRS 3 rd ] Exercise 15.3-1
## Topic
Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running $RECURSIVE-MATRIX-CHAIN$? Justify your answer.

![](https://i.imgur.com/dOjF7PB.png)
## Solution
Brute-force:
    $\Omega(\frac {4^n}{n^{\frac32}})$ from catalan number
RECURSIVE−MATRIX−CHAIN:
    $\Theta (n^3)$
RECURSIVE−MATRIX−CHAIN is better.

# Problem 4
[CLRS 3 rd ] Exercise 15.4-5
## Topic
Give an O(n^2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
## Solution
```
Pseudocode
longestIncSubseq(seq){
    //seq is a array
	sorted[1..seq.size()] = seq
	sort(sorted)

	int i, j, counter
	int len[0..seq.size()][0..sorted.size()] = {}

	for i from 1 to seq.size() do
		for j from 1 to sorted.size()do
			if seq[i - 1] == sorted[j - 1] do
				len[i][j] = 1 + len[i - 1][j - 1]
			else
                            if len[i - 1][j] > len[i][j - 1] do
                                len[i][j] = len[i - 1][j]
                            else
                                len[i][j] = len[i][j - 1]
                            end if
		        end if
                end for
	end for

	stack sub
	counter = len[seq.size()][sorted.size()]
        i = seq.size()
        j = sorted.size()
        while i > 0 and j > 0 and counter > 0 do
		if counter == len[i - 1][j] do
			i--
		else if(counter == len[i][j - 1]) do
			j--
		else if(counter - 1 == len[i - 1][j - 1]) do
                    sub.push_back(seq[--i])
                    j--
                    counter--
                end if
	end while
	while(!sub.empty()) do
		print(sub.top())
		sub.pop();
	end while
}
```

```C++=
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

void longestIncSubseq(vector<int> seq){
	vector<int> sorted = seq;
	sort(sorted.begin(), sorted.end());

	int i, j, counter;
	int len[seq.size() + 1][sorted.size() + 1] = {};

	for(i = 1;i <= seq.size();i++){
		for(j = 1;j <= sorted.size();j++){
			if(seq[i - 1] == sorted[j - 1])
				len[i][j] = 1 + len[i - 1][j - 1];
			else
				len[i][j] = len[i - 1][j] > len[i][j - 1] ? len[i - 1][j] : len[i][j - 1];
		}
	}

	stack<int> sub;
	for(counter = len[seq.size()][sorted.size()], i = seq.size(), j = sorted.size();i > 0, j > 0, counter > 0;){
		if(counter == len[i - 1][j])
			i--;
		else if(counter == len[i][j - 1])
			j--;
		else if(counter - 1 == len[i - 1][j - 1]){
            sub.push(seq[i - 1]);
            i--;
            j--;
            counter--;
        }
	}
	cout << "longestIncSubseq:";
	while(!sub.empty()){
		cout << sub.top() << ' ';
		sub.pop();
	}
	cout << endl;
}

int main(){
	vector<int> seq;
	int n;
	while(cin >> n)
		seq.push_back(n);

	longestIncSubseq(seq);
}

```
# Problem 5
[CLRS 3 rd ] Problem 15-5 Edit distance(要寫Code)
## Topic
[題目連結](https://walkccc.github.io/CLRS/Chap15/Problems/15-5/)

```C++=
// solution
#include <bits/stdc++.h> 
#include <vector>
using namespace std; 
string ops[7] = {"0", "C", "R", "D", "I", "T", "K"};
void ed(string str1, string str2, int cost[]) { 
  int m = str1.length(), n = str2.length();
  int dp[m+1][n+1], s[m+1][n+1] = {};
  for(int i = 0;i<=m;i++)
    for(int j = 0;j<=n;j++)
      dp[i][j] = INT_MAX;
  dp[0][0] = -1;
  s[0][0] = -1;
  int temp;

	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
      if(str1[i] == str2[j]) {
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + cost[0]);
        if(dp[i + 1][j + 1] == dp[i][j] + cost[0])
          s[i + 1][j + 1] = 0;
        temp = 0;
      }else{
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + cost[1]);
        if(dp[i + 1][j + 1] == dp[i][j] + cost[1])
          s[i + 1][j + 1] = 1;
        temp = 1;
      }
      
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost[2]);
      if(dp[i + 1][j] == dp[i][j] + cost[2])
        s[i + 1][j] = 2;
      
      dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cost[3]);
      if(dp[i][j + 1] == dp[i][j] + cost[3])
        s[i][j + 1] = 3;
      
      if(str1[i+1]==str2[j] && str1[j+1]==str2[i]){
        dp[i + 2][j + 2] = min(dp[i + 2][j + 2], dp[i][j] + cost[4]);
        if(dp[i + 2][j + 2] == dp[i][j] + cost[4])
          s[i + 2][j + 2] = 4;
      }

      dp[m][j] = min(dp[m][j], dp[i][j] + cost[5]);
      if(dp[m][j] == dp[i][j] + cost[5])
        s[m][j] = 5;
    }
	}

  /*
  cout<<"\t  ";
  for(int i=0;i<n;i++)
    cout<<i<<" ";
  cout<<"\n\n";
  for(int i=0;i<=m;i++){
    if(s>0)
    cout<<i-1<<"\t";
    else
    cout<<"\n\t";
    for(int j=0;j<=n;j++){
      cout<<(s[i][j]==-1?"0":ops[1+s[i][j]])<<" ";
    }

    cout<<"\n";
  }
	cout<<dp[m][n]<<"\n";
  */
  int M = m, N = n;
  m = 0;
  n = 0;
  while(m<=M&&n<=N){
    int mc = m+1, nc = n+1;
    
    cout<<ops[(s[m][n]+1)]<<" ";
    //cout<<"\t"<<m<<", "<<n<<"\n";
    
    if(s[m+1][n]<s[mc][nc]){
      nc--;
    }
    if(s[m][n+1]<s[mc][nc]){
      mc = m;
      nc = n+1;
    }

    m = mc;
    n = nc;
  }
  cout<<endl;
} 

// Driver program 
int main() 
{ 
    // your code goes here 
    string str1 ="sunday"; 
    string str2 ="saturday";
    // cin>>str1>>str2; 
    int cost[6] = {1, 1, 1, 1, 1, 1};
    //for(int i = 0;i<6;i++)
    //    cin>>cost[i];
    //cout<<str1<<"\t"<<str2<<endl;
    ed(str1, str2, cost); 
    return 0; 
}
```
# Problem 6(done)

## Topic
- [x] 完成[name=ZoneTwelve]
  [time=Thu, Apr 9, 2020 2:25 PM]
- [x] 複查[name=Zongyou]
  [time=Thu, Apr 9, 2020 0:00 PM]

Find out all **LCS** of《BADBCBA》and《ABACDBC》

## Solution:
| | | |L|C|S| | | |
|-|-|-|-|-|-|-|-|-|
| |∅|B|A|D|B|C|B|A|
|∅|0| | | | | | | |
|A|0| | | | | | | |
|B| |1| | | | | | |
|A| | |2| | | | | |
|C| | | |2| | | | |
|D| | | |3| | | | |
|B| | | | |4| | | |
|C| | | | | |5|5|5|

Result: **BADBC**
# Problem 7
String Alignment(要寫Code)
## Topic

Let $\sigma$ be an alphabet set, $\beta$ denote the blank character in $\sigma$ , and a measure function F:
$\sigma\times\sigma$ → R. Where F is defined as followings, for any x and y in $\sigma$ , F(x, y)<0 if x$\neq$y and
F(x, y)>0 if x=y; whereas F( $\beta$ , $\beta$ )=-$\infty$. Given X and Y be two strings of $\sigma$ * , let X’ and Y’
denote two new strings made by inserting some $\beta$ into X and Y respectively. The
similarity of X and Y is defined by measuring the maximal value of
$\sum_{ a_i ∈X′, b_i ∈Y′} F(a_i , b_i )$ 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.
## Solution (a, b一起)
```
Pseudocode 
stringAlignment(s1, s2, gap, dismatch, match){
        //gap is the score of either s1[i] or s2[i] is space
        //m records maximal similarity of substrings of s1 and s2
	int m[0..s1.length][0..s2.length], topLeft, left, top, max; 
        //s records how we get the maximal similarity
	char s[0..s1.length][0..s2.length]; 
	m[0][0] = 0;
	for i = 1 to s1.length do
		m[i][0] = m[i - 1][0] + gap;
	for i = 1 to s2.length do
		m[0][i] = m[0][i - 1] + gap;

	//constuct m and s
	for i = 1 to s1.length do
		for j = 1 to s2.length do
			if s1[i - 1] == s2[j - 1];
				topLeft = m[i - 1][j - 1] + match;
			else
				topLeft = m[i - 1][j - 1] + dismatch;
			left = m[i][j - 1] + gap;
			top = m[i - 1][j] + gap;
			
			max = Max(topLeft, left, top);
			if max == topLeft
				s[i][j] = '↖';
			else if max == top
				s[i][j] = '↑';
			else if max == left
				s[i][j] = '←';
			m[i][j] = max;
            end for
        end for
	
	//find s1' and s2'
	string s1' = "", s2' = "";
	i = s1.length;
	j = s2.length;
	while(i > 0 || j > 0)
		if s[i][j] == '↖'
			s1' = s1[--i] + s1';
			s2' = s2[--j] + s2';
		else if s[i][j] == '↑'
			s1' = s1[--i] + s1';
			s2' = ' ' + s2';
		else if s[i][j] == '←'
			s1' = ' ' + s1';
			s2' = s2[--j] + s2';
	end while
    
	return m[s1.length][s2.length], s1', s2';
}
	
				

```
```C++=
#include <iostream>
#include <vector>
#include <iomanip>
#include <tuple>

using namespace std;

int Max(int a, int b){
	return a > b ? a : b;
}

void stringAlignment(string s1, string s2, int gap, int dismatch, int match){
	int i, j, max, lu, l, u;
	vector<vector<tuple<int, int>>> len(s1.size() + 1, vector<tuple<int, int>>(s2.size() + 1, make_tuple(0, 0)));
	for(i = 1;i <= s1.size();i++)
		get<0>(len[i][0]) = get<0>(len[i - 1][0]) + gap;
	for(i = 1;i <= s2.size();i++)
		get<0>(len[0][i]) = get<0>(len[0][i - 1]) + gap;

	//get the length of longest subseq of length i from head
	for(i = 1;i <= s1.size();i++){
		for(j = 1;j <= s2.size();j++){
			lu = get<0>(len[i - 1][j - 1]) + (s1[i - 1] == s2[j - 1] ? match : dismatch);
			l = get<0>(len[i][j - 1]) + gap;
			u = get<0>(len[i - 1][j]) + gap;
			max = Max(lu, Max(l, u));
			
			if(max == lu)
				get<1>(len[i][j]) = 0;
			else if(max == u)
				get<1>(len[i][j]) = 1;
			else if(max == l)
				get<1>(len[i][j]) = 2;
			get<0>(len[i][j]) = max;
		}
	}

	vector<char> s1b, s2b;
	for(i = s1.size(), j = s2.size();i > 1 || j > 1;){
		switch(get<1>(len[i][j])){
			case 0:
				s1b.push_back(s1[--i]);
				s2b.push_back(s2[--j]);
				break;
			case 1:
				s1b.push_back(s1[--i]);
				s2b.push_back(' ');
				break;
			default:
				s1b.push_back(' ');
				s2b.push_back(s2[--j]);
		}
	}
	switch(get<1>(len[i][j])){
            case 0:
                s1b.push_back(s1[--i]);
                s2b.push_back(s2[--j]);
                break;
            case 1:
                s1b.push_back(s1[--i]);
                s2b.push_back(' ');
                break;
            default:
                s1b.push_back(' ');
                s2b.push_back(s2[--j]);
        }

	cout << endl << "similarity:" << get<0>(len[s1.size()][s2.size()]) << endl << "s1:";
	for(i = s1b.size();i >= 0;i--)
		cout << s1b[i];
	cout << endl << "s2:";
	for(i = s2b.size();i >= 0;i--)
		cout << s2b[i];
	cout << endl;
}

int main(){
	string s1, s2;
    int gap, match, dismatch;
    cout << "s1:";
	cin >> s1;
    cout << "s2:";
    cin >> s2;
    cout << "scores" << endl << "gap:";
    cin >> gap;
    cout << "match:";
    cin >> match;
    cout << "dismatch:";
    cin >> dismatch;
	stringAlignment(s1, s2, gap, dismatch, match);
}
```