---
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.

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)$

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

將對角線設為$\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 |


So the d(i,j) values that we get are

# 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.




由圖可知插入edge(B,C)後,若(A,B)&(C,D)皆連通則(A,D),(A,C),(B,D)也會連通
總共檢查$V*V$次,所以時間複雜度為$O(V^2)$

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
在原本的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
...

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)$

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)
}