DOC PREVIEW
MIT 6 006 - Problem Set #5

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithms: 6.006Massachusetts Institute of Technology Tuesday, April 7thProfessors Sivan Toledo and Alan Edelman Handout 10Problem Set 5This problem set is divided into two parts: Part A problems are programming tasks, and Part Bproblems are theory questions.Part A questions are due WEDNESDAY, April 22nd at 11:59PM.Part B questions are due Thursday, April 23rd at 11:59PM.Solutions should be turned in through the course website in PDF form using LATEX or scannedhandwritten 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 solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen 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.Exercises are for extra practice and should not be turned in.Exercises:• CLRS 24.1-1 (page 591)• CLRS 24.3-2 (page 600)• CLRS 24.3-4 (page 600)• CLRS 24.5-8 (page 614)• CLRS 24.3-6 (page 600)Part A: Due WEDNESDAY, April 22nd1. (50 points) Implementing Dijkstra.The Howe & Ser Moving Company is transporting the Caltech Cannon from Caltech’s cam-pus to MIT’s and wants to do so most efficiently. Fortunately, you have at your disposal theNational Highway Planning Network (NHPN), packaged for you in ps5_dijkstra.zip.You can learn more about the NHPN athttp://www.fhwa.dot.gov/planning/nhpn/This data includes node and link text files from the NHPN. Open nhpn.nod and nhpn.lnkin a text editor to get a sense of how the data is stored (datadict.txt has a more precisedescription of the data fields and their meanings). To save you the trouble of parsing thesestructures from a file, we have provided you with a Python module nhpn.py containing2 Handout 10: Problem Set 5code to load the text files into Node and Link objects. Read nhpn.py to understand theformat of the Node and Link objects you will be given.Additionally, we have provided some tools to help you visualize the output from your al-gorithms. You can use the Visualizer class to produce a KML (Google Earth) file. Toview such a file on Google Maps, place it in a web-accessible location, such as your AthenaPublic 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 theproblem, check your work by running test_dijkstra.py. As usual, remember to com-ment your code, including docstrings at the top of each function.(a) (5 points) Write a short function node_by_name(nodes, city, state) toreturn a node from the given city/state. Note that some nodes have a description whichisn’t solely the city name, e.g. CAMBRIDGE NW or NORTH CAMBRIDGE, either ofwhich we would like to match a query where city==’CAMBRIDGE’. Given a choiceof more than one node, choose the first node that appears in the data.(b) (5 points) The links you are given do not include weights, so instead we will use thegeographical positions of the edge’s nodes.Write a function distance(node1, node2) to return the distance between twoNHPN nodes. Nodes come with latitude and longitude (in millionths of degrees). Forsimplicity, treat these instead as (x, y) coordinates on a flat surface, where the distancebetween two points can be easily calculated using the Pythagorean Theorem.Hint: You may find the math.hypot function useful.(c) (40 points) Implement Dijkstra’s algorithm to find the shortest path between two ver-tices in a graph with non-negative edge weights.Your function shortest_path(nodes, edges, weight, s, t) will be givena graph (represented as a list of Node objects and a list of undirected Edge objects), afunction weight(node1, node2) which returns the weight of any edge betweennode1 and node2, a source Node s and a destination Node t. Your function shouldreturn a list of Node objects representing a path from s to t.Dijkstra’s algorithm uses a priority queue, but this priority queue has one subtle re-quirement not met by the heap.py implementation seen earlier in class. Dijkstra’salgorithm calls decrease_key, but decrease_key requires the index of an itemin the heap, and Dijkstra’s algorithm would have no way of knowing the current indexcorresponding to a particular Node. To solve this problem, the course staff has writtenan augmented heap object, heap_id, with the following extra features:• insert(key) returns a unique ID.• A new method, decrease_key_using_id(ID, key) takes an ID insteadof an index.• A new method, extract_min_with_id() extracts the minimum element andreturns a pair (key, ID)Handout 10: Problem Set 5 3You may import heap_id, without submitting the separate file.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 datainto a more useful graph representation. Don’t forget that the edges you are given areundirected.(d) (Optional) Included in nhpn.py is a method to convert a list of nodes to a .kml file..kml files can be viewed using Google Maps, by putting the file in a web-accessiblelocation (like your Athena Public directory), going tohttp://maps.google.com and putting the URL in the search box.Run visualize_path.py. This will create two files, path_flat.kml andpath_curved.kml. Both should be paths from Pasadena CA to Cambridge MA.path_flat.kml was created using the distance function you wrote in part (b), andpath_curved.kml was created using a distance function that does not assume theEarth is flat. Can you explain the differences? Also, try asking Google Maps for drivingdirections from Caltech to MIT to get a sense of how similar their answer is.Part B: Due Thursday, April 23rd1. (10 points) True or False.Decide whether these statements are True or False. You must briefly justify all your answersto receive full credit.(a) (5 points) If some edge weights are negative, the shortest paths from s can be obtainedby adding a constant C to every edge weight, large enough to make all edge weightsnonnegative, and running Dijkstra’s algorithm.(b) (5 points) Let P be a shortest path from some vertex s to some other vertex t. If theweight of each edge in the graph is squared, P remains a shortest path from s to t.2. (20 points) Parameterized GraphThis problem focuses on directed graphs G = (V, E) in which the edges have


View Full Document

MIT 6 006 - Problem Set #5

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Problem Set #5
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set #5 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set #5 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?