---
# System prepended metadata

title: 演算法作業 CH03
tags: [algorithm, learning, neopolitan]

---

###### tags: `learning` `algorithm` `neopolitan`

# 演算法作業 CH03

## ch 3-5 Floyd-Warshall algorithm 
- The source code
    - https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_5.py
- The step-by-step result
    - https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_5.py.out
- The D matrix
\begin{bmatrix}
0& 4& 24& 2& 4& 10& 10\\
3& 0& 24& 2& 4& 20& 10\\
6& 6& 0& 2& 4& 40& 10\\
6& 5& 24& 0& 2& 19& 5\\
12& 10& 12& 1& 0& 38& 10\\
24& 20& 48& 4& 8& 0& 10\\
12& 10& 24& 2& 4& 38& 0\\
\end{bmatrix}
- The P matrix
\begin{bmatrix}
-1& -1& 4& 4& 3& -1& 3\\
-1& -1& 4& 4& 3& 0& 3\\
1& -1& -1& 4& 3& 1& 3\\
1& -1& 4& -1& -1& -1& -1\\
3& 3& -1& -1& -1& 3& 3\\
6& 6& 6& 6& 6& -1& -1\\
3& 3& 4& 4& 3& 3& -1\\
\end{bmatrix}

## ch 3-10 Floyd-Warshall algorithm on negative weights
- For a directed weighted graph with positive weights, a shortest path is always a simple path.  So both of them can be determined by Floyd's algorithm. 
- For a directed weighted graph with some negative **without** any negative cycles, a shortest path is always a simple path.  So both of them can be determined by Floyd's algorithm. As we can see, the principle of optimality is still valid, even if there are some negative weights.
- For a directed weighted graph **with** negative cycles, a (non-simple) path can be even shorter when it goes through a negative cycle one more time. As a result, a shortest path is not well defined. 
    - For the case of finding shortest simple paths in a graph with negative cycles, Floyd's algorithm will **not** work, because the principle of optimization breaks.
        - Consider the following graph.   
        The shortest simple paths are $\{v1, v2, v4, v5, v7\}$ and $\{v1, v2, v4, v6, v7\}$.   
        To check the validity of principle of optimization, we now consider the path $\{v1, v2, v4, v5, v7\}$ and break it, by going from $v1$ to $v5$, then from $v5$ to $v7$.   
        The shortest simple path from $v1$ to $v5$ is $\{v1, v2, v4, v5\}$.  
        However, the shortest simple path from $v5$ to $v7$ is $\{v5, v3, v2, v4, v6, v7\}$.   
        So, the shortest simple sub-path is not included in tne shortest simple path, which  means the violation of principle of optimization.
```graphviz
digraph finite_state_machine {
	rankdir=LR;
	size="8, 5"
	node [shape = circle];
    
    v1_strart -> v2 [ label = "1" ];
	v2 -> v1_strart [ label = "1" ];
	
    v2 -> v4 [ label = "-100" ];
    
    v3 -> v4 [ label = "1" ];
    v4 -> v3 [ label = "1" ];
    
    v2 -> v3 [ label = "1" ];
	v3 -> v2 [ label = "1" ];
    
	v4 -> v5 [ label = "1" ];
    v5 -> v4 [ label = "1" ];
    
    v3 -> v5 [ label = "1" ];
    v5 -> v3 [ label = "1" ];
    
	v4 -> v6 [ label = "1" ];
    v6 -> v4 [ label = "1" ];
    
	v5 -> v7_end [ label = "1" ];
    v7_end -> v5 [ label = "1" ];
    
    v6 -> v7_end [ label = "1" ];
	v7_end -> v6 [ label = "1" ];
}
```

|Floyd algorithm|shortest path |shortest simple path|
|:-:|:-:|:-:|
|**positive weights**|✔|✔|
|**some negative weights without negative cycles**|✔|✔|
|**some negative weights with negative cycles**|not well-defined|✖<br>(violation of principle of optimization)|
---
## ch 3-13 Chained matrix multiplication
- The source code
    - https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_13.java

- The step-by-step output
    - https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_13.java.out

- The M matrix
\begin{bmatrix}
    0&   200&  1200&   320&  1320\\
    &     0&   400&   240&   640 \\
    &     &     0&   200&   700 \\
    &     &     &     0&  2000 \\
    &     &     &     &     0 \\
