\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Spring 2004\\
\rm
Homework 11b\\
Due on 4/13/04\\
\end{center}
\begin{enumerate}
\item \textbf{[10 points] Investigating Ones Cuts (Yum)!}

Suppose someone gave you an original graph $G$ and its residual $G_r$,
and that $G_r$ had no path from $s$ to $t$. 
Suggest how you would modify BFS or DFS to:
\begin{enumerate}
\item Return sets $S$ and $T$.
\item Return the set of edges in the minimum capacity cut.
\end{enumerate}
Either pseudo-code or a description in English is fine. Keep your
writeup brief. We're looking for the big-idea here, not the crossed
t's and dotted i's.




\item 
\textbf{[25 points] Space Shuttle Profit Optimization!}

After successful careers at Millisoft, Hurts Car Rental,
and the brokerage firm of Weil, Proffet, and Howe, you've
been hired by NASA to help optimize their Space Shuttle
program.

On a given mission, NASA will consider a set of
experiments that industrial sponsors would like to conduct
(for example, ``Does gravity affect Spam?'').  Let $E = \{
E_{1}, E_{2},
\ldots, E_{m} \}$ denote the set of experiments under
consideration.  Let $p_{j}$ denote the amount of money the
sponsor will pay to conduct experiment $E_{j}$.  The
experiments use a set $I = \{I_{1}, I_{2}, \ldots, I_{n}
\}$ of instruments to conduct the experiments.  For each
experiment $E_{j}$, let $R_{j}$ be the subset of $I$ that
contains all of the instruments needed to conduct
experiment $E_{j}$.  Notice that this allows a single
instrument to be used in multiple experiments.  The
instruments are potentially large and heavy and the cost
of taking instrument $I_{k}$ is $c_{k}$ dollars.  Your job
is to determine which experiments should be performed in
order to maximize the net revenue, which is the total
income from the performed experiments minus the total cost
of all instruments carried.  Amazingly, this problem can
be solved using {\bf network flow}!

We'll construct a network flow problem as follows: The
network contains a source vertex, $s$, vertices $I_{1},
I_{2}, \ldots, I_{n}$, vertices $E_{1}, E_{2},
\ldots, E_{m}$, and a sink vertex $t$.
For each instrument $I_{k}$ there is a directed edge from
$s$ to vertex $I_{k}$ with capacity $c_{k}$ (the cost of
taking this instrument).  For each experiment $E_{j}$
there is an edge from vertex $E_{j}$ to $t$ with capacity
$p_{j}$ (the payment for this experiment).  Finally, if
instrument $I_{k}$ is in set $R_{j}$ (meaning that
instrument $I_{k}$ is needed for experiment $E_{j}$) then
there is a directed edge from vertex $I_{k}$ to vertex
$E_{j}$ with {\bf infinite} capacity.

\begin{enumerate}

\item 
First, try this.  Consider a situation in which there are
three experiments $E_{1}, E_{2}, E_{3}$ which will bring
in $10$, $6$, and $6$ dollars, respectively.  Also there
are four instruments $I_{1}$, $I_{2}$, $I_{3}$, and
$I_{4}$ which cost $3$, $2$, $5$, and $7$ dollars,
respectively to take on the shuttle.  Experiment $E_{1}$
requires instruments $I_{1}$ and $I_{2}$, experiment
$E_{2}$ requires instruments $I_{1}$ and $I_{3}$, and
experiment $E_{3}$ requires instruments $I_{3}$ and
$I_{4}$.  Using brute-force, enumerate all seven possible
combinations of experiments that could be taken and
determine which combination is the most profitable.  What
is this combination and what is the net revenue?



\item 
For the example problem above, construct the corresponding
network flow problem.  Find the maximum flow in the
network (show your residual graphs at each step) and then
find the corresponding cut whose capacity is equal to this
flow.



\item 
Let's let $S$ denote the vertices that are on the same
side of the above cut as vertex $s$ and let $T$ denote the
vertices that are on the same side of the cut as $t$.
What do you notice about the instruments and experiments
that are in the set $T$?



\item 
Now, let $\tau$ be the sum of the payments that NASA would
receive for taking all of the possible experiments.  In
this case, $\tau = 10 + 6 + 6 = 22$.  From $\tau$,
subtract the capacity of the cut you found above.
Surprise!  What is this number and how does it appear to
relate to this problem?



\item 
Finally, we're ready to generalize all of this into an
efficient algorithm for solving the profit maximization
problem in general.  Assume that we've set up a network
flow problem corresponding to a given set of experiments
and instruments.  Prove that for any cut with finite total
capacity, if an experiment $E_{j}$ is in $T$ (the side of
the cut containing vertex $t$), then all of the
instruments used in this experiment must {\bf also} be in
$T$.  Be careful and precise.



\item 
Now prove that the maximum net revenue that can be
achieved is simply the total sum $\tau$ of the payments
that would be received for taking all of the experiments
minus the capacity of the cut found by a network-flow
algorithm.



\item 
Now summarize all of this step-by-step, producing a
general purpose algorithm for:
\begin{enumerate}
\item 
Finding the maximum net revenue, given a set of
experiments, instruments, and the corresponding payments
and costs.
\item 
Specifying which experiments should be run to obtain this
revenue.
\end{enumerate}
Derive the worst-case running time of the algorithm
assuming there are $m$ experiments and $n$ instruments
(use these variables in your final run-time analysis
instead of $V$ and $E$).



\end{enumerate}

\item \textbf{[20 Points] FUHLishness!}  

The Harvey Mudd {\bf F}aculty {\bf U}nicycle {\bf H}ockey
{\bf L}eague (FUHL) has four teams numbered 1 through 4.
Each team has lost a certain number of games so far, as
shown in Table~1 below, and has a certain number of games
remaining against the other teams in the league, as shown
in Table~2.

Aside: for those of you that are latex-ing your solutions,
you can download the eps file that contains these tables
via:
\begin{center}
{\tt http://www.cs.hmc.edu/courses/2004/spring/cs140/homework/nw\_fuhl.eps}
\end{center}
\begin{center}
\epsfig{file=nw_fuhl.eps,width=4in}
\end{center}

The league champion is the team with the minimum number of
losses at the end of the season.  We wish to know if Team
4 has any hope of being the league champion, in spite of
the fact that it has lost so many games already.

\begin{enumerate}
\item 
Show how this problem can be cast as a network flow
problem by constructing the corresponding flow network.



\item 
Now solve the network flow problem.  For each iteration of
the algorithm, show the residual graph and the flow in the
network so far.



\item Use the maximum flow to determine a scenario (which
teams win and lose) in which Team 4 is the league champion.


\end{enumerate}

\item \textbf{[25 points] And Yet More Network Reliability!}

%Next time: say something about explicitly using N/W Flow?
%Lead them thru the undir->dir case?

Give an efficient algorithm for the \emph{s,t-connectivity
problem} and argue that it is correct.  The
\emph{s,t-connectivity problem} is defined as follows:
given a directed or undirected graph $G = (V,E)$ and
elements $s, t \in V$, $s \neq t$, decide if there exists
$k$ edge-disjoint paths from $s$ to $t$ and if so, find
them.


\end{enumerate}
\end{document}
