# Week 4

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

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

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

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


int stock_buying_problem{
    int min_price = stock_price[0], max_profit = 0;
    for(int i = 1; i < stock_number;i++){
        if(min_price > stock_price[i])
            min_price = stock_price[i];
        else if(min_price < stock_price[i] && (stock_price[i] - min_price) > max_profit)
            max_profit = stock_price[i] - min_price;
    }
     return max_profit;
}

共做$n-1$次，因此時間複雜度為$O(n)$。
### Q2
> - [name=songchiu]


#### a.
$(2,1)$、$(3,1)$、$(8,6)$、$(8,1)$、$(6,1)$

#### b.
$\text{Array with descending order, it will have }(n-1)+(n-2)+...+1=\dfrac{(n-1)\times n}{2} \text{ inversions}$

#### c.
當inversion的數量越來越多時，跑insertion sort所花的時間就會越多
在所有元素皆已由小到大排序的情況下，會沒有inversion，所花的時間為$O(n)$ (從頭到尾走一遍檢查)
最差的情況為所有元素是由大到小排序，inversion會最多，此時所花的時間會來到$O(n^2)$ (要把整個array倒過來)

#### d.
【想法】
- 透過類似merge sort的方式，先兩兩一組比大小
- 如果左>右，則先將計數器+1，再執行正常的merge sort
- 如果左<右，則執行正常的merge sort
- 這樣可以確保當下右邊的都比左邊大，左邊or右邊無論內部要怎麼排序，皆不影響左邊與右邊的比較)

【時間複雜度】
這樣執行的時間就跟merge sort一樣，只是多了個counter而已，worst case的時間複雜度為 $\theta(n \; lg n)$

【程式碼】

int MergeSort(int array[], int front, int end)
{
    if (front < end)
    {
        int mid = (front+end)/2, temp[];
        int lIndex=front, rIndex=mid+1;
        MergeSort(array, front, mid);
        MergeSort(array, mid+1, end); 
        
        for(int i=front; i<=end && (lIndex <= mid && rIndex <= end) ; i++) //lIndex <= mid && rIndex <= end 要妹噗了QQ
            if(array[lIndex] <= array[rIndex])
                temp[i] = array[lIndex++];
            else
                temp[i] = array[rIndex++];
                counter++;
                
        for(int i=lIndex; i<=mid; i++)
            temp[i] = array[lIndex++]; //剩的抄一抄
        for(int j=rIndex; j<=end; j++)
            temp[j] = array[rIndex++]; //剩的抄一抄
            
            
        array[front~end] = temp[front~end];//將合併完成的資料寫回去
        
        //要不要寫這麼細啊，上面那段for其實就是在做merge的動作
        //不行這麼細的話就直接用個Merge函式帶過，然後再回傳個counter的值就好了？！！
        //我覺得還好
    }
    
    return counter;
}

註：變數`counter`預設為0

$\quad$

### Q3
> - [name=Xian]


#### 【題目程式碼】

STOOGE SORT(A, i, j){
    if A[ i ] > A[ j ]
        then exchange A[ i ] <-> A[ j ]
    if i + 1 >= j
        then return
    k <- ⌊(j – i + 1) / 3⌋
    STOOGE SORT(A, i, j - k)
    STOOGE SORT(A, i + k, j)
    STOOGE SORT(A, i, j - k)
}

#### 【A小題】
* #### Stable[O]
從程式碼第2、3行可得知，當進行升序sorting時，如果左邊數字較大，將會和右邊的數字做調換，但如果左邊數字小於等於右邊數字時，並不會作調換，且程式碼7-9所做的recursion是先處理前$\frac 23$的排序，再處理後$\frac 23$(詳細請看第b小題)，因此排序完後，並不會造成unstable的情形，因此此排序法為stable。

* #### In place[O]
從程式碼第2、3行可得知，stooge sort在做排序時，在第3行進行exchage時，多使用一個變數的儲存空間$O(1)$，且因為有使用到遞迴所以還有額外stack的空間$O(logn)$，空間複雜度為$O(logn)$，但因為大小$O(logn)$可忽略不計，因此此排序法為In place。

#### 【B小題】
$\text{For the base case, let }n = 2$, 從程式碼的第七八行可得知，程式會去判斷裡面兩個的值是否已被排序了，並且會在第二個if return 正確的值，因此可確定 $n = 2$ 時，$\text{Stooge-Sort}$ 成立。
$\text{Assume that Stooge-Sort correctly sorts an input array }A[1\cdots k],
\text{ where }k = length[A]\ and\ 1 \le k < n.\\
Let\ A[1\cdots n] \text{ be an input array of size } n = length[A].$
$\text{By the induction hypothesis,}$
從程式碼第6行可得知，k值大約等於$\frac 13length[A]$，因此從程式碼7-9行可得知，$\text{Stooge-Sort}$會先排序$A[1\cdots\frac 23n]$(前$\frac 13$會小於後$\frac 23$)，再排序$A[\frac 13n\cdots n]$(以此類推)，因此基本上可以確定數字較大的都會被排序到A的後部分，最後再將前$\frac 23$部分，也就是數字小的部分在第9行再做一次排序，由於程式會不斷地遞迴，持續將切割的三等份做排序，當recurison做到sort的array的長度$\le k$ 時，由前面假設可知$A[1\cdots k]$將會被排序好，因此最後$\text{Stooge-Sort}$將可以排序完$A[1\cdots n]$。
$\text{Therefore, by Mathematical Induction,}\\
\text{we know that STOOGE-SORT(A, 1, length[A]) correctly sort the input array } A[1\cdots n].$

