%
% 6.006 problem set template
%
\documentclass[12pt,twoside]{article}

\input{macros}

\usepackage{amsmath}

\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

% Fill these in!
\newcommand{\theproblemsetnum}{5}
\newcommand{\handoutnum}{10}
\newcommand{\releasedate}{Tuesday, November 4th}
\newcommand{\partaduedate}{Tuesday, November 18th}
\newcommand{\partbduedate}{Thursday, November 20th}

\begin{document}


\handout{\handoutnum}{Problem Set \theproblemsetnum}{\releasedate}
\setlength{\parindent}{0pt}

\newcommand{\solution}{
  \medskip
  {\bf Solution:}
}

This problem set is divided into two parts: Part A problems are
programming tasks, and Part B problems are theory questions.

{
\parindent 0.5in
\textbf{Part A questions} are due {\bf \partaduedate} at {\bf 11:59PM}.

\textbf{Part B questions} are due {\bf \partbduedate} at {\bf 11:59PM}.
}

Solutions should be turned in through the course website in PDF form
using \LaTeX\ or scanned handwritten solutions. 

A template for writing up solutions in \LaTeX\ is available on the
course website.

Remember, your goal is to communicate. Full credit will be given only
to the correct solution which is described clearly. Convoluted and
obtuse descriptions might receive low marks, even when they are
correct. Also, aim for concise solutions, as it will save you time
spent on write-ups, and also help you conceptualize the key idea of
the problem.

\medskip

\hrulefill

\medskip

Exercises are for extra practice and should not be turned in.

{\bf Exercises:}

\begin{itemize}

\item CLRS 24.1-1 (page 591)

\item CLRS 24.3-2 (page 600)

\item CLRS 24.3-4 (page 600)

\item CLRS 24.5-8 (page 614)

\item CLRS 24.3-6 (page 600)

\end{itemize}

\hrulefill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Part A: Due \partaduedate}

\begin{enumerate}

\item {\bf (50 points)} Implementing Dijkstra.

  \noindent The Howe \& Ser Moving Company is transporting the Caltech
  Cannon from Caltech's campus to MIT's and wants to do so most
  efficiently.  Fortunately, you have at your disposal the National
  Highway Planning Network (NHPN), packaged for you in
  \verb|ps5_dijkstra.zip|. You can learn more about the NHPN at \\
  \verb|http://www.fhwa.dot.gov/planning/nhpn/|

  This data includes node and link text files from the NHPN. Open
  \verb|nhpn.nod| and \verb|nhpn.lnk| in a text editor to get a sense
  of how the data is stored (\verb|datadict.txt| has a more precise
  description of the data fields and their meanings). To save you the
  trouble of parsing these structures from a file, we have provided
  you with a Python module \verb|nhpn.py| containing code to load the
  text files into Node and Link objects. Read \verb|nhpn.py| to
  understand the format of the Node and Link objects you will be
  given.

  Additionally, we have provided some tools to help you visualize the
  output from your algorithms.  You can use the \verb|Visualizer|
  class to produce a KML (Google Earth) file.  To view such a file on
  Google Maps, place it in a web-accessible location, such as your
  Athena \verb|Public| directory, and then search for its URL on
  Google Maps.

  For this problem, you will modify the file \verb|dijkstra.py|. As
  you solve each part of the problem, check your work by running
  \verb|test_dijkstra.py|. As usual, remember to comment your code,
  including docstrings at the top of each function.

  \begin{enumerate}
  \item {\bf (5 points)} Write a short function
    \verb|node_by_name(nodes, city, state)| to return a node from the
    given city/state. Note that some nodes have a description which
    isn't solely the city name, e.g. \verb|CAMBRIDGE NW| or
    \verb|NORTH CAMBRIDGE|, either of which we would like to match a
    query where \verb|city=='CAMBRIDGE'|. Given a choice of more than
    one node, choose the first node that appears in the data.

  \item {\bf (5 points)} The links you are given do not include
    weights, so instead we will use the geographical positions of the
    edge's nodes.

    Write a function \verb|distance(node1, node2)| to return the
    distance between two NHPN nodes. Nodes come with latitude and
    longitude (in millionths of degrees). For simplicity, treat these
    instead as $(x, y)$ coordinates on a flat surface, where the
    distance between two points can be easily calculated using the
    Pythagorean Theorem.
    
    \emph{Hint:} You may find the \verb|math.hypot| function useful.

  \item {\bf (40 points)} Implement Dijkstra's algorithm to find the
    shortest path between two vertices in a graph with non-negative
    edge weights.

    Your function \verb|shortest_path(nodes, edges, weight, s, t)|
    will be given a graph (represented as a list of Node objects and a
    list of undirected Edge objects), a function \verb|weight(node1, node2)| which
    returns the weight of any edge between \verb|node1| and
    \verb|node2|, a source Node $s$ and a destination Node $t$. Your
    function should return a list of \verb|Node| objects representing
    a path from $s$ to $t$.

    Dijkstra's algorithm uses a priority queue, but this priority
    queue has one subtle requirement not met by the \verb|heap.py|
    implementation seen earlier in class. Dijkstra's algorithm calls
    \verb|decrease_key|, but \verb|decrease_key| requires the index of
    an item in the heap, and Dijkstra's algorithm would have no way of
    knowing the current index corresponding to a particular Node. To
    solve this problem, the course staff has written an augmented heap
    object, \verb|heap_id|, with the following extra features:

    \begin{itemize}
    \item \verb|insert(key)| returns a unique ID.
    \item A new method, \verb|decrease_key_using_id(ID, key)| takes an
      \verb|ID| instead of an index.
    \item A new method, \verb|extract_min_with_id()| extracts the minimum
      element and returns a pair \verb|(key, ID)|
    \end{itemize}

    You may \verb|import heap_id|, without submitting the separate file.

    \emph{Hint:} The format in which you are given the data (a list of
    nodes, and a list of edges), is not what you want to use for
    Dijkstra's algorithm. Start by preprocessing the data into a more
    useful graph representation. Don't forget that the edges you are
    given are undirected.

  \item {\bf (Optional)} Included in \verb|nhpn.py| is a method to
    convert a list of nodes to a \verb|.kml| file. \verb|.kml| files
    can be viewed using Google Maps, by putting the file in a
    web-accessible location (like your Athena Public directory), going
    to \\ \verb|http://maps.google.com| and putting the URL in the
    search box.

    Run \verb|visualize_path.py|. This will create two files,
    \verb|path_flat.kml| and \\ \verb|path_curved.kml|. Both should be
    paths from Pasadena CA to Cambridge MA. \verb|path_flat.kml| was
    created using the distance function you wrote in part (b), and
    \verb|path_curved.kml| was created using a distance function that
    does not assume the Earth is flat. Can you explain the
    differences? Also, try asking Google Maps for driving directions
    from Caltech to MIT to get a sense of how similar their answer is.

  \end{enumerate}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Part B: Due \partbduedate}


