# Week 5

:::info
:::spoiler Click to Open TOC
[TOC]
:::

## Question
:::info
:::spoiler Click to Open Question

### Check
- [ ] Q1 Yee
- [ ] Q2 Mark
- [x] Q3 Mark
- [ ] Q4 songchiu
- [x] Q5 Xian
- [ ] Q6 Chung
- [ ] Q7 LXS
:::

## Answer
### Q1
> - [name=yee]


:::spoiler 【題目】
Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi / i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.
:::

#### 【Thought】
Because greedy strategy is to find local maximum, which means find the max density, therefore ,in cutting rods problem can't always find an optimal way ,which is global maximum.

#### 【Counter Example】

| $price\ pi$ | 1 | 6 | 8 |
| ----------- | --- | --- |:---:|
| $length\ i$ | 1 | 2 | 3 |
| $pi/i$ | 1 | 3 | 2.67 |

$Greedy (2,1) = 6 + 1 = 7\\
Optimal\ way (3) = 8\\
8 > 7\\
\text{Thus, greedy strategy does not always determine an optimal way to cut rods.}$
### Q2 DP切鋼筋
> - [name=Mark]


##### 初始化

function(p, n)
    //initialize memo
    //array r[] 用來存最大收益
    r[0] = 0     //都不切
    for i = 1 to n
        r[i] = -1     //初始化負的代表還未計算過
    return Cut_Rod(p, n, r)

#### Top-Downの作法

Memoized_Cut_Rod(p, n, r)
    if r[n] >= 0 return r[n]     //True, 代表該長度已計算過
    q = -1     // init q, q = Max_Revenue of Length N
    for i = 1 to n     //O(n^2) //c為fixed cost
        if q < p[i] + Memoized_Cut_Rod(p, n-i, r) - c
            then q = p[i] + Memoized_Cut_Rod(p, n-i, r) -c
    r[n] = q     //紀錄 Max_Revenue

    return r[n]

遞迴式：
$r_{n}=max_{1 \leq i \leq n}\{p_{i}+r_{n-i}-c\}$
$r_{0}=0,\;p_{i}=\text{the left part of cutting rod,}$$r_{i}=\;\text{max revenue the remaining part of cutting rod,}$
$c=\text{the fixed cost of each cut}$
時間複雜度：$T(n) = O(n^2)$

#### Bottom-Upの作法

Bottom_Up_Cut_Rod(p, n, r)
    for j = 1 to n //O(n^2)，雙層 for loop
        q = -1 // init q, q = Max_Revenue of Length N
        for i = 1 to j
            //在由小到大的情況下，每計算q時r[]必定已計算過
            if q < p[i] + r[j - i] -c //c為fixed cost
                then q = p[i] + r[j - i] -c
        r[j] = q
        
    return r[j]

遞迴式：
$r_{j}=max_{1 \leq j \leq n}\{max_{1 \leq i \leq j}\{p_{i}+r_{j-i}-c\}\}$
$r_{0}=0,\;p_{i}=\text{the left part of cutting rod,}$$r_{j-i}=\;\text{max revenue the remaining part of cutting rod,}$
$c=\text{the fixed cost of each cut}$
時間複雜度：$T(n) = O(n^2)$
### Q3 DP切鋼筋且要附做法
> - [name=Mark]


#### 改良 Top-Down

Memoized_Cut_Rod_With_Arg(p, n, r, cut)
    if r[n] >= 0 return r, cut
    q = -1 //同上
    for i = 1 to n
        if q < p[i] + Memoized_Cut_Rod(p, n-i, r) - c
            then q = p[i] + Memoized_Cut_Rod(p, n-i, r) -c
                 arg = i //得到當前最大的revenue時，紀錄i為Cut_Point
    r[n] = q
    cut[n] = arg
    return r, cut

遞迴式（承第二題）：
$cut_{n}=arg \; max_{1 \leq i \leq n}\{p_{i}+r_{n-i}-c\}$
$\text{cut = when lengh is n, which 'i' achived max}$
$\text{arg can assign 'i' which achived max to cut}$

#### 改良 Bottom-Up

Bottom_Up_Cut_Rod(p, n, r, cut)
    for j = 1 to n
        q = -1 
        for i = 1 to j
            if q < p[i] + r[j - i] - c
                then q = p[i] + r[j - i] - c
                     arg = i //得到當前最大的revenue時，紀錄i為Cut_Point
        r[j] = q
        cut[j] = arg
    return r, cut

遞迴式（承第二題）：
$cut_{j}=arg \; max_{1 \leq j \leq n}\{max_{1 \leq i \leq j}\{p_{i}+r_{j-i}-c\}\}$
$\text{cut = when lengh is n, which 'j' achived max}$
$\text{arg can assign 'j' which achived max to cut}$

### Q4
> - [name=songchiu]


