# HW-2

### 1
> Rank the following functions by order of growth; that is, $f(n)$ should come before $g(n)$ in your list if and only if $f(n) = O(g(n))$. Partition your list into equivalence classes such that $f(n)$ and $g(n)$ are in the same class if and only if $f(n) = \theta(g(n))$.

分解下列式子

$$
\begin{align}
\text{(lg n)!} &= O({lgn}^{lgn}) \\
\text{lg}^3 n &= O(n^{0.1}) \\
2^n &= O(4^n) \\
n\text{lg}n &= O(n\log n) \\
n^3+100n^2 &= O(n^3) \\
8n+\text{lg}n &= O(n) \\
\log(\log n) &= O(\log(\log n)) \\
4^{n/4} &= 2^{2n/4} = 2^{n/2} = O(2^n) \\
n^{0.1} &= O(n) \\
n^{\log(\log n)} &= \theta({lgn}^{lgn})\\
n^{5/2} &= O(n^3) \\
n! &= O(n!) \\
5^{\log n} &= n^{\log 5} = O(n^3) \\
4^n &= O(n!) \\
\log(n!) &= \log(n(n-1)...1) = \log n + ... + \log1= O(n\log n) \\
n^n &= O(n^n)\\
(\log n)^{\log n} &= \theta(n^{\log(\log n)}) \\
n^{1/\log n} &=(2^{\log n})^{1/\log n} =2=O(c) \\
5n^2+7n &= O(n^2) \\
3^{n/3} &= O(4^{n/4})
\end{align}
$$

時間複雜度由小到大排序&分類如下，括號起來的為同量級
$$
n^{1/lgn} < lg(lgn) < lg^3n < n^{0.1} < 8n + lgn \\
< [nlgn, lg(n!)] < 5n^2+7n < n^{5/2} < n^3+100n^2 < 5^{lg n}<(lgn)! \\
< [(lgn)^{lg n}, n^{lg(lg n)}]< 3^{n/3} < 4^{n/4} < 2^n < 4^n < n! < n^n
$$

---
### 2
> Give asymptotic tight bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for $n \leq 2$.

(a) $T(n)=n+\sum_{k=1}^{n-1} [T(k)+T(n-k)]$
$$
T(n)=n+\sum_{k=1}^{n-1} [T(k)+T(n-k)] \\
T(n-1)=n-1+\sum_{k=1}^{n-2} [T(k)+T(n-k)] \\
T(n) - T(n - 1) = 1 + T(n - 1) + T(1) \\
\Rightarrow T(n) = 2T(n - 1) + T(1) + 1 = 2T(n - 1) + c, \ c\ is\ constant \\
\begin{split}
\Rightarrow T(n) &= 2[2T(n-2) + c] + c \\
&= 2^2T(n-2) + c(1 + 2) \\
&= 2^2[2T(n-3) + c] + c(1 + 2) \\
&= 2^3T(n-3) + c(1 + 2 + 2^2) \\
&= 2^kT(n-k) + c(1 + 2 + ... + 2^{k-1}),\ let\ n - k = 1\\
&= 2^{n-1}T(1) + c(1 + 2 + ... + 2^{n-2}) \\
&= 2^{n-1}T(1) + c\frac{1 - 2^{n - 1}}{1 - 2} \\
&= 2^{n-1}T(1) + c(2^{n - 1} - 1) \in \theta(2^n)
\end{split}
$$

(b) $T(n) = 2T(\frac{n}{2}) + \frac{n}{logn}$
$$
\begin{split}
T(n) &= 2T(\frac{n}{2}) + \frac{n}{logn} \\
&= 4T(\frac{n}{4}) + \frac{n}{logn} +2\times\frac{\frac{n}{2}}{log\frac{n}{2}}\\
&=2^{\text{log}n}T(1)+\sum_{k=1}^{\text{log}n} \frac{n}{k} \\
&= n\times c +n\times\sum_{k=1}^{\text{log}n} \frac{1}{k} \in O(nlog(logn))\ 因為 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} \in O(log n)
\end{split}
$$

\(c\) $T(n) = 2T(\frac{n}{4})+\sqrt{n}$

From the Master theorem $T(n)=aT(\frac{n}{b})+f(n)$, we have $a=2, b=4$. The critical exponent $c_{crit}=\log_b a=\log_42=\frac{1}{2}$.