\begin{enumerate}
\item {\bf (10 points)} True or False.

  Decide whether these statements are {\bf True} or {\bf False}. You
  must briefly justify all your answers to receive full credit.

  \begin{enumerate}

  \item {\bf (5 points)} If some edge weights are negative, the
    shortest paths from $s$ can be obtained by adding a constant $C$
    to every edge weight, large enough to make all edge weights
    nonnegative, and running Dijkstra's algorithm.

  \item {\bf (5 points)} Let $P$ be a shortest path from some vertex
    $s$ to some other vertex $t$.  If the weight of each edge in the
    graph is squared, $P$ remains a shortest path from $s$ to $t$.

  \end{enumerate}


\item {\bf (20 points)} A \emph{longest path} from $s$ to $t$ is
  defined as the path from $s$ to $t$ with the largest possible
  weight.

  \begin{enumerate}
  \item {\bf (5 points)} In a directed graph $G$, when is a shortest path from vertices
    $s$ to $t$ well defined? When is a longest path from $s$ to $t$
    well defined?

  \item {\bf (7 points)} The Bellman-Ford algorithm assigns a value
    $d[v]$ to every vertex $v$. When does $d[v]$ equal the length of
    the shortest path from $s$ to $v$? This may or may not be related
    to whether the algorithm reports that there are negative-weight
    cycles in the graph.

  \item {\bf (8 points)} Describe how to use Bellman-Ford to find the
    longest path from $s$ to $t$ in a directed graph. Your algorithm
    does not have to handle cases analogous to ones that the normal shortest-paths
    Bellman-Ford does not handle.

  \end{enumerate}

%% Tighten up wording to ensure that the problem clearly states that
%% your algorithm doesn't have to work.
% Part a: ask when the longest /shortest path is defined
% Part b: when does bellman-ford fail for shortest paths s->t
% Part c: make bellman-ford work for longest when it works for shortest.

\item {\bf (20 points)} Even-Length Paths

  An even-length path is a path traversing an even number of
  edges. Describe a modified version of Dijkstra's algorithm that
  finds the shortest even-length path in a graph $G = (V, E)$ from a
  given start vertex $s$ to all vertices $t \in V$. The graph has non-negative
  edge weights. Your solution
  should have the same asymptotic running time as Dijkstra's algorithm. (HINT:
  try solving the problem by constructing a graph $G'$ that is somehow related
  to $G$, running Dijkstra's algorithm on $G'$, and projecting the results back
  onto $G$.)

\end{enumerate}





\end{document}