\end{bmatrix}
- The P matrix
\begin{bmatrix}
    &   1&  1&   1&  4\\\
    &     &   2&   2&   4 \\
    &     &     &   3&   4 \\
    &     &     &     &  4 \\
    &     &     &     &      \\
\end{bmatrix}
- The opimal order
\begin{equation}
(\;(\;A_1\;(\;A_2\;(A_3A_4)\;)\;)\;A_5\;)
\end{equation}

## ch 3-22

- The source code
https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_22.java

- The step-by-step output
https://github.com/y56/algo_neapolitan_exercises/blob/master/ch3_22.java.out
- A optimal  binary search tree, with a cost of $1.8$ 
```graphviz
digraph G {
    nodesep=0.4; //was 0.8
    ranksep=0.5;

    {node[style=invis,label=""]; cx_30;
    }
    {node[style=invis, label="", width=.1]; ocx_45; ocx_20;
    }

    {rank=same; ELSE; THEN; cx_30}
    {rank=same; CASE; END; ocx_20}
    {rank=same; OF; ocx_45}

    IF -> ELSE;
    IF -> THEN;
    ELSE -> CASE;
    ELSE -> END;

    THEN -> OF;

    {edge[style=invis];
                        //Distantiate nodes
                        IF -> cx_30;
                            ELSE -> cx_30 -> OF;

                        //Force ordering between children
                        THEN -> ocx_45;
                            OF -> ocx_45;
                        ELSE -> ocx_20;
                            CASE -> ocx_20 -> END;
    } 
} 
```
## Number of binary search trees (BSTs) for N keys
### Mapping from BTSs to pairs of parentheses
- We first map "a BST of $N$ keys" to "$N$ pairs of parentheses which are correctly matched". The mapping rules are:
    - Every node represents a pair of (parental) parentheses.
    - The left node represents a pair _**in**_ the (parental) pair.
    - The right node represents a pair _**on the right**_ of the (parental) pair.
- The construction processes of a sequence of pairs of parentheses according to a BST are:
    - Starting from the root, creat the 1st pair of parentheses.
    - If left key exsits, put one pair _**in**_ the (parental) pair.
    - If right key exsits, put one pair _**on the right**_ of the (parental) pair.
    - etc.
### Mapping from pairs of parentheses to a lattice path
- A sequence of $N$ pairs of (legal) parentheses can be mapped to a monotonic lattice path on a $N \times N$ grid. The consequent monotonic lattice path does not pass above the diagonal.
    - The mapping can be easily explained by:
        - A open parenthesis stands for going right, $R$.
        - A close parenthesis stands for going up, $U$.
### Number of  monotonic paths without passing above the diagonal
- Any **illegal** monotonic paths will pass above the diagonal.   
To count those illegal monotonic paths, we flip between U and R after the first illegal step.   
    - For example, the illegal path $RUURRU$ has its first illegal step $RU[U]RRU$.   
We flip after the illegal step and obtain at $RU[U]UUR$.
- It can be shown that all the processed illegal paths will terminate at the coordinate $(N-1, N+1)$. As the number of monotonic paths from $(0, 0)$ to $(N-1, N+1)$ is $\tbinom{2n}{n-1}=\tbinom{2n}{n+1}$, same as the number of illegal monotonic paths in $N \times N$ grid. Also, there are totally $\tbinom{2n}{n}$ monotonic paths in $N \times N$ grid. So, the number of legal monotonic paths in $N \times N$ is 
\begin{equation}
    {2n\choose n}-{2n\choose n+1}={1\over n+1}{2n\choose n}.
\end{equation}
### Examples

- $N = 1$ &nbsp;&nbsp;&nbsp; $()$  &nbsp;&nbsp;&nbsp; $RU$
```graphviz
digraph finite_state_machine {
	rankdir=LR;
	size=", 0."
	node [shape = circle, fixedsize=true];
    
    a[ label = "()" ];
}	
```
- $N = 2$ &nbsp;&nbsp;&nbsp; $(())$  &nbsp;&nbsp;&nbsp; $RRUU$
```graphviz
digraph finite_state_machine {
	rankdir=UD;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; 
        bb}
	node [shape = circle, fixedsize=true];

    
    a[ label = "()" ];
    b[ label = "(())" ];
    a -> b [ label = "" ];
    {edge[style=invis];
    a -> bb [ label = "" ];
    b -> bb;
    }
    {rank=same; b; bb}
}	
```
- $N = 2$ &nbsp;&nbsp;&nbsp; $()()$  &nbsp;&nbsp;&nbsp; $RURU$
    
