# Week 12
# Question
:::info
:::spoiler Click to Open Question
:::
# Answer
## Q1
> - [name=songchiu]
:::spoiler 題目
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges not in T. Give an algorithm for finding the minimum spanning tree in the modified graph.
:::
**【解題思路】**
1. 把降低權重的那條邊$(u,v)$，接回$\text{Minimum Spanning Tree}$ $T$裡
2. 對該條邊上任一點進行$\text{DFS}$，找出環以及環上的各個邊
3. 把環上權重最重的邊，從$T$當中移除
**【圖示】**
原圖：
將$(b,e)$的weight從$5 \rightarrow 1$：
拿掉$(b,e)$、$(b,f)$、$(e,f)$裡三個weight最大的邊$(b,f)$還是個$MST$：
**【蘇都扣】 (以上圖為例)**
```cpp=
set find to false //找到環了沒
decrease weight of edge(b,e)
add edge(b,e) into MST
stack = DFS(T, b)
removeMaxWeight(stack)
```
```cpp=
DFS(T, b){
mark b as visited, push b into stack
for each v ∈ Adj[b]
if v has not visited
DFS(T, v)
else
set find to true and return stack //找到環了，把程式結束掉
if find is false
pop stack //環不在這
else
return stack
}
```
```cpp=
removeMaxWeight(stack){
top = temp1 = stack.pop //把最上面那個存起來
max = 0
while stack.size > 0 //兩個兩個抓出來比較
temp2 = stack.pop
if(edge(temp1, temp2) > max and stack.size > 0)
max = edge(temp1, temp2)
else if(edge(temp1, top) > max and stack.size = 0)
max = edge(temp1, top) //回頭跟最前面的比較
temp1 = temp2
remove max from MST
}
```
**【時間複雜度】**
對加上一條邊之後的$T$進行$\text{DFS}$為$O(|V|)$
在環上找權重最大的邊為$O(|V|)$
故時間複雜度為$O(|V|)$
## Q2
> - [name=chung]
:::spoiler **【題目】**
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?
:::
Kruskal’s algorithm requires $O(ElogE)$ time:
- 初始化: $O(V)$
- 排序所有邊長的weight: $O(ElogE)$
- disjoint-set union: $O(Eα(V))$
1. 如果邊長的weight的範圍已知會介在1到|V|之間，可運用Counting Sort使時間複雜度為$O(V+E)=O(E)$ (因為是connected graph，$V = O(E)$)，因此Kruskal’s algorithm時間複雜度降為$O(V+E+Eα(V))=O(Eα(V))$
2. 如果邊長的weight的範圍會介在1到W之間，而W為一常數，則Counting Sort可使時間複雜度為$O(W+E)=O(E)$，Kruskal’s algorithm時間複雜度為$O(Eα(V))$
**【蘇都扣】**
```cpp=
MST-KRUSKAL(G,w){
A=∅
for each vertex v ∈ G.V
MAKE-SET(v)
sort the edges of G.E order by nondecreasing weight w
for each edge (u,v) of G.E, taken in nondecreasing order by weight w
if FIND-SET(u)!=FIND-SET(v)
Add (u,v) to A
Union(u,v)
return A
}
```
## Q3
> - [name=yee]
:::spoiler **【題目】**
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?
:::
$Let\ |V|=n,|E|= m$
#### 【Range 1 to |V|】
若為sparse可用一般heap來實作。
時間複雜度為$O(mlogn)$
若非sparse則$m$可能到$n^2$所以透過Fibonacci Heap來實作。
時間複雜度為$O(nlogn + m)$
#### 【Range 1 to W】
建立一個陣列Q[1...W] 來存放每個V(index為該V的weight)若有weight重複的V則透過Doubly linked list 連接。
使得 EXTRACT-MIN 由最小到大找到非空的陣列花$O(W)=O(1)$，
另外Change-Priority只花$O(1)$最差情形為每個邊都需要做一次Change-Priority需要花$O(m)$
時間複雜度為$O(n+m) = O(m)$
[Ref.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.5197&rep=rep1&type=pdf)
## Q4
> - [name=Mark]
:::spoiler Question
:::
### 【a小題】
Q: 舉一個所有 edge 的 weight 都不同，MST 唯一而 Second-Best MST 不唯一的例
### 【b小題 - 可跳過】
Q: $T為MST$，證明$T-{\{u,v\}} \cup{\{x,y\}}$就是 Second-Best MST
**證明**
1. 令 SBMST 有$\{x,y\}$取代$\{u,v\}$，及$T-{\{u,v\}} \cup{\{x,y\}}$
2. 令 SBMST' 也是 Second-Best MST 除了有$\{x,y\}$取代$\{u,v\}$，還有$\{x,z\}$取代$\{u,w\}$，及$T-{\{u,v\}} \cup{\{x,y\}}-{\{u,w\}} \cup{\{x,z\}}$
3. 根據MST的引理，$\{x,z\}的weight$ > $\{u,w\}的weight$可得出 4.
4. $SBMST' 的weight$ > $SBMST的weight$，與先前假設矛盾，SBMST' 非 Second-Best MST
5. 得 $T-{\{u,v\}} \cup{\{x,y\}}$就是 Second-Best MST，及 Second-Best MST 只能與 MST 差異一個 edge
### 【c小題】
**想法**
用DP來對$max[u, v]$做紀錄，再跑DFS對spanning tree做搜尋就可以找到了
**蘇都扣**
```cpp=
//T is spanning tree of G
//W(u,v) can get weight of edge(u, v)
let max[u, v] is a empty table to record the max edge between u, v
MaxEdge(T)
For each u ∈ T
u.visited = false
For each u ∈ T
DFS(T, u, u)
return max
DFS(T, u, x)
u.visited = true
for each v ∈ T.Adj[u]
if v.visited == false //這裡是不是好像也不用寫QQ
if max[u, v] == 0 //我總覺得這裡事不事也不用寫
if x == u or w(x, v) > max[u, x] //我覺得這裡應該要放w(max[u,x])
max[u, v] = (x, v)
else max[u, v] = max[u, x]
DFS(T, u, v)
```
<!--
```cpp=
//T is spanning tree of G
//W(u,v) can get weight of edge(u, v)
MaxEdge_DP(T)
let max be a new table with an entry max[u, v] for each u, v ∈ T.V
for each vertex u ∈ T.V
for each vertex v ∈ T.V
max[u, v] = 0
DFS(T, max)
return max
DFS(T, u, x, max)
for each vertex v ∈ T.V
if max[u, v] == 0 and v != u
if w(x, v) > max[u, x]
max[u, v] = (x, v)
else max[u, v] = max[u, x]
DFS(T, u, v, max)
```
-->
**Time Complexity**
DFS 因為是 tree 所以為 $O(|V|)$，因此 MaxEdge_DP 為 $O(V^2)$
### 【d小題】
設計一個演算法找出G的Second-Best MST
If we know which (x, y) to add to T2, then (u, v) must be the max-weight edge in the path from x to y (which can minimize the second part of the equation above).
**想法**
1. Prim's Algorithm 找到 G 的 MST，$O(ElogV)$
2. MaxEdge_DP 找到 MST 裡面最大的 edge -> max[x,y]，$O(V^2)$
3. 找到一個 (x,y) 不屬於T，且 w(x,y) - w(max[x,y]) 最小，$O(V^2)$
4. 透過b小題的想法，$T-{\{u,v\}} \cup{\{x,y\}}$，就可以找到 Second-Best MST
**蘇都扣**
```cpp=
//G is undirected graph
//w is weight
//r is root of MST
SB_MST(G, w, r)
{
MST = Prim(G, w, r) //找MST
Max[][] = MaxEdge(MST)
maxEdge, minEdge = max edge in Max
Remain = G - MST //把原本的G去掉MST的邊
for each edge (u,v) in Remain.edge
if w(minEdge) > w(u,v) - w(Max[u][v])
minEdge = (u,v)
(u,v) = minEdge
SBMST = MST - Max[u][v] + minEdge
return SBMST
}
```
**Time Complexity**
Total 為 $O(V^2)$
## Q5
> - [name=xian]
:::spoiler **【題目】**
Consider the following algorithm for the problem from Section 16.5 of scheduling unit-time tasks with deadlines and penalties. Let all $n$ time slots be initially empty, where time slot $i$ is the unit-length slot of time that finishes at time $i$. We consider the tasks in order of monotonically decreasing penalty. When considering task $a_j$, if there exists a time slot at or before ${a_j}'s$ deadline $d_j$ that is still empty, assign $a_j$ to the latest such slot, filling it. If there is no such slot, assign task $a_j$ to the latest of the as yet unfilled slots.
> a. Argue that this algorithm always gives an optimal answer.
>
> b. Use the fast disjoint-set forest presented in Section 21.3 to implement the algorithm efficiently. Assume that the set of input tasks has already been sorted into monotonically decreasing order by penalty. Analyze the running time of your implementation.
:::
【a小題】
令 O 為最優解。
1. 如果 $a_j$ 在 deadline 之前安排，我們可以將它與在 deadline 前安排的任何活動交換，且不會增加 penalty。
1. 如果它是在 deadline 後安排的，但因為 $j.deadline \le j$，則必須存在前 $j$ 中的任務，其 penalty 小於 $a_j$，因此可以和$a_j$交換，以減少 penalty。 但因為O是最優解( $a_j$ 是以 penalty 降序排序)，所以不可能發生。
1. 如果 $a_j$ 被安排在它的 deadline 後且 $a_j.deadline > j$，我們可以將 $a_j$ 與其他延遲的任務交換而不會增加 penalty。
因為表現出greedy choice property，所以這種貪心策略總是產生最優解。
**【蘇都扣】**
```cpp=
// let a[i] be the a_i, and a[i].time be the finish time of a_i
// if x is a disjoint set, x.low is the earliest time of activity in s
// n: given by question
// D[i] contains a pointer to the activity with deadline i.
SCHEDULING(a){
let D[1..n] be a new array
for i = 1 to n
a[i].time = a[i].deadline
if D[a[i].deadline] != NULL: //處理這個時間點已經有排活動了
y = FIND_SET(D[a[i].deadline])
a[i].time = y.low - 1
if a[i].time == 0:
x = MAKE_SET(a[i])
put x to the last unfilled slot in d
if D[a[i].time - 1] != NULL:
UNION(D[a[i].time - 1], D[a[i].time])
if D[a[i].time + 1] != NULL:
UNION(D[a[i].time], D[a[i].time + 1])
continue
x = MAKE_SET(a[i])
D[a[i].time] = x
x.low = a[i].time
if D[a[i].time - 1] != NULL:
UNION(D[a[i].time - 1], D[a[i].time])
if D[a[i].time + 1] != NULL:
UNION(D[a[i].time], D[a[i].time + 1])
return D
}
```
$ans: D_\#$
**【時間複雜度】**
MAKE_SET、UNION、FIND_SET 最多各執行n次(for迴圈為 n)
by Theorem 21.14, 時間複雜度為 $O(n\ α(n))_\#.$
## Q6
> - [name=LXS]
::: spoiler 題目
For a set of variables $x_1, x_2, … , x_n$, you are given some equality constraints, of the form $“x_i = x_j”$ and some disequality constraints, of the form $“x_i \ne x_j”$. Is it possible to satisfy all of them? For instance, the constraints : $x_1 = x_2,; x_2 = x_3; x_3 = x_4; x_1 \ne x_4$; cannot be satisfied. Give an efficient algorithm that takes as input $m$ constraints over $n$ variables and decides whether the constraints can be satisfied. Describe the data structure used by your algorithm, and analysis the time complexity of your algorithm.
:::
#### 【解題思路】 — Disjoint set
#### 【Psuedo code】
```python=
def satisfyTest():
DS = Disjoint_set()
for i in variables:
DS.create(i)
flag = satisfied
for i in constraint:
if i.operation == "=":
DS.equality(i.first, i.second)
union(DS[i.first], DS[i.second])
for j in constraint:
if j.operation == "!=":
if find(DS[j.first], DS[j.second]):
flag = connot_be_satisfied
return flag
return flag
```
::: spoiler 舊解法 **僅適用Boolean variables**
#### 【解題思路】
將每個變數視為一個可填色的節點，使用兩個**Adjacency List**以邊的方式分別儲存等式與不等式，不等式意味兩著顏色需不同，等式意味顏色相同，對於每個邊去檢查自身顏色與相鄰節點顏色，
由於每個邊只會被填色一次，我們又針對每個邊去檢查，時間複雜度為$O(|V|+2|E|)$也就是$O(n+2m)\in O(n+m)$
<!-- Space complexity:$O(n+m)$ -->
#### 【Psuedo code】
```python=
n = 4
color = ["?" for _ in range(n)]
# m = # of equal + # of notEqual
equal = [[1], [0, 2], [1, 3], [2]] # x0=x1 x1=x2 x2=x3 x2=x3
notEqual = [[3], [], [], [0]] # x1!=x4
def Paint(v: int, val: bool):
if color[v] != "?": # Colored -> Check
return color[v] == val
color[v] = val # Not Colored -> Assume current edge valid
for u in range(len(equal[v])): # Check other equality edges
if not Paint(equal[v][u], val):
return False
for u in range(len(notEqual[v])): # Check other inequality edges
if not Paint(notEqual[v][u], not val):
return False
return True
def main():
for v in range(len(color)):
if color[v] != "?": # Traversed
continue
if not Paint(v, True): # Can be either true or false
return False # Can't satisfied
```
:::
Sign in with Wallet
Connect another wallet