# Intro. to Algorithm HW2
###### tags: `Intro. to Algorithm`
- [name=曾文鼎 0716023]

## 1
### a
因為 $f(n)=O\left(h(n)\right)$ ，所以 $\exists n_1>0,c_1>0$ 使得 $$\forall n>n_1, f(n)\leq c_1h(n)$$

同理 $\exists n_2>0,c_2>0$ 使得 $$\forall n>n_2, g(n)\leq c_2k(n)$$

令 $n_0=\max(n_1,n_2),c_0=c_1c_2$ 則必有 $\forall n>n_0$ 使得 $$f(n)g(n) \leq c_1c_2h(n)k(n)=c_0h(n)k(n)$$

故 $f(n)g(n)=O\left(h(n)k(n)\right)$ 。

### b
以下用羅畢達證明 $\log^8n=o(n)=O(n)$ ，並且將 $\log$ 視為 $\ln$。 $$\begin{align}\lim_{n\to\infty}\frac{\log^8 n}{n}
&= \lim_{n\to\infty}\frac{8\cdot\log^7 n}{n}
\\&= \lim_{n\to\infty}\frac{8\cdot7\cdot\log^6 n}{n}
\\&= \lim_{n\to\infty}\frac{8\cdot7\cdot6\cdot\log^5 n}{n}
\\&= \cdots
\\&= \lim_{n\to\infty}\frac{8!}{n}
\\&=0
\end{align}$$

故 $f(n)+\log^8n=O(n)+O(n)=O(n)$ 。

## 2
以下給出 pseudo code 。

function judge(A) {
    let n = A.length
    let dp3 = new Array[n+1][n+1]
    let dp5 = new Array[n+1][n+1]
    fill dp3 with 0
    fill dp5 with infinity
   
    for (s=1; s<=2*n; s++) {
        for (x=1; x<=n; x++) {
            let y = s - x
            if (y < 1 or y > n) continue;
            dp3[x][y] = max(dp3[x-1][y], dp3[x][y-1])
            dp5[x][y] = min(dp5[x-1][y], dp5[x][y-1])
            if (A[x][y] % 3 == 0) dp3[x][y]++
            if (A[x][y] % 5 == 0) dp5[x][y]++
        }
    }
    
    return dp3[n][n] > dp5[n][n]
}

* 宣告並初始化陣列 `dp3` 和 `dp5` 的複雜度是 $O(n)$ 。
* 兩個 `for` 迴圈的複雜度各是 $O(n)$ ，合計起來是 $O(n)\times O(n)=O\left(n^2\right)$ 。
* 其餘操作都是 $O(1)$ 。

故整體複雜度是 $O\left(n^2\right)$ 。

## 3
直接使用 LIS 可以做出 "LBS" (Longest Bitonic Subsequence) ，複雜度為 $O(n\log n)$ 。作法是
1. 對於所有 $1\leq i\leq n$ ，將 input 陣列的前 $i$ 項 subarray 計算 LIS 長度。複雜度 $O(n\log n)$ 。
2. 反轉 input 陣列。然後模仿步驟 1. 。複雜度 $O(n\log n)$ 。
3. 合併 1. 和 3. 的結果，得出 LBS 長度。複雜度 $O(n)$ 。

以下給出 pseudo code 。

// Queires the number of elements, which are not greater than t, in the
// given sorted_array. The complexity is O(log(n)).
function lower_bound(sorted_array, t) {
    let l = 0, r = sorted_array.length - 1
    while (l <= r) {
        let m = floor((l + r) / 2)
        if (sorted_array[m] <= t) l = m + 1
        else r = m - 1
    }
    return l
}

// Returns an array, index i of which indicates length of longest 
// increasing subsequence of subarray within given array from index 0 
// to i. E.g. if input array is [0,7,1,6,0,2,3] then [1,2,2,3,3,3,4] 
// is returned. The complexity is O(n*log(n)).
function lis(array) {
    let ret = [] // empty array
    let dp  = []
    
    for (i=0; i<array.length; i++) {       // O(n)
        let val = array[i]
        let l = lower_bound(dp, val)       // O(log(n))
        if (l == dp.length) dp.append(val)
        else dp[l] = min(dp[l], val)
        ret.append(dp.length)
    }
    
    return ret
}

// Queries length of longest bitonic subsequence within array A. The
// complexity is O(n*log(n)).
function lbs(A) {
    let p = lis(A)                   // O(n*log(n)).
    let r = reverse(lis(reverse(A))) // O(n*log(n)).
    let ret = 0;
    for (i=0; i<A.length; i++)       // O(n)
        ret = max(ret, p[i] + r[i] - 1)
    return ret
}

## 4
以下給出 pseudo code 。顯然他是 $O(n)=O\left(n^2\right)$ 。當 `for` 迴圈跑到 $i=k$ 時， $\mathrm{dp}[j]$ 表示當 set 中元素的最大值被限制為 $k$ 的條件下， $j$ 的 integer partition set 的數量。

// Queries count of distinct integer partision set.
function judge(n) {
    let dp = new Array[n+1]
    fill dp with 0
    dp[0] = 1
    for (i=1; i<=n; i++) 
        for (j=1; j<=n; j++) 
            dp[j] += dp[j-i]
    return dp[n]
}

## 5
以下給出 $O(n)$ 的演算法。

