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