```graphviz
digraph finite_state_machine {
	rankdir=UD;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; 
        bb}
	node [shape = circle, fixedsize=true];
    
    a[ label = "()" ];
    b[ label = "()()" ];
    a -> b [ label = "" ];
    {edge[style=invis];
    a -> bb [ label = "" ];
    b -> b;
    }
    {rank=same; b; bb}
}	
```
- $N = 3$ &nbsp;&nbsp;&nbsp; $((()))$  &nbsp;&nbsp;&nbsp; $RRRUUU$
![](https://i.imgur.com/m1zDclD.png)

```graphviz
digraph finite_state_machine {
	rankdir=U;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; bb; cc}
	node [shape = circle, fixedsize=true];
    a[ label = "()" ];
    b[ label = "(())" ];
    c[ label = "(())" ];
    a -> b [ label = "" ];
    b -> c ;
    {edge[style=invis];
    a -> bb [ label = "" ];
    b -> bb;
    b -> cc;
    c -> cc;    }
    {rank=same; b; bb}
    {rank=same; c; cc}
    
}	
```
- $N = 3$ &nbsp;&nbsp;&nbsp; $(()())$  &nbsp;&nbsp;&nbsp; $RRURUU$
![](https://i.imgur.com/btWwabk.png)
```graphviz
digraph finite_state_machine {
	rankdir=U;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; bb; cc}
	node [shape = circle, fixedsize=true];
    a[ label = "()" ];
    b[ label = "(())" ];
    c[ label = "()()" ];
    a -> b [ label = "" ];
    b -> c ;
    {edge[style=invis];
    a -> bb [ label = "" ];
    b -> bb;
    b -> cc;
    cc -> c;    }
    {rank=same; b; bb}
    {rank=same; c; cc}
    
}	
```
- $N = 3$ &nbsp;&nbsp;&nbsp; $()(())$  &nbsp;&nbsp;&nbsp; $RURRUU$
![](https://i.imgur.com/ZcSzcRH.png)
```graphviz
digraph finite_state_machine {
	rankdir=U;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; bb; cc}
	node [shape = circle, fixedsize=true];
    a[ label = "()" ];
    b[ label = "()()" ];
    c[ label = "(())" ];
    a -> b [ label = "" ];
    b -> c ;
    {edge[style=invis];
    a -> bb [ label = "" ];
    bb -> b;
    b -> cc;
    c -> cc;    }
    {rank=same; b; bb}
    {rank=same; c; cc}
    
}	
```
- $N = 3$ &nbsp;&nbsp;&nbsp; $()()()$  &nbsp;&nbsp;&nbsp; $RURURU$
![](https://i.imgur.com/0F5d0Sr.png)
```graphviz
digraph finite_state_machine {
	rankdir=U;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
    {node[style=invis,label=""]; bb; cc}
	node [shape = circle, fixedsize=true];
    a[ label = "()" ];
    b[ label = "()()" ];
    c[ label = "()()" ];
    a -> b [ label = "" ];
    b -> c ;
    {edge[style=invis];
    a -> bb [ label = "" ];
    bb -> b;
    b -> cc;
    cc -> c;    }
    {rank=same; b; bb}
    {rank=same; c; cc}
    
}	
```
- $N = 3$ &nbsp;&nbsp;&nbsp; $(())()$  &nbsp;&nbsp;&nbsp; $RRUURU$
![](https://i.imgur.com/37vP5Or.png)
```graphviz
digraph finite_state_machine {
	rankdir=U;
	size="8, 5";
    nodesep=0.9; //was 0.8
    ranksep=0.1;
	node [shape = circle, fixedsize=true];
    a[ label = "()" ];
    b[ label = "(())" ];
    bb[ label = "()()" ];
    a -> b [ label = "" ];
    a -> bb [ label = "" ];
    {rank=same; b; bb}    
}	
```

## ch 3-39
Let us consider two sequences of characters `S1` and `S2`. 
For example, we could have `S1 = A$CMA*MN` and `S2 = AXMC4ANB`. 
Assuming that a subsequence of a sequence can be constructed by deleting any number of characters from any positions, 
use the dynamic programming approach to create an algorithm that finds the longest common subsequence of `S1` and `S2`.
This algorithm returns the maximum-length common subsequence of each
sequence.


