\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 11b\\
Due on 11/18/03 (in class)\\
\end{center}
\begin{enumerate}
\item \textbf{[6 Points] Remainder of Review of Network Flow Proofs.}
In class we proved four fundamental theorems which, in the end, allowed us to show that
our network flow algorithm does indeed find a maximum flow from $s$ to $t$.  
In this problem you will prove the Greed is Good Theorem, which states that 
a residual network for a flow $f$ has no augmenting path if and only if $f$ is a maximum flow.
Your proof should follow {\bf the argument presented in class} and can appeal to the the other
three theorems (i.e. Cut, Capacity, and Max-Flow Min-Cut Theorems).
Your grade will be based on how clearly and precisely you write this proof.



\item \textbf{[40 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$.



\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 minimum cut.




\item Now just summarize all of this by describing the
algorithm, step-by-step, for finding the maximum net revenue, given
a set of experiments, instruments, and the corresponding payments and
costs.  Give a careful derivation of the worst-case running time of
the algorithm assuming there are $m$ experiments and $n$ instruments.




\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.
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{center}
\epsfig{file=fuhl.eps,width=4in}
\end{center}

\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}

\end{enumerate}
\end{document}