Since $f(n)=\sqrt{n}=n^{1/2}=\Theta(n^{1/2})=\Theta(n^{\log_ba})$, asymptotic tight bounds for $T(n)=\Theta(n^{log_ba}\log n)=\Theta(n^{1/2}\log n)$. (using case 2 of the Master theorem)

(d) $T(n) = T(\frac{n}{2})+T(\sqrt{n})+n$
因為當$n\geq4$時，$\frac{n}{2}\geq\sqrt{n}$，因此我們選取$T(n) = T(\frac{n}{2})+T(\sqrt{n})+n\leq 2T(\frac{n}{2})+n$作為tight bound。
$$
\begin{split}
T(n) &\leq 2T(\frac{n}{2})+n\\
&=nT(1)+n\text{log}n\in\theta(n\text{log}n)\\
T(n) &\geq T(\frac{n}{2})+n\\
&=\text{log}nT(1)+n\text{log}n\in\theta(n\text{log}n)
\end{split}
$$
因此$T(n)\in \theta(n\text{log}n)$

(e) $T(n) = T(\frac{n}{2})+\sqrt{n}$
$$
\begin{split}
T(n) &= T(\frac{n}{2})+\sqrt{n}\\
&= T(1)+\sum_{k=1}^{\text{log}n}2^{\frac{k}{2}}< T(1)+2\sum_{k=1}^{\lceil\frac{\text{log}n}{2}\rceil}2^k
&=T(1)+2\sqrt{n}\in\theta(\sqrt{n})
\end{split}
$$

**[過程]**

(f) $T(n)=5T(\frac{n}{2}) + (n\text{lgn})^2$
$$
\begin{split}
T(n)&=5T(\frac{n}{2}) + (n\text{lgn})^2\\
&=5^{\text{log}n}T(1)+\sum_{k=1}^{\text{log}n}(2^k\times k)^2\\
&\leq n^{\text{log}5}T(1)+n^2(\text{log}n)^3\in\theta(n^{\text{log}5})
\end{split}
$$

(g) $T(n)=4T(\frac{n}{2}) + n^2\text{lg}^kn$ where $k$ is an integral constant.
$$
\begin{split}
T(n)&=4T(\frac{n}{2}) + n^2\text{lg}^kn\\
&=n^2T(1)+n^2\text{lg}^kn\in\theta(n^2\text{lg}^kn)
\end{split}
$$

若 k = 0，則 $T(n) = 4T(\frac{n}{2}) + n^2 \in \theta(n^2log^{0+1}n)$
若 k > 0，則 $T(n) = 4T(\frac{n}{2}) + n^2log^kn \in \theta(n^2log^kn)$
若 k < 0，則 令 k = -t, t > 0$$
\begin{split}
T(n) &= 4T(\frac{n}{2}) + n^2log^{-t}n \\
&= 4^iT(\frac{n}{2^i}) + n^2(\frac{1}{log^t(\frac{n}{2^{i - 1}})} + ... + \frac{1}{log^t(\frac{n}{2})} + \frac{1}{log^tn}),\ let\ n = 2^i \\
&=n^2T(1) + n^2(1 + \frac{1}{2^t} + \frac{1}{3^t} + ... + \frac{1}{{log}^tn}) \in O(n^2log^{k+1}n) \\
其中，\sum_{i = 1}^{logn} \frac{1}{i^t} \leq \int_{1}^{logn} \frac{1}{x^t}dx &= \frac{{(logn)}^{1-t}-1}{1 - t} \in \theta(log^{1-t}n) = \Theta(log^{k+1}n) \\
\end{split}
$$
綜合以上，若 k > 0，則 $T(n) \in O(n^2log^kn)$；若 k ≤ 0，則 $T(n) \in O(n^2log^{k+1}n)$

(h) $T(n)=T(pn) + T(qn)+\theta(n)$, $p <1$,$q<1$, and $p+q<1$
不失一般性，假設$p\leq q$，因此$2T(pn) + \theta(n)\leq T(n)\leq 2T(qn) + \theta(n)$。再令$\text{log}_{\frac{1}{p}}n=a$
$$
\begin{split}
2T(pn) + \theta(n)&=2^aT(1)+\sum_{k=0}^{a-1}\theta(p^kn)\\
&\geq nT(1)+\sum_{k=0}^{a-1}c\times p^kn\\
&= nT(1)+cn\times \frac{1-p^a}{1-p}\\
&= nT(1)+c\times \frac{n-1}{1-p}\in \theta(n)
\end{split}
$$
當$f(x)\in\theta(p^kn)$時，則有$c_k$與$d_k$使得$c_kp^kn\leq f(x)\leq d_kp^kn$
這裡的$c$便是指$\text{min}\lbrace c_1,...c_a\rbrace$，而同理:
$$
\begin{split}
2T(qn) + \theta(n)\leq nT(1)+d\times \frac{n-1}{1-q}\in \theta(n)\\
\end{split}
$$
因此$T(n)\in\theta(n)$