#### 【C小題】
從A、B小題可得知，$T(n) = 3T(\frac 23n)+\Theta(1)$，因為每做一次sort，Algorithm 都會再將問題分成$3$塊，每塊的大小為$\frac 23 n$，exchange和比較的時間複雜度為$O(1).$
$\text{By Master Theorem,}\\
a=3,\ b=\frac 32,\ c=0,\ f(n) = 1 = n^0$
$\because\ \log_{b}{a} = \log_{\frac 32}{3} > 1\ and\ f(n) = n^{log_{\frac 32}{1}}$
$\therefore\ f(n) = O(n^{\displaystyle\log_{\frac 32}{3-\epsilon}}),\ \epsilon > 0\ \Rightarrow\ T(n)= \Theta(n^{\log_{\frac 32}{3}})_\#$

#### 【D小題】
當worst-case發生時，各個排序法的時間複雜度如下
* Insertion sort $= O(n^2)$(最差形況為從頭Insert到尾)
* Merge sort $= O(n\log n)$(不管任何情形時間複雜度都相同)
* Heapsort $= O(n\log n)$(不管任何情形時間複雜度都相同)
* Quicksort $= O(n^2)$(最差的情況是當需要比較的值都在最邊緣)
* Stooge sort $= O(n^{\log_{\frac 32}{3}}) = \omega(n^2)$(由c小題可知)
$\because\ \log_{\frac 32}{3} \cong 2.7 > 2$
$\therefore\;$ The time complexity of Stooge sort is the worst case of all above, and I think professor still deserved venture, since he created a special sorting algorithm we haven't thought.$_\#$

### Q4
> - [name=LXS]


將$n\times n$矩陣補零至最近的$2^k\times 2^k$矩陣，透過Strassen演算法，時間複雜度仍是$O(n^{\lg{7}})$

【證明】
設 $2^{k-1}<n<2^k=N$，已知 $2^{k-1}<n\rightarrow N<2n$
$\therefore\Theta((2n)^{\lg7})=\Theta(2^{\lg7}\times n^{\lg7})\in\Theta(n^{lg7})\approx\Theta(n^{2.807})$

最後消去0項，遍歷一次矩陣需要$O(n^2)時間$

<!-- 發現我這題好像最水(；・∀・) -->
<!-- 您可以一起解第七題XD -->
<!-- 第七題我來就好ㄌ，好水 -->
### Q5
> - [name=Mark]


$T_{1}(n)=132464(\frac{n}{68})+\Theta(n^2) \implies T(n)=\Theta(n^{lg_{68}132464}) \cong O(n^{2.795128}) \quad (By \; Master \;Therom)$
$T_{2}(n)=143640(\frac{n}{70})+\Theta(n^2) \implies T(n)=\Theta(n^{lg_{70}143640}) \cong O(n^{2.795123})$
$T_{3}(n)=155424(\frac{n}{72})+\Theta(n^2) \implies T(n)=\Theta(n^{lg_{72}155424}) \cong O(n^{2.795147})$
$\because T_2(n)\cong O(n^{2.795123}) \; has \; the \; best \; asymptotic \; running \; time, \; which \; is \; 70 \cdot 70 \; using \; 143640.$
$\therefore O(n^{2.795123}) < O(n^{2.81}) \; The \; algorithm \; runs \; faster \; than \; Strassen's \; Algorithm.$
### Q6
> - [name=Chung]


