---
# System prepended metadata

title: HW-5
tags: [AA-Book]

---

# HW-5
### 1
每次 Increment 的花費變成 3 元，支付一元將 0 變成 1，保留一元(credit) 供未來 1 變成 0 的時候使用，保留另一元當作清空成 0 的費用。另外利用指標紀錄最高位的 1 的所在位置，當要計數到 2^k 時指標就會前進加一。所以一次 Increment 的 Amortized Cost 為常數時間。當要 RESET 時，從最高位指標的所在處往最低位走，當遇到 1 時就拿之前預付的一元來支付，所以一次 RESET 的 Amortized Cost 就為 0。故當有 n 次 Increment 和 Reset 的操作時就只要花 O(n)。

### 2
![image](https://hackmd.io/_uploads/BJrB2kkI6.png)

### 3
> 老師 HINT : 想像你要寫程式，需要定義好資料結構，以及簡單的虛擬碼設計如何實作 INSERT 和 DELETE-LARGER-HALF

* 資料結構可設計成 Dynamic Table (看上課講義)
* Insert(S, x) 直接把 x 放入陣列最後面，儲存 2 個 Token，每次插入為常數時間
* DELETE-LARGER-HALF(S) : 利用中位數演算法(median-of-midian) 找出中位數，花費時間為 O(|S|)，所以每個元素各支付一個 Token。接著刪除大於中位數的元素，而這些被刪除的元素支付 Token 給剩下一半的元素，所以剩下 $\frac{|S|}{2}$ 個元素還是維持每個元素有 2 個 Token，故攤提時間為常數時間

因此 m 次 Insertion 和 DELETE-LARGER-HALF 所花費的攤提時間為常數時間。

### 4
$\Phi (T) = |2 \cdot T.num - T.size|$

Case 1: 當 load factor 還沒降到 $\frac{1}{3}$ 以下，Table 還不會縮小，所以 $size_{i} = size_{i-1}$
$$ \begin{split} 
\hat c_i &= c_i + {\Phi}_i - {\Phi}_{i-1} \\
         &= 1 + |2 \cdot {num}_i - {size}_i| - |2 \cdot {num}_{i-1} - {size}_{i-1}| \\
         &= 1 + |2 \cdot {num}_i - {size}_i| - |2 \cdot ({num}_{i} + 1) - {size}_{i-1}| \\
         &\le 1 + |(2 \cdot {num}_i - {size}_i) - (2 \cdot ({num}_{i} + 1) - {size}_{i-1})|\ by\ Reverse\ Triangle\ Inequality \\
         &= 1 + |{size}_{i-1} - {size}_{i} - 2| \\
         &= 1 + |-2| = 3
\end{split}$$

Case 2: 當 load factor 來到 $\frac{1}{3}$ 以下，縮小 Table 大小 $\frac{2}{3}$ 倍，所以 $size_{i} = \frac{2}{3} \cdot size_{i-1}$ 且 $size_{i-1} = 3\cdot num_{i-1}$。
$$
\begin{split}
\hat c_i &= c_i + {\Phi}_i - {\Phi}_{i-1} \\
         &= (1 + {num}_i) + |2 \cdot {num}_i - {size}_i| - |2 \cdot {num}_{i-1} - {size}_{i-1}| \\
         &= (1 + {num}_i) + |2 \cdot {num}_i - {size}_i| - |2 \cdot ({num}_{i} + 1) - {size}_{i-1}|  \\
         &= 1 + {num}_i + 2 - (1 + {num}_i) = 2
\end{split}
$$
$$
\begin{split}
|2 \cdot {num}_i - {size}_i| &= |2 \cdot({num}_{i-1} - 1) - \frac{2}{3} \cdot size_{i-1}| \\
&= |2\cdot {num}_{i-1} - 2 - \frac{2}{3} \cdot 3\cdot num_{i-1}| \\
&= |-2| = 2
\end{split}
$$

$$
\begin{split}
|2 \cdot ({num}_{i} + 1) - {size}_{i-1}| &= |2 \cdot {num}_i + 2 - 3 \cdot {num}_{i-1}| \\
&= |2 \cdot {num}_i + 2 - 3 \cdot({num}_i + 1)| \\
&= |2 \cdot {num}_i + 2 - 3 \cdot {num}_i - 3| \\
&= |-(1 + {num}_i)| \\
&= 1 + {num}_i
\end{split}
$$
故 TABLE-DELETE 的攤提時間為常數時間。

### 5
![image](https://hackmd.io/_uploads/rkIo73zLT.png)
![image](https://hackmd.io/_uploads/rkgEQhGI6.png)
![image](https://hackmd.io/_uploads/Bklh47nGIa.png)
![image](https://hackmd.io/_uploads/BkxYX3zIa.png)
![image](https://hackmd.io/_uploads/HyrwmhGUp.png)
