% % 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}