113 交大資演 Part 2 參考詳解

採用 CC BY-NC-SA 4.0 許可協議共享，轉載請註明來源，禁止任何營利使用。
SayASun, Feb 4, 2024 9:33 AM

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{array}{rl}\text{ all keys in }& child[0]<key[0]\\ key[i-1]<\text{ all keys in }& child[i]<key[i],\mathrm{\forall }i,0<i<M-1\\ key[M-1]<\text{ all keys in }& child[M]\end{array}$$
• (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{array}{ll}0& \text{if }i>n\\ \underset{\begin{array}{}i<j\le n+1\\ a_i>a_j\end{array}}{max}(T_i(j)+1)& \text{if }1\le i\le n\end{array}$$
  • 註：題目的
    $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)={\mathrm{\Sigma }}_{i=1}^k\frac{a_i}{b_i^r}$ ，
    $g(r)=f(r)-1$
    • 當
      $r\to -inf$ 時，
      $f(r)\to inf$ ，
      $g(x)>0$
    • 當
      $r\to inf$ 時，
      $f(r)\to 0$ ，
      $g(x)<0$
  • 由勘根定理知
    $g(r)$ 有實數解，故
    $\mathrm{\exists }{r}_0\to f(r_0)=1$
• (B) 證明單調性，可二分
  
  $$\begin{array}{rl}& \because a_i>0,b_i>1,\mathrm{\forall }i,1\le i\le k\\ & \therefore f(r)>0\\ & \text{As r increases, f(r) decreases}\\ & \text{As r decreases, f(r) increases}\end{array}$$
  • 所以
    $f(r)$ 為嚴格遞減函數，具有單調性
  • 因此可以透過Binary Seach縮小答案範圍，when
    $f(r)-1<{10}^{-6}$, return r