\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 10b\\
Due on 4/6/04 (beginning of class)\\
\end{center}
\begin{enumerate}
\item \textbf{[20 Points] Minimum Spanning Trees from the Shortest Paths Perspective!}

Show that a minimum spanning tree (MST) of an undirected
graph is equivalent to the \emph{bottleneck shortest
paths} tree (BSPT) for the graph. A BSPT has the following
property: For every pair of vertices $u$ and $v$, it gives
the path connecting them whose longest edge is as short as
possible. 


\item \textbf{[15 Points] Johnson's on the Move!} 

An inspiring thought occurs to Professor Lai at the
Pasadena Institute of Technology.  ``Perhaps I don't need
to add a dummy vertex at all to get Johnson's trick to
work.  Instead, chose $s$ to be some random vertex in the
original graph (i.e. don't add any new zero-weighted
edges). Rather, just run Bellman-Ford on vertex $s$ in this
original graph and then use these $h$ values to transform
the negative weights just like Johnson does.''  He gets so
excited about this idea---especially because it means
he'll get an algorithm named after him!---that he forgets
to look for a counter example.
\begin{enumerate}
\item 
Give a counter-example that demonstrates why this
algorithm is incorrect.
\item 
Show that if the original graph is \emph{strongly
connected}---i.e., each vertex is reachable from every
other vertex---then the results returned by Johnson's algorithm combined with
with Professor Lai's modification are correct.  It may be
convenient for you to assume that $\infty + a = \infty$ for any
finite number $a$.
\end{enumerate}



\item \textbf{[5 Points] Doh! This is A-Really-Simple One!} 

CLRS, Exercise 25.3-3 (page 640).
Give a mathematical proof of your answer!


\item \textbf{[30 Points]} {\bf Hurts' On-board Navigation System Revisited.}

Hurts Car Rental has designed a new generation of
alternative fuel vehicles.  The new vehicles use a special
fuel comprising a finely minced mixture of the
``Introduction to Algorithms'' textbook and daily Platt
left-overs. (Students have often remarked that Platt's food is an
excellent fuel source!)  Due to this rather unusual fuel requirement,
there are only certain cities in the country where the
vehicles can be refueled.
Thus, to get from the start city to the
destination city, the driver must plan a route that
ensures that the car can be refueled along the way.

Hurts, a very consumer-friendly company, insists that all of its
rental vehicles come with an on-board pre-programmed computer chip
that contains the solutions to the following {\bf Hurts Navigation
Graph Problem}: Given an arbitrary start city $s$ and destination city
$t$, determine the shortest route from $s$ to $t$ that ensures that
the vehicle doesn't run out of fuel (or report that no such route
exists).

You've been hired to develop an algorithm for computing
the solutions up front. You are given the following:
\begin{itemize}
\item 
A weighted, directed graph whose vertices
represent cities, directed edges represent one-way
roads, and edge weights represent the lengths
of the roads (obviously in this application, all weights
are non-negative).
Each city that contains one of these special fueling stations is
also indicated by flagging its corresponding vertex.
\item 
A fixed driving range representing how far Hurts rentals
can drive on a full tank of gas.
\item 
You may assume that start and
destination cities, being Hurts car rental cities, have
the requisite fuel stations. Furthermore, vehicles begin
with a full tank.
\item 
You can assume that there is some constant $C$ such that the number of
roads into and out of a given city is at most $C$.
Similarly, you can assume
there is some other constant $C'$ that upper bounds the number of
within-range fuel-cities that can be reached from any particular
fuel-city.
\end{itemize}

Your job is to solve the following:
\begin{enumerate}
\item 
Describe and analyze the running time of an efficient algorithm for
solving the {\bf Hurts Navigation Graph Problem}.  For full credit, your algorithm should be as
fast as possible.  (By the way, I'm not asking you to {\em prove} that
this algorithm is as fast as possible---in general such proofs are
really hard! Rather, this cautionary note is intended to encourage you
to think carefully about the various algorithmic choices you are
making.)  Your algorithm may be built up of one or more of the
algorithms which we have seen in class.



\item 
Briefly explain how, had the $C'$ assumption not been given, 
different algorithmic choices might have been more efficient.



\item 
Prove that your algorithm finds an optimal solution.  Be
careful and precise.  If you're algorithm relies on
algorithms discussed in class, when appropriate, feel free
to appeal to results that were proved for them in prior
class discussion.



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