\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Spring 2001}\\
\vspace{.3 in}
{\large Assignment 7}
\end{center}

\noindent
This assignment is due by the start of class on Tuesday, Mar 6.  You may collaborate
with your classmates to complete this assignment but you must reference your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 100 points (65 points if handwritten).  


\vspace{.2 in}
\begin{enumerate}

\item 

Problem 27-1 on page 625 of the  text.

To impose vertex flow constraints we can replace a single node $v$ with two
nodes $v$-in and $v$-out.  The in-edges of $v$ become in-edges to $v$-in and
the out-edges of $v$ become out-edges of $v$-out.  In addition we add an
edge from $v$-in to $v$-out with capacity equal to the vertex flow capacity of
$v$.

To solve the escape problem we design a flow network with both edge and vertex
flow constraints.  We replace the edges of the grid with bi-directional edges,
each with capacity 1.  We add a source and an edge with capacity 1 to every starting point in
the grid.
We add a sink and an edge with capacity 1 from every point on the boundary of the grid.
In addition we require that each vertex have capacity 1.  

The maximum flow of the network is $m$ iff there are disjoint paths from the starting
vertices to boundary points.

\item

Problem 27-2 on page 626 of the text.

Note that minimizing the number of paths in a path cover is equivalent to maximizing
the number of edges in the path cover.  The maximum flow in the network described in
the text is exactly the maximum number of edges that can exist in any path cover.

\item

Problem 27-3 on page 627 of the text.

Suppose that $E_j \in T$ for some finite capacity cut $(S,T)$.  Assume $I_k \in R_j$. So
there is an infinite capacity edge from $I_k$ to $E_j$ in the network.  If $I_k \in S$
then the cut $(S,T)$ has infinite capacity, which is a contradiction.  So $I_k \in T$.

Consider a minimum capacity cut $(S,T)$.  If we perform the experiments and buy the
instruments in $T$, then the edges crossing the cut are the costs of the instruments
we buy and the payments for the experiments we don't perform.  Minimizing this
sum is equivalent to maximizing our profit.








\end{enumerate}
\end{document}

