# COMP 3711 – Design and Analysis of Algorithms IV

2022 Fall Semester – Written Assignment 4
Distributed: November 14, 2022
Due: November 30, 2022, 23:59

Name: Kwong Cheuk Lam
SID: 20776617
Email: [e-mail]

**Implementation of Pseudocode of Q2-Q3:**
https://colab.research.google.com/drive/15xWgDTWnFu9h74Ofy8JOEkEIuX_OK-P1?usp=sharing

**Online version:**
https://hackmd.io/@j1Jsew7VSb-GQ9oE3SBz8g/ryw6TkCIj

**Collaborators:**

1. Lam Ho Wai ([e-mail])

### Question 1
#### Definition
Define $d(v)$ as the degree of node $v$.
Define $|V|$ be the number of vertices (nodes) in the graph $G(V,E)$.
Define $|E|$ be the number of edges in the graph $G(V,E)$.

#### a)

First, every vertex of G has a non-zero even degree, which means:
$2 \leq d(v), \forall v \in V$.
$\Rightarrow 2|V| \leq \sum_{v \in V}d(v) = \frac{1}{2}|E|$
$\Rightarrow |V| \leq |E|$
$\Rightarrow$ There is at least one cycle in G.

Secondly, we remove the edges in (one of the) cycle(s). After removing the edges, if the node has a degree zero, we remove that node too. Consider the followings:
1. Every node in that cycle will have an ancestor and descendant. We would reduce the degree of every node in the cycle by two. So all the node degrees remains even.
2. If the node originally has a degree of two, it would be removed.
3. The graph may be disconnected.

Then, we are left with a (dis)connected graph, with all vertices of the graph still have a non-zero even degree. We can repeat these two steps on the graph reducing some nodes' degree by 2 every time, until there is only one cycle in the graph, and all nodes have a degree of two. After removing it, we are left with an empty graph.

Since we only remove nodes that are in a cycle and all nodes have been removed, we can say all nodes in the graph are in some cycles.

#### b)
(canceled)

### Question 2

#### Description:

BFS can be used to find the shortest distance from a node $s$ to all other nodes in the graph $G$. We can therefore run BFS on each node once to find all the shortest distance between pairs of node in $G$.

For the sake of convenience, we denote each node with integer keys.
#### Pseudocode:
1. BFS algorithm
Input: The graph `G` and a starting node `s`$\in G$
Output: A list of distances of nodes in `G` from `s`.
Note: |V| is number of vertices in G

// We run bfs with initial node s, and will get the distances from s to all other nodes.
def bfs(G, s):

    // We first initialize all the nodes so that it is white,
    // meaning it is undiscovered by the bfs algo yet.
    // Also, the distance between s and other nodes are initialized as infinity (arbitrary number can do)
    for each vertex v in G:
        v.color <- white
        v.d <- ∞
        
    // Then, we declare that s is in color gray
    // meaning it has been discovered but the neightbours haven't been fully processed yet.
    // Also, the distance between itself is 0.
    s.color <- gray
    s.d <- 0

    // We initialize a resulting array to store the resulting distance between s to other nodes.
    res = [1...|V|]
    
    // We also initialize a FIFO queue to process the nodes that are discovered but not yet fully explored.
    initialize empty queue Q
    enqueue(Q, s)
            
    // We repeat the exploration until all nodes are explored.
    while Q ≠ ø do:
        // We pop the first node in the queue and process all its neightbours.
        u <- dequeue(Q)
            
        for each v in u.adj do:
            if(v.color = white) do:
                // If the neightbour is newly discovered:    
                // We set its color as gray and add it to the back of the queue
                v.color <- gray
                // The distance from s is one larger than the current vertex's distance
                v.d <- u.d + 1
                enqueue(Q, v)
                    
        // We turn the color of the node black after its fully explored.
        u.color <- black
        // We also add the distance to the resulting array
        res[u.key] <- u.d

    return res

2. Main algorithm
Input: The graph
Output: A 2D matrix `res`, where `res[i][j]` is the shortest distance between node i and node j in $w$.

def allPairShortestPath(G):
    // We initialize a 2d matrix for storing the result.
    res <- []
    
    // We loop through all the vertices to find all distances between them.
    for u in G.V:
      tempRes <- bfs(G, u))
      add tempRes to then end of res

    return res

#### Runtime:
1. bfs(G, s) in (1): Running time is $\sum_{u \in V} (1+deg(u)) = \Theta(|V|+|E|)$, which is $\Theta(|E|)$ if the graph is connected.
2. Line 3 - 5 in (2): We loop through the bfs for |V| times, the running time is $\mathcal{O}(|V||E|)$

The total runtime is $\mathcal{O}(|V||E|)$.

### Question 3
#### Description

First, we can observe the following property:
If $(x_i,x_j) \times (x_j,x_i) > 1$ $,\exists i, j \in [1, n]$, we can make a profit by
1. exchanging 1 unit of $x_i$ to $(x_i,x_j)$ unit of $x_j$.
2. exchanging $(x_i,x_j)$ unit of $x_j$ back to $(x_i,x_j) \times (x_j,x_i)$ unit of $x_i$.

