# 台大電信丙
## 108
> False
> Dijkstra不行用在有negative weight edge的圖，就算圖是DAG也不行，因為在Dijkstra中，不會對已經被extract min掉的vertex再次進行relax，這也就是Dijkstra的正確性需要edge都是正的的原因。

> F
> 

> FT
> https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

> C
> 印度神法 https://www.youtube.com/watch?v=OynWkEj0S-s&t=784s

> A
> Binomial heap insert amortized $\theta(1)$
> 
> 

> A
> $2019 = 1024 + 512 + 256 + 128 + 64 + 32 + 2 + 1$
> $2019 = 2^{10} + 2^{9} + 2^{8} + 2^{7} + 2^{6} + 2^{5} + 2^{1} + 2^{0}$
> degree k的binomial **tree** root下 child的degree為 k-1, k-2, ..., 0
> degree 5的binomial **tree** root下有 1個 node degree = 5
> degree 6的binomial **tree** root下有 1個 node degree = 5
> degree 7的binomial **tree** root下有 degree 6, 5 的child，總共有1 + 1 = 2個node degree = 5
> degree 8的binomial **tree** root下有 degree 7, 6, 5 的child，總共有1 + 1 + 2 = 4個node degree = 5
> 以此類推，degree 10的binomial **heap**會有 1 + 1 + 2 + 4 + 8 + 16 = 32個node degree = 5

---
> D
> $F_0 = 0, F_1 = 1, F_2 = 2, ..., F_{13} = 233, F_{14} = 377$
> $F_{13} = 233 < 256 < F_{14} = 377$ 所以 degree即是13 - 2 = 11

> C
> $F_{6+2} = F_8 = 21$

* 這兩題在問的是同一件事情，就是給定一個degree = k的Fibonacci heap，求其最少node數？
* 以下為推導過程

> 
> 

> A
> Fibonacci one decrease key amortized $\theta(1)$

> D
> Fibonacci one decrease key worst case $O(n)$

> C
> degree 6 node 的child degree 為 0, 0, 1, 2, 3, 4, 5，至多失去一個child，所以child degree 為 0, 0, 1, 2, 3, 4。

> B

> C
> with weighted union and path compression, one find operation worst case?
> cost of find operation is bounded by height, with weighted union it is $O(logn)$

## 109
> A
> 計算？
> Binomial insert amortized $\theta(1)$

> A
> 
> Binomial insert amortized $\theta(1)$

> C

> C
> 

> B
> height 最少的情況發生於Complete binary tree
> Complete binary tree height k 有 $2^{k+1} -1$個 node
> $2^{6+1} -1 = 63 < 100$
> $2^{7+1} -1 = 127 > 100$
> so AVL tree of 100 nodes has height **at least** 6

> D
> $F_{k}$ is the $k^{th}$ fibonacci number
> AVL tree h = 0, #node = 1 = $F_2$ - 1
> AVL tree h = 1, #node = 2 = $F_3$ - 1
> AVL tree h = k, #node = 1 = $F_{k+2}$ - 1
> AVL tree h = 8, #node = 1 = $F_{8+2} - 1 = 89 - 1 = 88$
> AVL tree h = 9, #node = 1 = $F_{9+2} - 1 = 144 - 1 = 143$
> $88 < 100 < 143$
> so AVL tree of 100 nodes has height **at most** 8

> A
> $4^{3+1} - 1 = 255$
> 

> E
> $2^{7+1} - 1 = 255$

> D
> 2020 = 1024 + 512 + 256 + 128 + 64 + 32 + 4

> C
> Fibonacci delete-min amortized $O(logn)$

> ABCE
> 
> 

> AB

--


---
* Fibonacci heap專題
> Find-min 若有維持min pointer --> O(1)
> Union若是用doubly linked list串起來就是O(1)
> find-min O(n) if you don't maintain a min-pointer