---
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.
## 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);
}
```
Sign in with Wallet
Connect another wallet