$\text{Let A is kn×n matrix and B is n×kn matrix}\\
A=\left[
\begin{array}{}
A_1\\
A_2\\
...\\
A_k\\
\end{array}
\right]\\
and\\
B=\left[
\begin{array}{}
B_1 & ... & B_k\\
\end{array}
\right]\\
\text{Where each Ai and Bi is a n×n matrix.}\\
\text{Hence, A×B is a kn×kn matrix equal to}\\
\left[
\begin{array}{}
A_1B_1 & ...& A_1B_k\\
& ...&\\
& ...&\\
A_kB_1 & ...& A_kB_k\\
\end{array}
\right]\\
\because\text{(kn×n)(n×kn) produces a kn×kn matrix.}\\
\text{This produces }k^2\text{ multiplications of n×n matrices}\\
\text{And, by Strassen's Algorithm,}\
T(n×n,n×n)=\Theta(n^{\lg_{7}})\\
\therefore\;
T(kn×n,n×kn)=\Theta({k^2}{n^{\lg_{7}}})
.$

#### 【Reversed Order】
$\text{Let A is n×kn matrix and B is kn×n matrix}\\
A=\left[
\begin{array}{}
A_1 & A_2 &...&A_k\\
\end{array}
\right]\\
and\\
B=\left[
\begin{array}{}
B_1 \\
B_2 \\
... \\
B_k\\
\end{array}
\right]\\
\text{Hence, A×B is a n×n matrix equal to}\\
\left[
\begin{array}{}
A_1B_1 + A_2B_2 + ... + A_kB_k\\
\end{array}
\right]\\
\because\text{(n×kn)(kn×n) produces a n×n matrix.}\\
\text{This produces k multiplications of n×n matrices and k−1 additions}\\
T(n×kn,kn×n)=kT(n×n)+O(k)\\
\therefore\;
T(n×kn,kn×n)=k×{n^{\lg_{7}}}+O(k)=k×{n^{\lg_{7}}}=\Theta(kn^{\lg_{7}})\
.$

### Q7
> - [name=Mark]
<!-- 早上不用上經濟，起床寫 -->

#### 【A小題】
[Young Tableau Usage](https://oi-wiki.org/math/young-tableau/)
$\begin{bmatrix}
2 & 4 & 9 & \infty \\
3 & 8 & 16 & \infty \\
5 & 14 & \infty & \infty \\
12 & \infty & \infty & \infty
\end{bmatrix}$
#### 【B小題】
$\text{Both is true,}$
$\because according \; Young \; Tableau \; Y[m,1] \leq Y[1,n] \leq Y[m,n]$
$\therefore Y[1,1]=\infty \implies \text{all elements is }\infty \implies \text{the tableau is empty}$
$\therefore Y[m,n]< \infty \implies Y[1,1]<\infty \implies \text{all elements existed}$
<!-- 靠腰不小心被我刪掉了 -->
#### 【C小題】
$After \;$ `Extract-Min` $Y[1,1] \text { would be replace with }\infty, \text{we should restore it}$
$\implies \text{find the minium put into Y[1,1] & modify it to be Young Tableau}$
$\text{The worst case is the tableau is full}\implies modify \; \infty \text{ to Y[m,n]}$
$\text{It would exchange for m+n times.}$
$T(p)=O(m+n)=T(p-1)+O(1)=T(p-2)+O(1)+O(1)=...$
$\implies T(p)=O(p)$

Extract_Min(Y) 
    x=Y [1, 1] 
    Y[1, 1]=∞ 
    Min_Youngify(Y, 1, 1) 
    return x 
        
Min_Youngify(Y, i, j) 
    min_i = i 
    min_j = j 
    if i + 1 ≤ m & Y[i, j] > Y[i + 1, j] 
        then min_i = i + 1
    if j + 1 ≤ n & Y[i, j] > Y[i, j + 1] 
        then min_j = j + 1 
    if min_i != i | min_j != j
        if Y[min_i, j] >= Y[i, min_j]
            then min_i = i
        else
            then min_j = j
        SWAP(Y[i, j], Y[min_i, min_j])
        Min_Youngify(Y, min_i, min_j)

#### 【D小題】
同C小題做法，改成將要插入的元素放置Y[m,n]，反著排序回來
Time Complexity $O(m+n)$

Insert(Y, k)
    Y[m,n] = k
    Max_Youngify(Y, m, n)
Max_Youngify(Y, i, j)
    max_i = i
    max_j = j
    if i − 1 ≥ 1 & Y[i, j] < Y [i − 1, j] 
        then max_i = i − 1
    if j − 1 ≥ 1 & Y [i, j] < Y [i, j − 1] 
        then max_j = j − 1 
    if max_i != i | max_j != j 
        if Y[max_i, j] <= Y[i, max_j]
            then max_i = i
        else
            then max_j = j
        then SWAP(Y[i, j], Y[max_i, max_j]) 
        Max_Youngify(Y, max_i, max_j)

#### 【E小題】
##### 想法
要一個NxN的方陣將元素一一`Insert`進去，再透過`Extract_Min`一一取出即可完成`Sort`
跟之前透過`MinHeap`實作`Priorty Queue`一樣
##### 蘇都扣

Sort(Target)
    for(i = 0; i < n^2; i++)
        Insert(Y, Target[i])
    for(i = 0; i < n^2; i++)
        sorted_output[i] = Extract_Min(Y)

##### 複雜度
$Insert() = O(n+n) \cdot n^2 \implies O(n^3)$
$\text{Extract_Min()} = O(n+n) \cdot n^2 \implies O(n^3)$
$\therefore Time \; Complexity = O(n^3)$

#### 【F小題】
##### 想法
將Target放在Y[n,1]，比Target大、Target往上，比Target小、Target往右，直到碰到Y[1,m]都沒找到，搜尋結束。
##### 蘇都扣

Search(Target)
    position = Y[n,1]
    while(position != Y[1,m])
        COMPARE(Target, position)
        if(find) break
        if(bigger) position.x++  //if target is larger
        if(smaller) position.y--

##### 複雜度
Worst case為都沒找到，Target共走過m+n次(一路向右、向上)
$\therefore O(m+n)$