### 準備作業
* 如果 $B$ 是一個籃子，則定義 $|B|$ 為該籃子中石頭的數量。
* 準備一個籃子 $S$ ，然後把所有石頭放到 $S$ 裡。
* 定義各石頭的 CP 值為 $v_i/w_i$ 。
* 準備一個空背包，這個背包裡的石頭將是答案。其餘重定義為 $m$ 減去其已放入的石頭的總重。
* 準備一個垃圾桶，收集被棄置的石頭。

### 演算法流程
1. 若 $|S|=0$ 或背包餘重不足 $3$ ，跳到步驟 9. 。
2. 用 Quick select 找出 $S$ 裡石頭的 CP 值的中位數，令其為 $c$ 。此步驟複雜度 $O(|S|)$ 。
3. 準備四個籃子 $G$、$E_1$、$E_3$、$L$ ，依照下列規則將石頭移至這些籃子當中的其中一個。此步驟複雜度為 $O(|S|)$ 。
* CP 值大於 $c$ 的石頭移至 $G$
* CP 值等於 $c$ 且重量為 $1$、$3$ 的石頭分別移至 $E_1$、$E_3$
* CP 值小於 $c$ 的石頭移至 $L$ 。
4. 若 $G$ 的總重量為大於背包餘重，則將 $G$ 中的石頭全部移至 $S$ ，並且把其他他三個籃子裡的石頭丟進垃圾桶，然後回到步驟 1.。此步驟複雜度為 $O\left(|S|\right)$ 。
5. 將 $G$ 中的石頭全部移至背包。此步驟複雜度為 $O(|S|)$ 。
6. 在不超重的前提下，盡量將 $E_3$ 中的石頭移至背包。因為 $E_3$ 中的石頭都一樣，所以不分放入順序。此步驟複雜度為 $O(|S|)$ 。
7. 在不超重的前提下，盡量將 $E_1$ 中的石頭移至背包。因為 $E_1$ 中的石頭都一樣，所以不分放入順序。此步驟複雜度為 $O(|S|)$ 。
8. 將 $L$、$E_3$ 和 $E_1$ 中的石頭全部移至 $S$ ，然後回到步驟 1.。此步驟複雜度為 $O(|S|)$ 。
9. 若背包仍有餘重，則盡量將重量為 $1$ 且價值最大的石頭移至背包，直到背包沒有餘重、或找不到重量為 $1$ 的石頭為止。注意，這裡要搜尋的石頭不限於 $S$ 中的石頭，也包含垃圾桶裡的石頭。
10. 演算法結束。

### 複雜度計算
注意以下事實：
* 因為在步驟 4. 中，必有 $|G|\leq|S|/2$ 且 $|L|\leq|S|/2$ ，且其他步驟的複雜度皆限於 $O(|S|)$ 。所以無論後來是 $S=G$ 還是 $S=L$ ，都遵守以下遞迴關係式，其中 $f(n)$ 為本演算法的複雜度。 $$f(n)=f\left(\frac n 2\right) + O(n)$$ 根據 Master Theorem ，可以知道 $f(n)=O(n)$ 。

* 到步驟 8. 時，背包餘重至多為 $2$ ，故此步驟最多移動兩個石頭，其複雜度為 $$O(2)\cdot O(n)=O(n)$$

綜合以上，本演算法的複雜度為 $O(n)$ 。

## 6
### a
假設我有 $k=3$ 的演算法 $A$ 和陣列 $S$ ，並令 $n=|S|$ ，則我可以用以下方法判斷 element uniqueness problem 。
1. 檢查 $S_1$ 和 $S_2$ 是否相同。若是，則答案為假。此步驟複雜度 $O(1)$ 。
2. 將一個 $S_1$ 和一個 $S_2$ 放入到 $S$ 尾端。此步驟複雜度 $O(1)$ 。
3. 對 $S$ 使用演算法 $A$ 。若其有輸出值，令其為 $h$ ；若其輸出 `not found.` ，則答案為真。此步驟複雜度待定。
4. 若 $h$ 在 $S$ 中只出現一次，則答案為真；否則為假。此步驟複雜度 $O(n)$ 。

因為既成事實是 element uniqueness problem 的複雜度至低為 $\Omega(n \log n)$ ，可以斷定 $k=3$ 的演算法 $A$ 的複雜度至低為 $\Omega(n \log n)$ 。

### b
假設我有 $k=\lfloor \log n\rfloor$ 的演算法 $A$ 和陣列 $S$ ，並令 $n=|S|$ ，則我可以用以下方法判斷 element uniqueness problem 。
1. 檢查 $S$ 的首 $\lfloor \log n\rfloor -1$ 項元素是否出現重複。若是，則答案為假。就算用 naive 方法，此步驟的複雜度也頂多 $O\left(\log^2 n\right)=O(n)$ 。
3. 在 在 $S$ 尾端加入 $S$ 的首 $\lfloor \log n\rfloor -1$ 項元素各一個。此步驟時間複雜度為 $O(\log n)$ 。
5. 對 $S$ 使用演算法 $A$ 。若其有輸出值，令其為 $h$ ；若其輸出 `not found.` ，則答案為真。此步驟複雜度待定。
6. 若 $h$ 在 在 $S$ 中只出現一次，則答案為真；否則為假。此步驟複雜度 $O(n)$ 。

因為既成事實是 element uniqueness problem 的複雜度至低為 $\Omega(n \log n)$ ，可以斷定 $k=\lfloor \log n\rfloor$ 的演算法 $A$ 的複雜度至低為 $\Omega(n \log n)$ 。