Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Konstantinos Daskalakis and Patrick Jaillet November 2 2010 Handout 5 Problem Set 5 This problem set is divided into two parts Part A problems are theory questions and Part B problems are programming tasks Part A questions are due Tuesday November 16th at 11 59PM Part B questions are due Friday November 19th at 11 59PM Solutions should be turned in through the course website Your solution to Part A should be in PDF form using LATEX or scanned handwritten solutions Your solution to Part B should be a valid Python file together with one PDF file containing your solutions to the two theoretical questions in Part B Templates for writing up solutions in LATEX are 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 Part A Due Tuesday November 16th 1 15 points No Odd Cycles Given an undirected graph G V E design an algorithm that decides whether or not G contains a cycle of odd length Prove its correctness Your algorithm should run in time O V E 2 15 points Maximum Bandwidth Path Suppose we have a telephone network N with n nodes m links undirected edges between them and a distinguished source node s Each link has an associated bandwidth which is a non negative integer that indicates the maximum number of requests that link can handle In a path of links the link in the path with the smallest bandwidth constrains the number of requests that can be passed along the path Hence we define the bandwidth of a path P consisting of links 1 k to be min bandwidth 1 bandwidth k The maximum bandwidth path to a node v is the path from s to v with the maximum bandwidth Design an algorithm that computes the maximum bandwidth path to every node v in the network and prove its correctness Your algorithm should have the same asymptotic running time as Dijkstra s 3 20 points Shortest Roundtrip Path Suppose G is a strongly connected directed graph meaning that for every two vertices u and v in G there is a directed path from u to v and a directed path from v to u Each edge has 2 Handout 5 Problem Set 5 a weight not necessarily non negative Let s be a distinguished node in G For every vertex v in the graph we want to calculate a path from s to v and a path from v to s such that the sum of the weights of edges on the two paths is minimized Give an efficient algorithm to perform this task and show correctness If your algorithm encounters a negative weight cycle it should output false Otherwise it should output the pair of paths from s to v and from v to s that minimizes the roundtrip cost Part B Due Friday November 19th 1 50 points Speeding up Dijkstra 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 ps5 dijkstra zip You can learn more about the NHPN at http www fhwa dot gov planning nhpn This data includes node and link text files from the NHPN Open nhpn nod and nhpn lnk in a text editor to get a sense of how the data is stored 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 nhpn py containing code to load the text files into Node and Link objects Read nhpn py to understand the format of the Node and Link objects you will be given Your goal in this problem is to implement and test several techniques for speeding up Dijkstra s algorithm in order to compute shortest paths between various pairs of locations Implementation of Dijkstra s algorithm is already provided Function dijkstra nodes edges weight source is given a graph with non negative edges represented as a list of Node objects and a list of undirected Edge objects a function weight node1 node2 that returns the weight of any edge between node1 and node2 and a source node source This function updates the node visited field for all nodes which indicates whether a shortest path to node has been found as well as node distance and node parent for visited nodes which are the length of the shortest path from the source node to node and the previous node on that path respectively The function returns the number of nodes visited during the execution of the algorithm The links you are given do not include weights so instead we use the geographical distance between their endpoints Function distance node1 node2 returns the distance between two NHPN nodes Nodes come with latitude and longitude in millionths of degrees For simplicity we treat these as x y coordinates on a flat surface where the distance between two points can be calculated using the Pythagorean Theorem Handout 5 Problem Set 5 3 Dijkstra s algorithm uses a priority queue but this priority queue has one subtle requirement Dijkstra s algorithm calls decrease key but 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 have written an augmented heap object heap id with the following extra features insert key returns a unique ID decrease key using id ID key takes an ID instead of an index extract min with id extracts the minimum element and returns a pair key ID Additionally we have provided some tools to help you visualize the output from your algorithms You can use the 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 Public directory and then search for its URL on Google Maps For this problem you will modify the file dijkstra py As you solve each part of the problem check your work by running the appropriate test functions We have provided several test functions that test each part separately or perform comparison tests of several methods You should follow the instructions for each part of the problem perform appropriate tests and draw conclusions Please submit the modified dijkstra py file with the code and dijkstra pdf file with proofs and short
View Full Document
Unlocking...