(i) $T(n)=2T(\frac{n}{2}) + n\text{lg}\text{lg}n$
令$\text{log}n=a$
$$
\begin{split}
T(n)&=2T(\frac{n}{2}) + n\text{lg}a\\
&= nT(1) + \sum_{k=1}^{a}2^k\text{log}k\\
&\leq nT(1) + 2^{a+1}\text{log}a\\
&= nT(1) + 2n\times \text{loglog}n
\in O(n{\text{log}\text{log}n})
\end{split}
$$

(j) $T(n)=T(n-1) + n^k\text{lg}n$
$$
\begin{split}
T(n)&=T(n-1) + n^k\text{lg}n \\
&= T(1)+ \sum_{i=2}^{n}i^k\text{lg}i \\
&= O(n^{k+1}\text{lg}n) \\
&= \Omega(n^{k+1}\text{lg}n) \\
&= \Theta(n^{k+1}\text{lg}n) \\
\end{split}
$$
### 3

**[演算法正確性證明]**

使用monotonic decreasing stack將數列左邊且小的數字移除，剩餘的數字為最大，即如果$x_{i+1}>x_i$，則須移除$x_i$

考慮任一數列如下
$$
\begin{align}
x_1,x_2,...,x_{i-1},x_i,x_{i+1},...,x_{j-1},x_j, ..., x_n
\end{align}
$$

令$S_1$為移除$x_i$後的數列，$S_2$為移除$x_j$後的數列
$$
\begin{align}
S_1 = x_1,x_2,...,x_{i-1},x_{i+1},...,x_{j-1},x_j, ..., x_n \\
S_2 = x_1,x_2,...,x_{i-1},x_i,x_{i+1},...,x_{j-1}, ..., x_n
\end{align}
$$

由於$x_{i+1}$與$x_i$在同一個位置，探討兩者大小對於數列之間關係。

如果$x_{i+1} > x_i$，則$S_1>S_2$。

**[遞迴式]**
$A(i)$: the last index of the resulting number after removing k digits from $x[1,i]$.

$f(x[i,j])$: the index of $max(x[i,j])$.

$A(i)=f(x[A(i-1)+1,i])$
Initial: $A(k)=1 \Rightarrow$ 起始從k+1開始算

### 4

### 5
Divide and Couquer 可線性
https://personal.utdallas.edu/~daescu/maxsa.pdf

### 6
> Let x1, x2, … , xn be a sequence of real numbers (not necessarily positive). Design an algorithm to find a subsequence xi , xi+1, …, xj (of consecutive elements) such that the product of the numbers in it is maximum over all subsequences of consecutive elements. The product of the empty subsequence is defined as 1.

**Recursive form:**
$P(n)$: maximum product of $x_{1:n}$
$S(n)$: maximum subsequence product of $x_{1:n}$
$S(n)=\text{max}\{S(n-1)\times x_n, x_n\}$
$P(n)=\text{max}\{S(n),P(n-1)\}$
$P(0)=S(0)=1$

**Algo:**

Input: x[1:n]
Output: i, j

Initial: i=j=sb=0
for a = 1 to n
    S(a) = max{S(a-1)*x[a], x[a]}
    if P(a-1) < S(a)
        P(a) = S(a)
    else
        P(a) = P(a-1)

以下考慮所有數字為整數

### 7


Ref: https://stackoverflow.com/a/77505644

### 8

### 9.
> Design an algoritm to solve Problem 10154 “Weights and Measures” in the ACM web site.

想法: 疊烏龜由上到下來建塔，把力量小的的烏龜放在上面，所以先按照烏龜負荷量由小到大排序。
$w$: 重量
$m$: 負荷量

$w[1,n-1]+w[n] \leq m[n] \Rightarrow m[n]-w[n] \geq w[1,n-1]$


### 10

### 11