\handout{Homework 8,  Due Friday,  December 4, 2020} 
\bigskip

\bigskip

On all problems provide justification of your answers.   Provide a clear explanation of why your algorithm solves the problem, as well as a justification of the run time.   

\problem{1 (10 points)} (Page 324, Exercise 13.)
The problem of searching for cycles in graphs arises naturally in financial
trading applications. Consider a firm that trades shares in $n$ different
companies. For each pair $i \ne j$, they maintain a trade ratio $r_{ij}$, meaning
that one share of $i$ trades for $r_{ij}$ shares of $j$. Here we allow the rate $r$ to be
fractional; that is, $r_{ij} = {2\over 3}$ means that you can trade three shares of $i$ to get
two shares of $j$.
\medskip

A {\it  trading cycle} for a sequence of shares $i_1, i_2, \ldots, i_k$ consists of
successively trading shares in company $i_1$ for shares in company $i_2$, then
shares in company $i_2$ for shares $i_3$, and so on, finally trading shares in $i_k$
back to shares in company $i_1$. After such a sequence of trades, one ends up
with shares in the same company $i_1$ that one starts with. Trading around a
cycle is usually a bad idea, as you tend to end up with fewer shares than
you started with. But occasionally, for short periods of time, there are
opportunities to increase shares. We will call such a cycle an {\it opportunity}
cycle, if trading along the cycle increases the number of shares. This
happens exactly if the product of the ratios along the cycle is above 1. In
analyzing the state of the market, a firm engaged in trading would like
to know if there are any opportunity cycles.

\medskip

Give a polynomial-time algorithm that finds such an opportunity
cycle, if one exists.

\problem{3 (10 points) Word segmentation}  (This problem is based on problem 5 on Page 316 of the text without the excessive verbiage.)  The word segmentation problem is: given a string of characters $Y=y_1y_2\ldots y_n$,  optimally divide the string into consecutive characters that form words.  (The motivation is that you are given at text string without spaces and have to figure out what the words are.  For example,  {\it ``meetateight''} could be {\it ``meet ate ight'',  ``me et at eight''} or {\it ``meet at eight''.})  The problem is to find best possible segmentation.  We assume we have a function {\it Quality} which returns an integer value of the goodness of a word, with strings that correspond to words getting a high score and strings that do not correspond to words getting a low score.  The overall quality of a segmentation is the sum of the qualities of the individual.

\medskip
Give an dynamic programming algorithm to compute the optimal segmentation of a string.
You can assume that calls to the function {\it Quality} take constant time and return an integer value.



\problem{3 (10 points)} The Chvatal-Sankoff constants are mathematical constants that describe the length of the longest common subsequences of random strings.  Given parameters $n$ and $k$, choose two length $n$ strings $A$ and $B$ from the same $k$-symbol alphabet,  with each character chosen uniformly at random.  Let $\lambda_{n,k}$ be the random variable whose value is the length of the longest common subsequence of $A$ and $B$.  Let $E[\lambda_{n,k}]$ denote the expectation of  $\lambda_{n,k}$.  The Chvatal-Sankoff constant $\gamma_k$ is defined at $$\gamma_k = \lim_{n\rightarrow \infty} {E[\lambda_{n,k}] \over n}.$$

Experimentally determine (by implementing an LCS algorithm), the smallest value of $k$, such that $\gamma_k < {2\over 5}$.  In other words determine how large an alphabet needs to be so that the expected length of the LCS of two random strings is less than 40\%  the length of the strings.


\problem{4 (10 points)}
In a standard $s-t$ Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node.  In this problem, we consider the variant of the Maximum-Flow problem with node capacities.

\medskip

Let $G=(V,E)$ be a directed graph, with source $s\in V$, sink $t\in V$, and nonnegative node capacities $\{c_v\ge 0\}$ for each $v\in V$.  Given a flow $f$ in this graph, the flow through a node $v$ is defined as $f^{\mbox{in}}(v)$, the sum of the flows on the incoming edges to $v$.  We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: $f^{\mbox{in}}(v) \le c_v$ for all nodes.

\medskip

Give a polynomial-time algorithm to find an $s-t$ maximum flow in such a node-capacitated network.  Justify the correctness of your algorithm.  (Note and hint: you may call an $O(n^3)$ subroutine for the standard network flow problem

\vfill\eject

\problem{5 (10 points)}

Consider the following flow graph.  Find a maximum flow.  

\def\bb{\makebox(0,0){$\bullet$}}
\setlength{\unitlength}{0.4in}
\begin{center}
\begin{picture}(10,11)
\multiput(0,10)(0,-2){5}%
{\multiput(0,0)(2,0){5}{\bb\vector(0,-1){1.95}\vector(1,0){1.95}}\put(10,0){\bb}}
\multiput(0,10)(2,0){5}{\bb\vector(1,0){1.95}}
\multiput(10,10)(0,-2){5}{\vector(0,-1){1.95}}
\multiput(0,0)(2,0){5}{\bb\vector(1,0){1.95}}
\put(10,0){\bb}
\multiput(0.2,9)(2,2){1}{\makebox(0,0){20}}
\multiput(1,10.2)(2,2){1}{\makebox(0,0){20}}
\multiput(0.2,7)(2,2){2}{\makebox(0,0){10}}
\multiput(1,8.2)(2,2){2}{\makebox(0,0){10}}
\multiput(0.2,5)(2,2){3}{\makebox(0,0){6}}
\multiput(1,6.2)(2,2){3}{\makebox(0,0){6}}
\multiput(0.2,3)(2,2){4}{\makebox(0,0){4}}
\multiput(1,4.2)(2,2){4}{\makebox(0,0){4}}
\multiput(0.2,1)(2,2){5}{\makebox(0,0){3}}
\multiput(1,2.2)(2,2){5}{\makebox(0,0){3}}
\multiput(1,0.2)(2,2){5}{\makebox(0,0){4}}
\multiput(2.3,1)(2,2){5}{\makebox(0,0){4}}
\multiput(3,0.2)(2,2){4}{\makebox(0,0){5}}
\multiput(4.2,1)(2,2){4}{\makebox(0,0){5}}
\multiput(5,0.2)(2,2){3}{\makebox(0,0){7}}
\multiput(6.2,1)(2,2){3}{\makebox(0,0){7}}
\multiput(7,0.2)(2,2){2}{\makebox(0,0){10}}
\multiput(8.2,1)(2,2){2}{\makebox(0,0){10}}
\multiput(9,0.2)(2,2){1}{\makebox(0,0){20}}
\multiput(10.2,1)(2,2){1}{\makebox(0,0){20}}
\put(-0.2,10){\makebox(0,0){{\it s}}}
\put(10.2,0){\makebox(0,0){{\it t}}}

\end{picture}
\end{center}

\begin{itemize}

\item[a)] What is the value of the maximum flow?  Indicate the value of flow on each edge.


\item[b)] Prove that your flow is maximum.

\end{itemize}

\problem{6 (10 points)}
Decide whether you think the following statement is true or false.  If it is true, give a short explanation.  If it is false, give a counterexample.

\medskip
{\it
Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$ and a positive integer capacity $c_e$ on every edge $e$; and let $(A,B)$ be a minimum $s-t$ cut with respect to these capacities $\{c_e:e\in E\}$.  Now suppose we add 1 to every capacity; then $(A,B)$ is still a minimum $s-t$ cut with respect to these new capacities $\{1+c_e:e\in E\}$.
}