---
# System prepended metadata

title: Homework XIII

---

---
title: Homework XIII
---
# P1
[CLRS 3rd] Problem24.3 Arbitrage
## Topic
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0.0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 49 × 2× 0.0107=1.048649  U.S. dollars, thus turning a profit of 4.86 percent.

Suppose that we are given n currencies $c_1, c_2, \ldots, c_n$ and an n×n  table R of exchange rates, such that one unit of currency $c_i$ buys R[i,j] units of currency $c_j$.

a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies $\langle c_{i_1}, c_{i_2}, \ldots, c_{i_k} \rangle$ such that

$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k - 1}, i_k] \cdot R[i_k, i_1] > 1.$

Analyze the running time of your algorithm.

b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

## Solution
### a.
![](https://i.imgur.com/IlcnshE.png)

edge的權重 : $-ln(R[u,v])$
若edge形成負環代表可以獲利(匯率相乘大於1)
```
Bellman_Ford{
    for i = 1 to V
       for each edge (u, v) ∈ E
          if d[v]>d[u]+w(u,v)
            d[v]=d[u]+w(u,v)
            pi[v]=pi[u] add u	//ancestor set to find cycle
            if(find negative-cycle)
                Print_Cycle(pi[v],v)
                return true	//find
    return false;    //not find
}
```
我們用Bellman_Ford檢查負環,因此時間複雜度為O(VE)
### b.
輸出的負環就是所求的兌換順序
```
Print_Cycle(set,v){
    start=set.get_index(v)    //index of v(first appear
    for count=start to set.size()-1
        cout << set.at(count) << ',';
}
```
負環最多由E個edge組成,因此時間複雜度為O(E)
# P2
[CLRS 3rd] Exercise 25.1-10
- [ ][name=Joe]
## Topic
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.
## Solution
用Floyd-Warshall解
time complexity = $O(V^3)$
```pseudo=
Floyd-Warshall(){
    Initialization( ); // d[u,v] = w[u,v]
    vector negative;
    For k from 1 to n 
        For u from 1 to n 
            For v from u to n 
                d[u,v] = min(d[u,v], d[u,k]+d[k,v]);
    For i from 1 to n // check negative cycle
        if d[i,i]<0
            store i into negative
    return negative;
}

```

# P3 
[CLRS 3rd] Exercise 25.2-1
- [ ] 民
> 記得把到自身的距離設成無限大跑跑看 助教在下面額外要求的 [name=Joe][color=#F55555]
> 你是說下面對角線的那個嗎? [name=民]
> 對 把0改成無限大 [name=Joe]
> 我弄好了[name=翔]
## Topic
Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 25.2. Show the matrix $D^{(k)}$ that results for each iteration of the outer loop.
## Solution
![](https://i.imgur.com/XPxenMG.png)
![](https://i.imgur.com/OgeFwlP.png)

將對角線設為$\infty$:
| 0   | $D^0$    |          |          |          |          |          |
| --- | -------- |:-------- | -------- |:-------- |:-------- |:-------- |
|     | 1        | 2        | 3        | 4        | 5        | 6        |
| 1   | $\infty$ | $\infty$ | $\infty$ | $\infty$ | -1       | $\infty$ |
| 2   | 1        | $\infty$ | $\infty$ | 2        | $\infty$ | $\infty$ |
| 3   | $\infty$ | 2        | $\infty$ | $\infty$ | $\infty$ | -8       |
| 4   | -4       | $\infty$ | $\infty$ | $\infty$ | 3       | $\infty$ |
| 5   | $\infty$ | 7        | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 6   | $\infty$ | 5        | 10       | $\infty$ | $\infty$ | $\infty$ |

| 1   | $D^1$    |          |          |          |          |          |
| --- | -------- |:-------- | -------- |:-------- |:-------- |:-------- |
|     | 1        | 2        | 3        | 4        | 5        | 6        |
| 1   | $\infty$ | $\infty$ | $\infty$ | $\infty$ | -1       | $\infty$ |
| 2   | 1        | $\infty$ | $\infty$ | 2        | 0        | $\infty$ |
| 3   | $\infty$ | 2        | $\infty$ | $\infty$ | $\infty$ | -8       |
| 4   | -4       | $\infty$ | $\infty$ | $\infty$ | -5       | $\infty$ |
| 5   | $\infty$ | 7        | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 6   | $\infty$ | 5        | 10       | $\infty$ | $\infty$ | $\infty$ |

| 2   | $D^2$    |          |          |          |     |          |
| --- |:-------- |:-------- | -------- |:-------- |:--- |:-------- |
|     | 1        | 2        | 3        | 4        | 5   | 6        |
| 1   | $\infty$ | $\infty$ | $\infty$ | $\infty$ | -1  | $\infty$ |
| 2   | 1        | $\infty$ | $\infty$ | 2        | 0   | $\infty$ |
| 3   | 3        | 2        | $\infty$ | 4        | 2   | -8       |
| 4   | -4       | $\infty$ | $\infty$ | $\infty$ | -5  | $\infty$ |
| 5   | 8        | 7        | $\infty$ | 9        | 7   | $\infty$ |
| 6   | 6        | 5        | 10       | 7        | 5   | $\infty$ |

| 3   | $D^3$    |          |          |          |     |          |
| --- |:-------- |:-------- | -------- |:-------- |:--- |:-------- |
|     | 1        | 2        | 3        | 4        | 5   | 6        |
| 1   | $\infty$ | $\infty$ | $\infty$ | $\infty$ | -1  | $\infty$ |
| 2   | 1        | $\infty$ | $\infty$ | 2        | 0   | $\infty$ |
| 3   | 3        | 2        | $\infty$ | 4        | 2   | -8       |
| 4   | -4       | $\infty$ | $\infty$ | $\infty$ | -5  | $\infty$ |
| 5   | 8        | 7        | $\infty$ | 9        | 7   | $\infty$ |
| 6   | 6        | 5        | 10       | 7        | 5   | 2        |

| 4   | $D^4$    |          |          |          |     |          |
| --- |:-------- |:-------- | -------- |:-------- |:--- |:-------- |
|     | 1        | 2        | 3        | 4        | 5   | 6        |
| 1   | $\infty$ | $\infty$ | $\infty$ | $\infty$ | -1  | $\infty$ |
| 2   | -2       | $\infty$ | $\infty$ | 2        | -3  | $\infty$ |
| 3   | 0        | 2        | $\infty$ | 4        | -1  | -8       |
| 4   | -4       | $\infty$ | $\infty$ | $\infty$ | -5  | $\infty$ |
| 5   | 5        | 7        | $\infty$ | 9        | 4   | $\infty$ |
| 6   | 3        | 5        | 10       | 7        | 2   | 2        |

| 5   | $D^5$ |     |          |     |     |          |
| --- |:----- |:--- | -------- |:--- |:--- |:-------- |
|     | 1     | 2   | 3        | 4   | 5   | 6        |
| 1   | 4     | 6   | $\infty$ | 8   | -1  | $\infty$ |
| 2   | -2    | 4   | $\infty$ | 2   | -3  | $\infty$ |
| 3   | 0     | 2   | $\infty$ | 4   | -1  | -8       |
| 4   | -4    | 2   | $\infty$ | 4   | -5  | $\infty$ |
| 5   | 5     | 7   | $\infty$ | 9   | 4   | $\infty$ |
| 6   | 3     | 5   | 10       | 7   | 2   | 2        |

| 6   | $D^6$ |     |          |     |     |          |
| --- |:----- |:--- | -------- |:--- |:--- |:-------- |
|     | 1     | 2   | 3        | 4   | 5   | 6        |
| 1   | 4     | 6   | $\infty$ | 8   | -1  | $\infty$ |
| 2   | -2    | 4   | $\infty$ | 2   | -3  | $\infty$ |
| 3   | -5    | -3  | 2        | -1  | -6  | -8       |
| 4   | -4    | 2   | $\infty$ | 4   | -5  | $\infty$ |
| 5   | 5     | 7   | $\infty$ | 9   | 4   | $\infty$ |
| 6   | 3     | 5   | 10       | 7   | 2   | 2        |
# P4
[CLRS 3rd] Exercise 25.3-1
- [ ] 民
## Topic
Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph of Figure 25.2. Show the values of h and $\hat w$ computed by the algorithm.
## Solution


| v | h(v) | 
| -------- | -------- | 
| 1     | -5     |
| 2     | -3     |
| 3     | 0      |
| 4     | -1     |
| 5     | -6     |
| 6     | -8     |

![](https://i.imgur.com/Tvr1CHh.png)

So the d(i,j) values that we get are
![](https://i.imgur.com/qqy7cWd.png)





# P5
[CLRS 3rd] Problem25.1 Transitive closure of a dynamic graph
## Topic
Suppose that we wish to maintain the transitive closure of a directed graph $G=(V, E)$ as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph G has no edges initially and that we represent the transitive closure as a boolean matrix.

a. Show how to update the transitive closure $G^* = (V, E^*)$ of a graph G = (V, E) in $O(V^2)$ time when a new edge is added to G.

b. Give an example of a graph G and an edge e such that $\Omega(V^2)$ time is required to update the transitive closure after the insertion of e into G, no matter what algorithm is used.

c. Describe an efficient algorithm for updating the transitive closure as edges are inserted into the graph. For any sequence of n insertions, your algorithm should run in total time $\sum_{i = 1}^n t_i = O(V^3)$, where $t_i$ is the time to update the transitive closure upon inserting the ith edge. Prove that your algorithm attains this time bound.
## Solution
### a.
![](https://i.imgur.com/GSzvaMK.png)

![](https://i.imgur.com/q4sZzes.png)

![](https://i.imgur.com/IbMMVQN.png)

![](https://i.imgur.com/ofAbfcJ.png)

由圖可知插入edge(B,C)後,若(A,B)&(C,D)皆連通則(A,D),(A,C),(B,D)也會連通
總共檢查$V*V$次,所以時間複雜度為$O(V^2)$
``` pseudo=
initial(T,G);	    //if(u==v){T[u][v]=1} else{T[u][v]=0}
update(T,edge){
    T[x][y]=1    //G<-edge(x,y)
    for each u in G.V
        for each v in G.V
            if ( T[u][x]==1 && T[y][v]==1)
                T[u][v] = 1
}
```
### b.

當兩個點數為$V/2$ strongly connected components加了一條連接兩個component的邊, 則會有V/2個點可以連到另一個strongly connected component所有點, 總共$V^2/4$個矩陣裡的entry需要更新, 假設更新可在constant time內完成, 時間複雜度為$\Omega(V^2)$

### c.
藉由a小題的方法，每次都新增1條邊，總共要新增n條邊，故新增了n次；而a小題的方法其時間複雜度為$O(V^2)=t_i$，因此新增n次的時間複雜度為$\sum_{i = 1}^n t_i = O(V^3)$，

# P6
## Topic
Give  an  efficient  algorithm  to  count  the  total  number  of  shortest  paths between any pair (u, v) of vertices in a directed graph. (There may be a cycle but definitely no negative-cycle)
## Solution
![](https://i.imgur.com/0BtIiCA.png)
在原本的Floyd-Warshall algorithm裡記下每條路徑的$\pi$, 在回溯路徑時只能得到最早紀錄的一條最短路徑
如:
1~>4: 1->3->4
1~>5: 1->5
1~>2: 1->2
...

==原始演算法得到的$\pi$==
| $\pi$ | 1   | 2   | 3   | 4   | 5   |
|:----- | --- |:--- |:--- | --- |:--- |
| 1     | NIL | 1   | 1   | 3   | 1   |
| 2     | NIL | NIL | NIL | 5   | 2   |
| 3     | NIL | 3   | NIL | 3   | 2   |
| 4     | NIL | NIL | NIL | NIL | NIL |
| 5     | NIL | NIL | NIL | 5   | NIL |
為了記下所有的最短路徑, 使用set矩陣來儲存$\pi$

==新演算法得到的$\pi$==
| $\pi$ | 1   | 2    | 3   | 4    | 5    |
|:----- | --- |:---- |:--- |:---- |:---- |
| 1     | NIL | 1, 3 | 1   | 3, 5 | 1, 2 |
| 2     | NIL | NIL  | NIL | 5    | 2    |
| 3     | NIL | 3    | NIL | 3, 5 | 2    |
| 4     | NIL | NIL  | NIL | NIL  | NIL  |
| 5     | NIL | NIL  | NIL | 5    | NIL  |
透過遞迴式和$\pi$可以還原所有最短路徑和計算最短路徑數量
如:
1~>5: 1->5, 1->2->5
1~>4: 1->3->4, 1->5->4, 1->2->5->4, 1->3->2->5->4
3~>4: 3->2->5->4, 3->4
...

``` pseudo=
Floyd-Warshall ()
input: graph in adjacency matrix
output: count[u, v]
    initialization() //d[u,v] = w[u, v], parent[u,v] = u if u->v, count[u, v] = 0
    for(int k = 1;k<=n;k++)
        for(int u = 1;u<=n;u++)
            for(int v=1;v<=n;v++)
                if d[u, v] > d[u, k]+d[k, v] //shorter path
                    d[u, v] = d[u, k]+d[k, v]
                    parent[u, v].clear()
                    parent[u, v] = parent[k, v]
                else if d[u, v] == d[u, k]+d[k, v]
                    parent[u, v].insert(parent[k, v])
    for(int u = 1;u<=n;u++)
            for(int v=1;v<=n;v++)
                count_path(u, v, v, parent, count)
            
count_path(u, k, v, parent, &count)
    if u==k
        count[u, v]++
    else
        for n in parent[u, k]
            count_path(u, n, v)
    
```
算完$\pi$後回溯每個pair的最短路徑

計算$\pi$: $O(n^3)$
pair數量: $O(n^2)$
回溯時間複雜度: $O(n^2)$ //u到v有 O(n)個最短路徑, 路徑上有O(n)個點
時間複雜度: $O(n^4)$
有點慢, 或許修改一下就可以在跑Floyd-Warshall algorithm的時後就算答案來
# P7
- [ ] [name=Joe]
## Topic
給三個整數m,n,p設計一個有效率的演算法，算出$m^n\ mod\ p$
## Solution
If n is odd,
$m^n\ mod\ p=((m^2)^{(n/2)}*m)\ mod\ p=((m^2\ mod\ p)^{(n/2)}*m)\ mod \ p$
If n is even,
$m^n\ mod\ p=((m^2)^{(n/2)})\ mod\ p=((m^2\ mod\ p)^{(n/2)})\ mod \ p$
=>time complexity =$O(logn)$
``` pseudo=
ans = 1
mod(m,n,p,ans){
    if n==0
        return ans
    if n%2==1            //n一定會等於1,所以至少跑一次=>可以把m轉移到ans上
        ans=(ans*m)%p
    n=n/2
    m=(m*m)%p
    mod(m,n,p,ans)
}

```