# 台大資演
## 111
(14.,15.)A,B
此題要注意紅黑樹跟234-tree等價的特性

15.
26個node的red-black tree,可製作出13個皆為含2個keys的node的2-3-4 tree，以此圖若轉化回red-blacl tree即為高度為6的red-black tree

14.而依上圖可知總共n/2個node為一黑帶一紅。

# 交大資演
## 111
3.
(E)AVＬ的insertion&rotation 比red black tree複雜

13.
(E)非dynamic

14.
(A)Array才static
link list is called dynamic because it can be used with a data collection that grows and shrinks during program execution

(D)best time,短的跑完即可，O(n)

(E)這邊的merge 應只是連起來，而非ordered merge

18.這題個人覺得應該有問題，當年我有查到他的選項是從某本原文書抄下來的，應該是全才對，但我有點忘了是哪一本。

23.雖然筆記上寫的是stable但那是因為他寫<而這題是<=故非stable。

32.畫成圖後走得路徑weight挑最小

33.
(c)104年證過了

37.
(c)
co-np:x∈co-NP↔x^c∈NP
np-complete 問題不落在co-np
反np-complete問題不落在NP

38.
O(V+E)即完成，
algo:任意挑一點，並把任意鄰點挑入，重複直到皆納入

## 110
1.NP是polynomial time可驗證
NP hard才是不確定能否在polynomial time驗證

11.
(D)minimum cut值=max flow 只有一種
(E)兩者相同 故相加為複數
12.
把master theory三個case都講得很清楚，推推:
https://www.youtube.com/watch?v=OynWkEj0S-s&t=887s

(B)筆記有
(C)因找不到ϵ 不能用master theory

14.注意是說minimum degree of 3,故要考慮degree=3,4,5,6..等等狀況。

20.dynamic array.

21.
因題目給6個data
根據tenary huffman tree要先merge 2個若資料是奇數才能3個3個merge.
因為3個3個merge每次總數減2，而最終只會剩下一個node故要先把數量弄成奇數。

27.
在滿足task i~n,
si<...<sk(start time)
f1<....<fk(end time)
時greedy才成立

從頭choose 結束時間且compatible
從尾choose 開始時間且compatible
皆可達到上述性質

30.
(A)T(n)=T(n/3)+T(5n/6)=T(7n/6)
(B)T(n)=T(n/7)+T(11n/14)=T(13n/14) bn
## 109
(10).minimum degree of b-tree=t
(A)any node may contain at most 2t-1 keys
(D)不包含root 所有點at least t-1個keys
(E)
height of B-tree h從- min deg=t>=2
root 有1key 其他t-1個keys
h=1: 2
h=2: 2t
h=3: 2t^2
n>=1+(t-1) ∑_i=1~h(2t^(i-1))
=1+2(t-1)(t^h-1)/(t-1)
=2t^h-1

6.
(15)
A->B->D->E->C->A->B->D->E->F
(17)
A->C->A->B->D->E->C->A->B->D->E->F

8.
(23)
if n為奇 an=a_(n-1)+6b_(n-1),bn=2a_(n-1)+b_(n-1)
if m為偶 an=(a_(n/2))^2+3(b_(n/2))^2,bn=2a_(n/2)b_(n/2)
遇到奇就變偶再recursive

## 108
10.
algo2:larger part 指的不是數字上的large而是長度上的large因此才要1/3~2/3這段
(20)
lim(1-(2/3)^n)/(1-2/3)=3
or
執行一次機率1/3
=....2/3x1/3
=....2/3x2/3x1/3
1x1/3+2x2/3x1/3...=1/3 sigma (r(2/3)^r-1)
=3

11.
判斷總數為何，若是奇數先去除最大的、偶數不變，剩下的儲存值相鄰相加。
(4+4)+8+(5+4)+(3+5)
=(8+8)+(9+8)=16+17
=>8+9+8+16+17+31=91

15.
-2 直接全拿，m=n^2物品總重為n
-3 同上
## 107
9.(b)紀錄第1~第i項最小和
10.加點強迫起終點
## 106
15.
將red edges 的weights 設0
將blue edges的weights 設1
採kruskal's algo建MST
weight較小的red edge 會先被考慮
## 105
3.2,3格不在while裡

(17)
(b)theta(m) space
(c)theta(m) space

(23)
(c)less than 才停的話相等會跳過就不stable了。

(24)
(a)an algo can be said to be optimal if the describes its time complexity in the worst case is a lower bound of the ftn that describes the time complexity in the worst case of a problem that the algo in question solves.
(b)會nlogn是因為comparison based，跟選項說的無關

(25)
(c)圖太大要擔心 stack overflow union/find 比較省

(26)
(a) n-1 unions

11.
(31)
2/m(撞前面2個其中一個)x1/(m-1)(第一個撞過剩(m-1)個選項)
(32)
空位的比例
(33)
先放一個:1
下一個跟他一樣:1/m
1x1/m=1/m