#### 【初始值】
為題目給的數列$5, 10, 3, 12, 5, 50, 6$
並且陣列$m$內的元素皆預設為$INT\_MAX$

#### 【遞迴式】
$m[i,j] =
\begin{cases}
0 , &i \geq j\\
min_{i \leq k < j}\{m[i,k] + m[k+1, j]+p_{i-1}p_kp_j\}, & i < j
\end{cases}$

此陣列$m[i,j]$係存放矩陣從$i$相乘至$j$時，所需要的最小花費
並且為提升效能，在進行相乘時，可先透過變數$k$，來去查詢過去已計算好的值$m[i,k]$與$m[k+1, j]$
最後再將分割點$k$處的矩陣相乘值計算出來後相加，即可得到結果(因為$m[i,k]$與$m[k+1, j]$分別代表分割點$k$的左右兩邊，再加上分割點$k$的值後，即可組合出$m[i,j]$)
經過比較後，將計算出的最小值存至$m[i,j]$，並且將$k$值存放至另一陣列$s$，以供日後查詢相乘時的分割情況

#### 【蘇都扣 - 計算相乘結果】

for len from 2 to 7 
    for i from 1 to 7 - len + 1
        int j = i + len - 1;
        m[i][j] = INT_MAX;

        for k from i to j-1
            if(m[i][k] + m[k+1][j] + arr[i-1]*arr[k]*arr[j] < m[i][j]) 
                m[i][j] = m[i][k] + m[k+1][j] + arr[i-1]*arr[k]*arr[j];
                s[i][j] = k;

<!-- 註：陣列$m$是拿來存矩陣相乘的運算結果
　　陣列$s$是拿來存矩陣相乘時，$k$值為多少的情況下所算出的最小值 -->

#### 【蘇都扣 - 輸出最後結果】

Print-Parens(s, i, j)
    if i == j
        print Ai //輸出矩陣的名字
    else
        print "("
        Print-Parens(s, i, s[i][j])
        Print-Parens(s, s[i][j]+1, j)
        print ")"

#### 【題目所求的解答】

| m | 1 | 2 | 3 | 4 | 5 | 6 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 1 | 0 | 150 | 330 | 405 |1655 | 2010|
| 2 | | 0 | 360 | 330 |2430 | 1950|
| 3 | | | 0 | 180 | 930 | 1770|
| 4 | | | | 0 |3000 | 1860|
| 5 | | | | | 0 | 1500|
| 6 | | | | | | 0 |

| s | 1 | 2 | 3 | 4 | 5 | 6 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 1 | | 1 | 2 | 2 | 4 | 2 |
| 2 | | | 2 | 2 | 2 | 2 |
| 3 | | | | 3 | 4 | 4 |
| 4 | | | | | 4 | 4 |
| 5 | | | | | | 5 |

Note: $s[i,j]=$ a value of $k$ that gives the minimum

畫出圖形後可得(上面也有附程式碼)：

因此答案為$(A_1 A_2)((A_3A_4)(A_5A_6))$

### Q5
> - [name=xian]


:::spoiler 【題目】
#### 【題目】
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⋅5. There are two ways to parenthesize the expression 2+(7⋅5) = 37 and (2+7)⋅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 ‘⋅’.
:::
#### 【解題思路】
因為題目說有 `+ - *` 三種運算符號，因此需要考慮 `負值x負值` 之類的狀況，所以要探討每個區間最大最小值做運算的狀況(有可能會是兩個子區間的最小值相乘而得到最大值)，首先我們可以將表達式$a_1\ op_1\ a_2\ op_2\cdots\ op_{n-1}\ a_n$的數字 $[\ a_1,a_2,\cdots,a_n\ ]$ 和運算符號 $[\ op_1,op_2,\cdots,op_{n-1}\ ]$ 分開來看。

而我們需要有兩個二維矩陣(數字大小)分別儲存子表達式內最大值`max[i][j]`及最小值`min[i][j]`，代表 `i` 到 `j` 所計算出來的最大值及最小值，而運算符號則放在一維陣列內 `op[n-1]`。

#### 【遞迴式】
$max[i][j],\ min[i][j] = a_i\; ,\;if\;i=j.$
\begin{align*}
max[i][j]\ =\ Max_{i\le k < j}
\begin{cases}
max[i][k] &op[k]\quad max[k+1][j]\\
max[i][k] &op[k]\quad min[k+1][j]\\
min[i][k] &op[k]\quad max[k+1][j]\\
min[i][k] &op[k]\quad min[k+1][j]
\end{cases}，max[i][j]代表subexpression數字i到j裡所算出來的最大值。
\end{align*}
\begin{align*}
min[i][j]\ =\ Min_{i\le k < j}
\begin{cases}
max[i][k] &op[k]\quad max[k+1][j]\\
max[i][k] &op[k]\quad min[k+1][j]\\
min[i][k] &op[k]\quad max[k+1][j]\\
min[i][k] &op[k]\quad min[k+1][j]
\end{cases}，min[i][j]代表subexpression數字i到j裡所算出來的最小值。
\end{align*}