Similarly,
If $(x_i,x_{n_1}) \times (x_{n_1},x_{n_2}) \times ... \times (x_{n_k},x_i) > 1$ $\exists n_1, n_2, ... n_k, i \in [1,n]$, we can make a profit by
1. exchanging 1 unit of $x_i$ to $(x_i,x_{n_1})$ unit of $x_{n_1}$.
2. exchanging $(x_i,x_{n_1})$ unit of $x_{n_1}$ to $(x_i,x_{n_1})\times (x_{n_1},x_{n_2})$ unit of $x_{n_2}$.
...
3. exchanging back to $(x_i,x_{n_1}) \times (x_{n_1},x_{n_2}) \times ... \times (x_{n_k},x_i)$ unit of $x_i$.

Also, we know that:
1. $\log(mn) = \log(m) + \log(n)$
2. $mn > l \Rightarrow \log(mn) > \log(l) \Rightarrow \log(m) + \log(n) > \log(l)$
3. $mn>1 \Rightarrow \log(m) + \log(n) > 0$

Then, we can make a profit if $\log(x_i,x_{n_1}) + \log(x_{n_1},x_{n_2}) + ... + \log(x_{n_k},x_i) > 0$
or equivalently, $-\log(x_i,x_{n_1}) - \log(x_{n_1},x_{n_2}) - ... - \log(x_{n_k},x_i) < 0$

Lastly, we can convert the above problem to a negative cycle detection problem in a directed graph. We assume each currency is a vertex in the graph while $-\log(x_i, x_j)$ is the weight of a directed edge from vertex $x_i$ to $x_j$. If there is any negative cycle in the graph, we can make a profit.

#### Algorithm

We can then use the Floyd-Warshall algorithm. We define $d_{ij}^{k}$ smallest -log amount of $x_j$ you can get from exchanging 1 unit of $x_i$ using currencies ${x_1, x_2 ... x_k}$, i.e. the shortest path from $x_i$ to $x_j$ using intermediate vertices on the path in the set ${x_1, x_2 ... x_k}$. And first, we want to find all pairs of shortest path.

Then consider a currency $x_k$, and should we include it to the shortest path from $x_i$ to $x_j$.
$d_{ij} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)}+d_{jk}^{(k-1)})$.

Lastly, assume there is a negative cycle in the graph. Let C be the smallest negative cycle and k be the highest number for $x_k \in C$.
Then, $d^k_{ii} = \min(d^{(k-1)}_{ii}, d^{(k-1)}_{ik}+d^{(k-1)}_{k_1}) < 0$. Since it is a negative cycle and $d^{(k+1)}_{ii}, ... , d^{n}_{ii}$ never increases, $d^n_{ii} < 0$.
Therefore, we can conclude that we can earn a profit if $\exists i, d^n_{ii} < 0$ produced by the Floyd-Warshall algorithm.

#### Pseudocode
1. Input
rate: A 2d matrix where `rate[i][j]` denotes $(x_i, x_j)$
n: number of currencies
2. Output
True if there is profit, False otherwise

Note: If the rate is missing, `rate[i][j]` should be zero and `-log(rate[i][j])` is infinity.

def exchangeProfit(rate, n):

  // taking log of all rates in the matrix elementwise
  rate <- -log(rate)

  // Floyd-Warshall algorithm
  for k in range(n):
      for i in range(n):
          for j in range(n):

              if(rate[i][k] + rate[k][j] < rate[i][j]):
                  rate[i][j] <- rate[i][k] + rate[k][j]
                  
  // output true if any of the diagonal is greater than 0
  for i in range(n):
    if(rate[i][i] < 0):
      return True
  return False

#### Runtime:
$\mathcal{O}(n^3)$

### Question 4
#### Definition
Consider A:
$A[i][j]$ denotes the non-negative real number in the $i$th row and $j$th column.
$SR_i$ denotes the sum of real numbers in the $i$th row.
$SC_j$ denotes the sum of real numbers in the $j$th column.
Define $SA$ as the sum of all entries in A, i.e. $SA = \sum_j{SC_j} = \sum_i{SR_i}$.
Where $i \in [1,n]$ and $j \in [1,m]$.

Similarly for B, if it exists
$B[i][j]$ denotes the non-negative integer in the $i$th row and $j$th column.
Since, by definition, B has the same sum as A in every row and every column, we can still use $SR_i$ and $SC_j$ to denote the row sum and column sum respectively.
Where $i \in [1,n]$ and $j \in [1,m]$.

#### Description:
First, consider A as a $1 \times 1$ matrix $(A[1,1])$, it is obvious that $B = (A[1,1])$. We can represent B as a graph:
The value above the edge is the flow of the edge. For example, the edge $(S, R_1)$ has a value of $SR_1$, meaning that the value $SR_1$ flows into the first row, or sum of first row is $SR_1$. From the graph, we can clearly see that $SR_1 = SC_1 = B[1][1] = A[1][1]$ in this case.