(48)
(B) amortized的結果
(c)他一次就是logv了不用amortized來看

20.
Y is polu reducible to x
=> x is at least as hard as y
(A)P is subset of NP .NP can reduce to NP-complete in polynomial time.
(E)CNF 轉3-CNF的時候literal不會全來自原式
ex.
A ∨ Ｂ
=>(A∨B∨P)∧(A∨B∨~P)

(60)
## 104
2.
(A)筆記有很多反例
(B)後序沒刮號
(C)運算元轉完後順具仍一樣
(D)stack不算priority queue

21.
(A).若沒有where....的條件則不成立，
ex. f(n)=2 g(n)=1
lg(f(n))=1 lg(g(n))=0
O(lg(f(n))) !=O(lg(g(n)))
(B).f(n)=2n g(n)=n
=>2^f(n)=2^(2n)!=O(2^n)
(D)筆記有
(E)polynomial bounded的定義，記起來

22.
(A)函數不一定趨近於固定
ex.
g(x)=xsin(x)+x
f(x)=lg(x)
O,omega都不成立
(C)space complexity is always the lower bound of time complexity

25.
(B)筆記有O(nlglgn)

26.
(B,C).
ex.

28.
(C)
設存在2 MST:T,T'，對任一邊e∈T若從T中移除e則T變得不聯通
形成cut(s,V-s)且e試穿過cut(s,V-s)之最輕邊，
設x∈T'穿過cut(s,V-s)則x同樣最輕由於穿過cut(s,V-s)的最輕邊唯一，
e=x
=>所有在Ｔ的邊也在T'中
=>MST唯一

若反過來說則不成立。
(B) (D)
|1----/1----cut
(A)
切到權重一樣的邊

NOTE:
greedy:
greedy choice property ,optimal substructure都是用來形容'問題'的
greedy choice property:
是充分但非必要條件
=>透過greedy algo 可以達到global optimal但global optimal可能不只一個，因此不能說我有global optimal就代表從greedy來，shortest path 問題若直接取一個最短到另一個city他後面的路可能長於一開始選另一條路的長度。

optimal substructure:
比較像知道答案回去看他的subproblem 也是optimal, greedy choice property則是從最初一直做，結果是optimal。
## 103
8.
(7)strassen matrix algo:7 個子問題的算法,D&C
9.
(5)像HC
(6)BFS即可
11.
a. 圖sparse時比floyd快
## 102
8.void partition中 data[i]<pivot_v的case中沒有++i

12.第二格：有給值域1~|V|且為整數，因此可以counting sort，並用disjoint set 看是否有cycle=O(alpha(v))大約=O(1)
E* O(1)=O(E)

15.
R1,R2全流//p1 ok
仍有5篇未有兩人看
但R3只能看4篇且R3={A11}
因此4+p1=5篇

17.圖畫出來加一點Bellman ford個點值相加即可。

## 101
4.注意從1開始不是0，因此root8不會動。
5.
(13)
因已排序好，故可以在node中做binary search，
找node:O(n/m)+在node內找目標值:O(log m)=O(logm + n/m)
(14,15)
一個node有m/2個data，至多2n/m個node 因此找node=O(n/m)，而在一個node中insert or delete要移動m個data因此O(m)。
7.

14.
(40)排序好再從頭到尾比較:O(nlogn+ n )= O(nlogn)
(41)掃過整條array找MAX&MIN=O(n)
(42)已排序好，可用二分搜尋法=O(logn)

15.
(43)題目有規定只能用greedy 故以v/w去取可得34。
(45)用dp可達更好結果，fractional才可用greedy。
16.nubnaxpath(bottleneck path)找最大瓶頸：所有可從s->t中最大邊為最小的。
=找bottle neck spanning tree
BST不難於MST
(46)C.找到MST即可
(47)
走1步:2
走2步:5
走3步:5
走4步:2
B.一直一步一步走
D.ex. 1->2->3 1->4->3

(53)變起點到該點。
prim's algo 跟dijkstra就差在一個用從src到一個node的dist來選node,而prims是用一個node到目前集合的距離來選node。
(54)
n^2:用adjacent maxtrix delete-min一次花n共n次=n^2
m:decrease key
n:initialize step
19.
HP,shortest,longest
20.
(58)D.即使所以有邊有不同capacity仍有多種切法。
(60)D. flow value 不一定為整數。
## 100

(5)非遞迴版的DFS
(15)題目應改antisymmetric
(29)要注意selection sort跟bubble sort的差別在於 selection一圈只會swap 一次，而bubble sort每次都會swap。
(34)
E.並不是所有greedy choice都會output最佳解，要確認正確性（greedy choice property,optimal substructure）
(53)
C.並不是任意皆可連，只有S,T
(56)
B.如果說method應該就是對的
## 99

## 備註
1. hash map 的quadratic probing有多種定義有的要+-、有的不用、有的ax^2 + bx+c也可以。