\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage[all]{xy}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 11b\\
Due on Tuesday, 11/16/2004 (beginning of class)\\
\end{center}
\begin{enumerate}
\item 
\textbf{[6 Points] Review of Remaining Network Flow Proof.}

In class, we proved four fundamental theorems which, in the end, allowed us to
show that several network flow algorithms were correct.  For this assignment,
you will re-prove the last one, the Greed Is Good Theorem, {\bf as it was
presented in class}.



\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 (you
can assume the graphs are both represented as adjacency lists) 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. Also, briefly analyze
your approach's runtime. Keep your writeup short. We're looking for big-ideas,
not the crossed t's and dotted s'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 offered two jobs, one by NASA to help
them optimize their Space Shuttle program, and the other by Professor Lai to
help him get tenure. Your decision, of course, was no Lye.

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.  Then,
identify the most profitable combination (what experiments it runs, what
instruments are required, and what the overall profit is).



\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 performing
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
the most profitable combination of experiments, what instruments are required,
and what is the net revenue?



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

In both this and the next item, some students find it useful to use the
following notation: let $X_T$ be those vertices in instrument set $X$ that lie
in $T$ and $X_S$ be the remaining instruments (which must lie in
$S$). Similarly, let $Y_T$ be those vertices in experiment set $Y$ that lie in
$T$ and $Y_S$ be the remaining experiments (which must lie in $S$).



\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 performing all of the
experiments minus the capacity of the cut that would be found by one of our
network-flow algorithms.  Be careful and precise.



\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}
You should think about the choices you are making---try and make your approach
as fast as you can.  Then, derive the worst-case running time of your approach
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{[25 Points] Graph Partitioning!}  

Given an \emph{undirected} graph $G$, a \emph{partition} of the graph is a
division of the vertices $V$ into two sets $A$ and $B$ such that every vertex is in
exactly one of $A$ and $B$.  The only constraint on $A$ and $B$ is that neither
%CHANGE THIS NOTATION; crossing number in graph theory has to do with planarity
%graph DRAWING. Given this, the definition given here is confusing (and at worst, wrong).
set can be empty. The \emph{crossing number} of the partition is the number of
edges with one endpoint in $A$ and one endpoint in $B$.  Professor Minal Cutts
would like to find an algorithm which finds a partition with the smallest
possible crossing number. (Fast graph partitioning algorithms are used in a
variety of applications ranging from data clustering to circuit design.)

\begin{enumerate}
\item 
Describe your algorithm.  (You may use existing algorithms to help!)



\item Explain clearly why your algorithm is correct.



\item 
Derive the running time of your algorithm.  You should try and make your
algorithm as fast as you can (exponential time algorithms are unacceptable!).



\end{enumerate}
\end{enumerate}
\end{document}