Then, let's consider the general case, where we do not know the actual value of flows $f(e)$. Construct a directed connected graph $G = (V, E)$, where every edge $e \in E$ has capacity $c(e)$ and it contains a source vertex $s$ and a target vertex $t$.
We set $c(e) = min(SR_i, SC_j)$ $,\forall e \in (R_i, B[i,j]) \bigcup (B[i,j], C_j)$. As $0 \leq B[i,j] \leq SR_i$ and $0 \leq B[i,j] \leq SC_j$. The entries must be smaller or equal to its row sum and column sum.
We set $c(e) = SR_i$ $,\forall e \in (s, R_i)$ and $c(e) = SC_j$ $,\forall e \in (C_j, t)$. The reason is to maximize the flow and will be discuss below.
Note that we also add dummy vertices from entries of B for our convenience.
The value below the edge is the capacity of the edge. To prove that such $B$ exists and $B$ can be represented by $G$ (denoted $G^*$), if and only if $G$ has the following flows:
1. Each row conserves its sum - (1)
$f((s, R_i)) = c((s, R_i)) = SR_i$.
2. Each column conserves its sum - (2)
$f((C_j, t)) = c((C_j, t)) = SC_j$.
3. All entries in B[i,j] is a non-negative integer - (3)
$f((R_i, B[i, j])) \in N$ and $f((B[i, j], C_j)) \in N$

$\forall i \in [1,n]$ and $\forall j \in [1,m]$

To prove such $G^*$ exists for any matrices $A$, we can consider the Ford-Fulkerson algorithm to find the maximum flow of $G$. Consider the following s-t cuts that divides the vertices to set $S$ and $T$.
1. Only vertex $s$ is in set $S$
$s \in S$
$c(S,T) = \sum_{i=1}^n{SR_{i}}$
2. Some $R_{i'}$ vertices are also in set $S$
$s \in S$ and $\exists R_{i'} \in S$
$c(S,T) = \sum_{i=1}^n{SR_i} - \sum_{i'}{SR_{i'}} + \sum_{i'}{\sum^m_{j=1}\min{(SR_{i'}, SC_j)}}$
If $SC_j < SR_{i'} \forall j$, ${\sum^m_{j=1}\min{(SR_{i'}, SC_j)}} = {\sum^m_{j=1}{SC_j}} = {SA} \geq {SR_{i'}}.$
Otherwise, ${\sum^m_{j=1}\min{(SR_{i'}, SC_j)}} \geq {SR_{i'}} \\ \text{}$
$\sum_{i'}{\sum^m_{j=1}\min{(SR_{i'}, SC_j)}} \geq \sum_{i'}{SR_{i'}}.$
$\Rightarrow c(S,T) \geq \sum_{i=1}^n{SR_{i}}$.

3. The $B[i',j]$ vertices are also in set $S$
$s \in S$ and $\exists R_{i'} \in S$ and $\exists B[i',j] \in S$
$c(S,T) = \sum_{i=1}^n{SR_i} - \sum_{i'}{SR_{i'}} + \sum_{i'}{\sum^m_{j=1}\min{(SR_{i'}, SC_j)}}$
$\Rightarrow c(S,T) \geq \sum_{i=1}^n{SR_{i}}$

4. Some $C_{j'}$ vertices are also in set $S$
$c(S,T) = \sum_{i=1}^n{SR_i} - \sum_{i'}{SR_{i'}} + \sum_{i'}{\sum^m_{j=1}\min{(SR_{i'}, SC_j)}} - {\sum_{j'}\min{(SR_{i'}, SC_{j'})}} + \sum_{j'}{SC_{j'}}$
Since $-{\sum_{j'}\min{(SR_{i'}, SC_{j'})}} + \sum_{j'}{SC_{j'}} > 0$
$\Rightarrow c(S,T) \geq \sum_{i=1}^n{SR_{i}}$

In fact, any arbitrary s-t cut has a capacity greater or equal to sum of all elements in the matrix A, i.e. $c(S,T) \geq SA, \forall (S,T)$. Then, by the property of maximum flow, G has a max flow that should be equal to the capacity of min-cut, i.e. $SA$.

Therefore, all edges from $s$ to $R_i$ and from $C_j$ to $t$ are of full capacity. And (1) and (2) is fulfilled. ($SA = \sum_j{SC_j} = \sum_i{SR_i}$)
Lastly, from the Integrality property of the F-F algorithm, since all the edge capacities are integers, there exists some $f(e)$ for which every flow value is an integer for the max flow. So, (3) is also fulfilled. In other words, $G^*$ exists for any A and we can convert $G^*$ to $B$.

Intuitively, we can distribute the sum of each row to m integral elements in a way that the sum of each column is conserved.

Hence, $G^*$ exists for any matrix A and $G^*$ can be used to represent $B$. $B$ exists for any matrix A.