\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\num}[1]{\mbox{{\em num}}[#1]}
\newcommand{\numnoargs}{\mbox{{\em num}}}
\newcommand{\btrsearch}{{\sc B-Tree-Search}}

\head{3390}{Analysis of Algorithms}{Spring 1999}{7 June 1999}{26}

\begin{center}
\Large{\bf Hints for Practice Problems}
\end{center}

{\bf 1.} For part (a), take the maximum of the first and last elements.  For
part (b), use divide-and-conquer to find the element in the ``middle'' that is
the smallest one.  For part (c), first use part (b) to find the minimum
element.  This divides the given sequence into two sorted lists.  Find the
median of the two lists using POW-3.

{\bf 2.} In an optimal solution $S$, let, if possible, $A$ be paired to $C$
and $B$ be paired to $D$.  Then, consider the following $S'$ in which we pair
$A$ with $B$ and $C$ with $D$ and the rest as in $S$.  Let $h(A)$, $h(B)$,
$h(C)$, and $h(D)$ denote the heights of $A$, $B$, $C$, and $D$, respectively.
We can see that the difference between the cost of $S'$ and the cost of $S$
equals $|h(A) - h(B)| + |h(C) - h(D)| - |h(A) - h(C)| - |h(B) - h(D)|$, which
can be shown to be at most $0$ if $A$ and $B$ are the tallest woman and man,
respectively.  This completes part (a).

For part (b), we repeatedly pair the next tallest man with the next tallest
woman.

{\bf 3.} Statement (a) is false.  Consider a triangle with 3 vertices and 3
edges, each edge of weight $1$.  Each pair of vertices is $1$ apart.  However,
in any MST, the shortest path length between two of the vertices is $2$.

Statement (b) is true.  One can prove it by a cut and paste argument.

Statement (c) is false.  Immediately after relaxing edge $(u,v)$, it is
certainly true that $d[v] \le d[u] + w(u,v)$.  However, during any iteration
of Bellman-Ford, one may relax edge $(u,v)$ and then go on to relax some edge
coming into $u$, say $(x,u)$, and end up decreasing $d[u]$.  This decrease in
$d[u]$ may make $d[v] > d[u] + w(u,v)$ at the end of the particular
iteration.  One can construct a simple counterexample.

{\bf 4.} We can determine whether a box nests in another box by simply sorting
all the dimensions of each box and checking to see whether each dimension of
one box is less than each dimension of the other.  If so, then the ``smaller''
one nests inside the other.  

We can find the longest sequence of nestable boxes by constructing the
following graph $G$.  Have one vertex for each box.  If box $B_i$ nests inside
box $B_j$, then add an edge from $B_i$ to $B_j$.  Add two distinguished
vertices $s$ and $t$.  Add an edge from $s$ to each $B_i$ and from each $B_i$
to $t$.  Let all of the edges have weight $-1$.  Now simply find the shortest
path from $s$ to $t$.  It is easy to see that if remove the source $s$ and
destination $t$ from this path, we obtain a sequence of nestable boxes.  Since
the weights are set to be negative and the path is a shortest path, the
sequence of nestable boxes is the longest.  (Note that there are no negative
weight cycles in the graph.) 

We can use the Bellman-Ford algorithm to solve the above shortest-path problem
in time $O(VE) = O(n^3)$.

We can also directly solve the above problem using dynamic programming in
$O(n^2)$ time.

{\bf 5.} Given any positive integer $k$, we will first solve the problem: can
$k$ reporters cover all of the events in the Olympiad?  Then, we can go
through the values of $k$ from $1$ onwards and find the smallest $k$ for which
we find that $k$ reporters can cover all the events.

To find out whether $k$ reporters suffice, construct the following flow
network.  For each event $E_i$, have two nodes $b_i$ and $e_i$ -- these stand
for the start of event $E_i$ and the end of event $E_i$.  For any two events
$E_i$ and $E_j$, if any reporter can cover event $E_j$ after covering event
$E_j$, have an edge from $e_i$ to $b_j$.  All of these edges have capacity
$1$.  Next add $4$ new vertices, $s$, $s'$, $t$, and $t'$.  Have an edge from
$s$ to $s'$ of capacity $k$ and an edge from $t'$ to $t$ of capacity $k$.
Also, have an edge from $s'$ to each $b_i$ and set the capacity to be $1$.
And have an edge from each $e_i$ to $t$ with capacity $1$.

The vertices $s$ and $t$ are the source and sink, respectively.  The vertices
$s'$ and $t'$ are there to enforce the $k$ reporter constraint.  Note that
{\em we do not have any edge from $b_i$ to $e_i$} for any $i$.  It is tempting
to add an edge from $b_i$ to $e_i$ for each $i$ and seek the maximum flow.
Then if we get a flow of size $k$, one may be tempted to conjecture that the
$k$ paths correspond to the $k$ reporters and we can find out which reporter
covers which event.  The problem with this approach is that we are not {\em
guaranteed that flow will go through all of the $(b_i, e_i)$ edges}.  This is
what makes the problem hard to tackle.  We need to somewhow enforce that all
the events are covered.

Rather than adding an edge from $b_i$ to $e_i$ for each $i$, we make the
following changes to the above graph.  We add an edge from $s$ to each $e_i$
and an edge from each $b_i$ to $t$, each edge of capacity $1$.  This completes
the description of the flow network.

The sum of the capacity of the edges coming out from $s$ (similarly, coming
into $t$) is $n + k$.  We now claim that $k$ reporters can cover all of the
events in the Olympiad if and only if the maximum flow in the above network is
$n + k$.  Note that the proof of this claim completes our task.  This is
because all we need to do is to run a maximum flow algorithm on the given flow
network and see whether the maximum flow is $n + k$ or less.

We now prove the only if direction.  Suppose $k$ reporters can cover all of
the events in the Olympiad.  Then we can send the following $n + k$ flows of
unit size from $s$ to $t$: (i) If a reporter covers events $E_{i_1}$,
$E_{i_2}$, \ldots, $E_{i_j}$, then we send a unit flow from $s$ to $s'$ to
$b_{i_1}$ to $e_{i_1}$ to $b_{i_2}$ to $e_{i_2}$, and so on, and finally
through $b_{i_j}$ to $e_{i_j}$ to $t'$ to $t$, and (ii) for each event $E_i$,
we send a flow $s$ to $e_i$ to $b_i$ to $t$.  Note that all of the flows in
(i) are using edges of the form $(b_i, e_i)$, which do not exist!  But flows
along these edges are canceled by the flows of type (ii).  The total amount of
flow in (i) and (ii) is $n + k$.  This completes the proof.

Now consider the if direction.  Let $f$ be a flow of size $n + k$ from $s$ to
$t$.  Clearly, there is a flow of $1$ unit along each of the edges $(s, e_i)$
and of $k$ units along the edge $(s,s')$ that goes on through $k$ of the $n$
$b_i$'s.  Similarly, there is a flow of $1$ unit along each of the edges
$(b_i, t)$ and of $k$ units along the edge $(t',t)$ that has come from $k$ of
the $n$ $e_i$'s.  We subtract from this flow a flow of $n$ units, along
the path $s$ to $e_i$ to $b_i$ to $t$ for each $i$.  This leaves us with a
flow of $k$ units in a residual network in which we have an edge from $b_i$ to
$e_i$ for each $i$ and there is a unit of flow along each such edge!
Therefore, this implies that there are $k$ units of flow going from $s$ to
$s'$ to the $b_i$'s through the $e_i$'s to $t'$ to $t$.  This flow passes
through each $(b_i, e_i)$ pair.  We can easily decompose this flow into $k$
paths, each of which corresponds to the coverage of a reporter.

\end{document}