#### 【蘇都扣】

//初始值設定 
n = num_size;
for i from 1 to n:
    max[i][i] = a[i],  min[i][i] = a[i];

//主code
get_Max_expression(1,n){
    for q from 1 to n-1:    //不能超過n，固定現在運算的長度。
        for i from 1 to n-q:   //會是以陣列為斜的算下去
            j = i + q;
            (max[i][j],min[i][j]) = sub_expression_result(i, j);
    return max[1][n];
}

//跑遞迴式
sub_expression_result(i, j){
    minimum = INT_MAX, maximum = INT_MIN;
    for k from i to j-1:
        MM = max[i][k] op[k] max[k+1][j];//op是運算符號
        Mm = max[i][k] op[k] min[k+1][j];
        mM = min[i][k] op[k] max[k+1][j];
        mm = min[i][k] op[k] min[k+1][j];
        maximum = Max(MM, Mm, mM, mm, maximum);
        minimum = Min(MM, Mm, mM, mm, minimum);
    return maximum, minimum;
}

#### 【Example Expression = 3 + -4 * 7 + 6】
| min | 1 | 2 | 3 | 4 |
|:---:|:---:|:---:|:---:|:---:|
| 1 | 3 | -1 | -25 | -49 |
| 2 | | -4 | -28 | -52 |
| 3 | | | 7 | 13 |
| 4 | | | | 6 |

| max | 1 | 2 | 3 | 4 |
|:---:|:---:|:---:|:---:|:---:|
| 1 | 3 | -1 | -7 | -1 |
| 2 | | -4 | -28 | -22 |
| 3 | | | 7 | 13 |
| 4 | | | | 6 |

$Ans: max[1][4]=-1_\#$

### Q6
> - [name=chung]


#### 【題目】
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?

#### 【分析】

RECURSIVE-MATRIX-CHAIN iterates over all possible splitting point $i \leq k \leq j-1$, and calls itself on the two emerging subchains, and combines the results. Therefore, for splitting point k, it find the solutions for $A[i...k]$ and $A[k+1...j]$ separately, and combines them. Running time for RECURSIVE-MATRIX-CHAIN is $O({{n}{3^{n-1}}})$

On the other hand, enumerating all the ways of parenthesizing the product would consider splitting point k in the following way:
- For each possible way to parenthesize $A[i...k]$, Consider every possible way to parenthesize $A[k+1...j]$ and keep track of the minimal scenario among all combinations.
- The running time for enumerating all the ways of parenthesizing the product is $O({\frac {4^n}{n^ \frac32}})$

Therefore doing much more work. The problem is that it doesn't use the optimal substructure property and then taken together that solve the bigger problem of optimal parenthesizing with splitting point k.

<!-- #### 【分析二】
 -->

#### 【Ans】
Running RECURSIVE-MATRIX-CHAIN performs better than enumerating all the ways of parenthesizing the product.

[Matrix-Chain Multiplication參考影片](https://www.youtube.com/watch?v=x6NQ3oHOHuI&ab_channel=VivianNTUMiuLab)
<!--  -->
<!-- 
-->
### Q7
> - [name=LXS]


$\text{Suppose four matrices }A_1A_2A_3A_4\text{ with dimension }(p_0,p_1,p_2,p_3,p_4)=(13,5,4,3,34)\text{ respectively}\\
\text{Therefore we choose k=3 to minimize }p_0p_3p_4=13\times3\times34=1326\\
\text{Spliting the problem into }(A_1A_2A_3)A_4\\
\text{Then k=2 with }p_0p_3p_4=13\times4\times3=156\\
\text{Therefor the optimal parenthesization by this method is }((A_1A_2)A_3)A_4)\\
\text{However by enumerate all combanation of parenthesization}\\
\text{The optimal solution should be }((A_1(A_2A_3))A_4)\\
(A_1(A_2(A_3A_4)))\text{ costs}=13\times5\times34+5\times4\times34+4\times3\times34=3298\\
(A_1((A_2A_3)A_4))\text{ costs}=13\times5\times34+5\times3\times34+5\times4\times3=2780\\
((A_1A_2)(A_3A_4))\text{costs}=13\times4\times34+13\times5\times4+4\times3\times34=2436\\
((A_1(A_2A_3))A_4)\text{ costs}=13\times3\times34+13\times5\times3+5\times4\times3=1581\\
(((A_1A_2)A_3)A_4)\text{ costs}=13\times3\times34+13\times4\times3+13\times5\times4=1742\\
\text{In this case the greedy approach yields a sub-optimal solution.}$