# 113 交大資演 Part 2 參考詳解

> ==採用 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hant) 許可協議共享，轉載請註明來源，禁止任何營利使用。==
> [name=SayA] [time=Sun, Feb 4, 2024 9:33 AM] [color=#4c33af]

## 1. B-Tree of order M
- (A) ***The answer is not unique***
- trv1: level order(BFS)
- trv2: preorder(DFS, DLR)
- (B)
- \(C)
We can sort sequence of any order, and sorted sequence will be inorder of BST, so it implies inorder.
***Ans: preorder, postorder, level-order***
- (D)
- In *Horowitz*'s definition of a B-Tree, the new key *participates* in the split. So M-way Search Tree at most contains $M$ keys and $M+1$ pointers before balancing process.
- Notice that $M$ keys store in $[0, ..., M-1]$, and $M+1$ childs stroe in $[0, ..., M]$
- ***Ans:***
$$
\begin{aligned}
\text{ all keys in } & child[0] < key[0] \\
key[i-1] < \text{ all keys in } & child[i] < key[i], \forall i, 0 < i < M-1 \\
key[M-1] < \text{ all keys in } & child[M]
\end{aligned}
$$
- (E)
- B-Tree of order M have $ceil(M/2)$-node to $M$-node, and a M-node has $M-1$ keys after *balancing*.
- For example, there are 2-node, 3-node, 4-node in 2-3-4 Tree (B-Tree of order 4).
- ***Ans: $ceil(M/2) - 1$***

## 2. Bellman-Ford
- (A)
- (1) $\text{INF}$
- (2) $0$
- (3) $<$
- (4) $<$
- (B) $-4$
- \(C) $-1$
- (D) $0$

| | A | B | C | D |
|---------|-----|-----|-----|-----|
| initial | INF | INF | INF | INF |
| round 1 | 0 | -1 | -4 | 3 |
| round 2 | 0 | -1 | -4 | 0 |
| round 3 | 0 | -1 | -4 | 0 |

## 3. Longest Palindrome Bimodal Subsequence Problem (LPBS)

- 長度為 $m$ 的LPBS，其 `pivot` 為$a_k, k=\frac{(m+1)}{2}$。也就是以$a_k$為中點，前半段是Increasing，後半段是Decreasing。
- 因此求以 $i$ 為pivot的LPBS，可以將問題分隔成以$a_i$結尾的LIS，和以$a_i$開始的LDS兩個部分。
- 以 $a_i$結尾的LIS即為 $T(i)$ ，令以 $a_i$開始的LDS為 $T_2(i)$：
$$
T_2(i) = \begin{cases}
0 &\text{if } i > n \\
{\max_{
\begin{subarray}{}
i < j \leq n+1 \\ a_i > a_j
\end{subarray}}} (T_i(j) + 1) &\text{if } 1 \leq i \leq n \\
\end{cases}
$$
- 註：題目的 $T(i)$ 中implies $a_0$ 為 $-\inf$，我這裡定義的 $T_2(i)$ 也假設 $a_{n+1}$ 為$-\inf$
- 因為兩段長度要相同，且 $a_i$ 重疊於兩段，故所求為 **$PV(i) = min(T(i), T_2(i)) \times 2 -1$**

## 4. Binary Search

- (A) 由`勘根定理`證存在性
- 令 $f(r) = \Sigma_{i=1}^{k} \frac{a_i}{b_i^r}$ ， $g(r) = f(r) - 1$
- 當 $r \rightarrow -\inf$ 時， $f(r) \rightarrow \inf$ ， $g(x) > 0$
- 當 $r \rightarrow \inf$ 時， $f(r) \rightarrow 0$ ， $g(x) < 0$
- 由勘根定理知 $g(r)$ 有實數解，故 $\exists r_0 \rightarrow f(r_0) = 1$
- (B) 證明單調性，可二分
$$
\begin{aligned}
& \because a_i > 0, b_i > 1, \forall i, 1 \leq i \leq k \\
& \therefore f(r) > 0 \\
& \text{As r increases, f(r) decreases} \\
& \text{As r decreases, f(r) increases}
\end{aligned}
$$
- 所以 $f(r)$ 為嚴格遞減函數，具有單調性
- 因此可以透過***Binary Seach***縮小答案範圍，when $f(r) - 1 < 10^{-6}$, return r

<style> :root{
--markup-code: #003060;
--strong-code: #000079;
--strong-bg: #000079;

}
.markdown-body code,
.markdown-body tt {
background-color: #FFCBB3;
color: var(--strong-code)
}
.markdown-body strong{
font-weight:700;
background-color: yellow; /* 設置背景顏色為黃色 */
padding: 3px; /* 添加一些內邊距以增加可讀性 */
}
}
.markdown-body code{
color: var(--markup-code)!important
}
</style>