# MIT midterm/Final
## T/F

> 四維用人腦不好想像，先想二維：$T(n) = T(n/2) + O(n), T(n) = O(n)$

> WTF

> WTF

> WTF

> 什麼的rotation?

> 

> substring是連在一起的，subsequence是可以分開的

> But 如果是問 insert "rotation"的cost，是 O(1)


>

> 上面例子中weight都等於 1，所以在證明greedy choice property時，用greedy choice取代原本的optimal choice後，至少一樣好，但是在weighted interval當中，greedy choice的weight可能比optimal choice的weight還低，所以greedy choice正確性就不成立了
> 

> 

> 在Worst case $O(nlogn)$的情況下，$T(n) = 2T(n/2) + n$ （不一定要完美split成兩半，只要分成any constant fraction都可以是$O(nlogn)$）
> 只需要$O(logn)$去存unsort array的start address

> randomized quicksort 是對**任何**input都有 **expected** $O(nlgn)$
> 當然可以說**某些**input在**某些時候**會有$O(n^2)$的表現
> 但是不可能 always runs in $O(n^2)$




> lightest edge 一定在 MST裡面是正確的，heaviset edge一定不在MST中嗎？不一定，例如heaviset edge為bridge

> 因為edge （u,v）只加了vertex 的weight各一半，所以最後還要再加上 $1/2 (w(u) + w(v))$ 才會是正確的shortest path weight








> $T(n) = T(n/9) + T(8n/9) + \theta (n)$
> $T(n) = \theta (nlgn)$

> True:
> 令 potential function = $\sum_{i=0}^{n} 2w_i$, $w_i$為每個node在heap中的depth
> so root 的$w_i = 0$，root的兩個child $w_i = 1$
>
> For insert:
> $\hat Ci = Ci + \Phi(Hi) - \Phi(H\text{i-1}) = Ci + 2h$, $h$為 heap depth = $O(logn)$
> $\hat Ci = O(logn) + O(logn) = O(logn)$
> For extract-min:
> $\hat Ci = Ci + \Phi(Hi) - \Phi(H\text{i-1}) = Ci + (-2h)$
> $\hat Ci = O(logn) + (-O(logn)) = O(1)$



> DP 的 sub problem tree 不需要是 rooted tree，只需要是 DAG即可

> 原本的min cut每一條edge都 + 1，可能不再是 min cut



> 3SAT is NP-Complete, 所以若 P = NP，有polynomial time algorithm
> 但是如果是 NP-hard but not in NP, 例如 halting problem，則就算 P = NP，還是沒有polynomial time algorithm
> 

> not "always"
> 就像 random quicksort runs in expected $O(nlgn)$ for **all input**, 但是還是會有**某些**input在**某次**執行時的**worst case**是 $O(n^2)$

> Approximation factor 和 reduction沒有絕對關係


> edge weight unique, MST is unique, but second lowest ST is not.
> 找second lowest ST就是移除 MST中最大edge weight，加入尚未在MST中，不會形成cycle且weight最小的edge
> 反例：

> at most k edges是 Bellman-ford的觀念
> Floyd-Warshall的核心就是DP on k, where k is intermediate vertex from 1 to n

> 同樣道理，Accounting method的 bank 存款也不能為負



> Master theorem case 3:

> $m*1/m^{3}$

> 這是在說對於所有sort 最多就是$nlgn$個比較，但是像是insertion sort就有可能 $n^2$
（little o 是對於所有 n 都要成立）
等於說sorting得上限被壓到nlgn了（問題是it's not the case）

--
> WLOG，先排好 ACD，接著用兩次comparison找出E的位置，E排在哪裡都沒差，因為先前假設A > B，所以B也一定只會需要和三個人比較，也就是兩次comparison
> 第一點：decision tree必須要是balanced（對任何input，建構出來的decision tree），才可以說因為 $2^h > n!$，所以必定可以sort好
第二點：$lg(n!)$ 和 $nlgn$ 只是 theta bound的關係，數字大小沒有絕對關係


---

> $source ->t ->... ->u->v$
$d[v] = d[u] + w(u, v)$, in which $w(u,v) > 0$
我們可以從後面一個一個往前推，u在到v的s-t path中，再往前推，最後推到t， t是s到v的shortest path中最靠近s 的node，因此可以證明t也在shortest path中，因為edge weight 只有在從s出去的時候才是 < 0，但s為起點，一定在shortest path中（因為是求s到v的shortest path，所以不影響正確性），所以t也必定在shortest path中。
> 要注意：Dijkstra的**正確性**是建立在**沒有 negative weight edge**之上，而不是沒有negative weight cycle。


> $n(n+1) / 2*n = (n+1) / 2$ --> $O(n)$


> johnson's algorithm allow negative weights because it will reweight those edges
--> but no negative cycle allowed!
--> graph may not have cycle --> DAG

> 也可用遞迴來想
存在n條線，再加上一條線與這n條都相交
total = $n + n +1$
故從1開始，是$1 + 2 + 3 + 4 + ... + n
= O(n^2)$


> Johnson's algorithm的正確性：
> 1. negative cycle若存在於原本的圖，則用source和weight 0 edge連接每個vertex後，negative cycle繼續存在
> 2. triangle inequality：從 s 到 u 和 s 到 v的shortest path距離，再加上w(u,v)，即有不等式，用來reweight，保證reweight後的edge weight > 0


> Diffie Hellman (DH) key exchange algorithm 三人以上不適用

> A van Emde Boas tree (Dutch pronunciation: [vɑn 'ɛmdə 'boːɑs]), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O(log m) time, or equivalently in O(log log M) time, where M = 2m is the maximum number of elements that can be stored in the tree. The M is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has good space efficiency when it contains many elements, as discussed below. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.[1]


## others
> 看到要求複雜度$O(1)$，通常就是要用hash
> 
>