\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms Section 2\\
Spring 2003\\
\rm
Homework 7\\
Due Tuesday, April 1 (no fooling!)\\
\end{center}

\begin{enumerate}
\item \textbf{[15 Points]} {\bf Proof of Dijkstra's Algorithm.}
Write the proof of correctness of Dijkstra's Algorithm (that we saw
in class) in your own words. For full credit, your proof should be 
clear, precise, and complete. Note that the proof we did in class is not
the same that is in the book. (The technique shown in class was much simpler;
use that technique here.)
\item \textbf{[25 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, chocolate fudge Pop Tarts, Spam, Spam,
Spam, 
        and Mountain Dew.
        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.

        The on-board computer on such a vehicle contains a weighted directed graph in which the
        vertices represent cities, the directed edges represent one-way 
        roads, and the weights on the edges represent the lengths of the roads.
        Moreover, the computer knows which select cities have filling stations.
        To use the navigation system, the user will enter the starting
        city, the destination city, and the range of the vehicle on a 
	full tank.        
	(You may assume that the starting city and the destination
	cities, being Hurts rental cities, both have filling stations
	- and that the car starts with a full tank of fuel.)
        The computer will respond with the {\em shortest} route from the source
        to the destination that ensures that the vehicle doesn't run out
        of fuel or determines that no such route exists.

You should assume that there is some constant $C$
such that every vertex has in-degree and out-degree (number of entering edges and number of exiting
edges, respectively) at most $C$.
	\begin{enumerate}
	\item {\bf Describe} and {\bf analyze the running time} of an 
	efficient algorithm for determining such a path.  For full credit, your algorithm should be as fast as possible.

	
	\item \emph{Prove} that  your algorithm finds an optimal solution.  Be careful and precise.
	\end{enumerate}
(Note:  Your algorithm may be built up of several algorithms which we have seen
in class.  You may apply any algorithms that we have seen in class.)

\item \textbf{[10 Points]} CLRS, Exercise 25.3-3 (page 640).
Give a mathematical proof of your answer!

\item \textbf{[20 Points]} CLRS, Exercise 25.3-6 (page 640).  The first part
of this problem requires a single counter-example.  The second part requires
a careful proof.
Clarification: the book uses {\tt line 1} to refer to the entire action of
creating the dummy vertex and adding in its zero weight edges. What Prof. 
Michener is proposing is to eliminate the dummy vertex altogether (this
means no additional edges are added), instead running Dijkstra on the original
graph $V$ times, once with each vertex being set to $s$.
\end{enumerate}


\end{document}

