# ADA Handwriting Assignment 1

## Problem 5
### (1)
#### (a)

False
如果 f(n) 比 g(n) 高次，則 f(n)+g(n) = O(f(n)) $\neq$ O(g(n))
ex. f(n) = $n^{2}$, g(n) = n, O(min(f(n),g(n)) = O(n) $\neq$ f(n)+g(n)。

#### (b)
True
#### \(c\)
True
#### (d)
False
設$f(n) = 2^{n} f(n/2) = 2^{n/2} = \sqrt{2}^{n}$
$2^{n} \neq \Theta(\sqrt{2}^{n})$

#### (e)
False
$\Omega$(x) = y 表示 x次數 $\leq$ y次數
$log_{2}(n!) = lgn+lg(n-1)+......+lg1 <= n(lgn+lg1)/2 = nlgn/2$
Because $nlgn/2 < n^{2}$ $\rightarrow$ $\Omega(n^2) \neq log_{2}(n!)$

### (2)

#### (a)

Use master theorem
Because $108n = O(n^{log_{3}6})$
we can know $T(n) = \theta(n^{log_{3}6})$

#### (b)

$T(n) = T(n/3)+T(n/4)+T(n/12)+24n \leq cn(1/3+1/4+1/12)+24n = 2cn/3+24n \leq cn$
$c \geq 2c/3+24 \rightarrow c \geq 36$
$T(n) \geq dn(1/3+1/4+1/12)+24n = 2dn/3+24n \geq dn$
$d \leq 2d/3+24 \rightarrow d \leq 36$
$cn \geq T(n) \geq dn \Rightarrow \Theta(T(n)) = n$

#### \(c\)

設T(n) = nS(n)
$nS(n) = \sqrt{n}*\sqrt{n}S(\sqrt{n})+2nlgn = nS(\sqrt{n})+2nlgn$
$S(n) = S(\sqrt{n})+2lgn = S(S(n^{1/4})+2*(1/2)lgn)+2lgn = ......$
$\Rightarrow \Theta(2lgn(1+1/2+1/4+......)) = \Theta(2lgn*2) = \Theta(n)$

#### (d)

$T(n) = 2T(n/2)+4n/lgn = 2(2T(n/4)+2n/lg(n/2))+4n/lgn = ......$
$\Rightarrow \Theta(4n/lgn+2*2n/lg(n/2)+4*n/lg(n/4)+......)$
$\Rightarrow \Theta(4n(1/lgn+1/(lgn-1)+1/(lgn-2)+....+1))$
$= \Theta(4nln(lgn)) = \Theta(nln(lgn))$

## Problem 6

### (1)

Merge(left,right):
    if left == right:
        return;
    mid = (left+right)/2
    Merge(left,mid);
    Merge(mid+,right);
    left_ptr = mid;
    right_ptr = right;
    while left_ptr >= left:
        while array[right_ptr] > array[left_ptr]:
            right_ptr--;
        pair += right_ptr-mid
        left_ptr--;
    return;

### (2)

The while loop in Merge() visits all points between left and right, so it's O(n).
$T(n) = 2T(n/2)+O(n)$
by recursion tree , we can know that $T(N) = O(NlgN)$.

### (3)

因為bubble sort的交換發生的時候，條件為index_i < index_j 且 value_i > value_j，剛好是inversion的條件，因此當bubble sort完S，就能找出所有符合題目要求的inversion。

### (4)

利用第一小題的方法，我們可以在O(NlogN)時間內找到所有horizontal lines的數量，且因為第三小題，我們可以得知其答案與bubble sort得出的解答相同，bubble sort的swap就是horizontal lines。

### (5)

跟第四小題一樣，我們不需要去理會當constraints<N的情形，因為無論如何我們都會找到所有horizontal lines來滿足，因此做法與第四小題相同，時間複雜度也為O(NlogN)。

## Problem 7

### (1)

只有當所有格子總數為$2^{n}$時，才會有可行解。
觀察 :
* 以兩格為一組，把所有格子分組，然後把block往同組的方向擴展。
* 以四格為一組，把所有格子分組，然後把block往同組的方向擴展。
* 以此類推

我們可以得知，當所有格子總數為$2^{n}$時，才會有可行的解。

### (2)

跟第一小題一樣，分組的時候，觀察同組的空格是在左邊或是右邊，output方向即可。

### (3)

討論所有條件:
* block length = 1 :
* 只有一種可能
* block length = 2 :
* 兩種可能
* block length = 4 :
* 4種可能
* 以此類推，總共會有1+2+....+$2^{lgn}$種可能

$\Theta(1+2+......+2^{lgn}) = \Theta(\frac{2^{lgn+1}-1}{2-1}) = \Theta(2*2^{lgn}-1) = \Theta(2n-1) = \Theta(n)$

### (4)

[000011110000000011111000000000000111100001000]
* dp[] = 0，儲存從1到i是否可以成功填充
* 第一步，找出 (包含 1 的 且 左邊界碰到全部最左邊)的區間[1,i]，dp[i] = 1 $\Rightarrow$ O(1的長度 = n1)
* 第二步，找出 (包含 1 的 且 左邊界的前一個dp[l-1]=1)的區間[l,i],dp[i] = 1 $\Rightarrow$ O(1的長度 = n2)
* 一直做下去直到 i = S.length

### (5)

### (6)

因為遍歷了所有S的點，因此時間複雜度為O(N)

## 一起討論的同學

b07902056 郭瑋喆 b07902102 吳庭維 b07902108 翁祖毅
b07902066 黃禹喆 b07902007 伍柏豪 b07902120 趙晉杰