1. Homepage
  2. Programming
  3. CSE 450 Design and Analysis of Algorithms: Code Project 1 - Hiking Trails

CSE 450 Design and Analysis of Algorithms: Code Project 1 - Hiking Trails

Contact Us On WeChat
USASUCSE 450CSE450Design and Analysis of AlgorithmsHiking TrailsPython

CSE 450: Code Project 1 (Hiking Trails) CourseNana.COM

This code project should be completed individually. Refer to Canvas for a code template and example test case input/output pairs. When you’re finished, upload your completed code to codePost for autograding. You may resubmit as many times as you want until the deadline. CourseNana.COM

1 Motivation & Setting CourseNana.COM

Suppose that a government wants to create a new, large conservation park for wildlife and tourism. They know where they want to build the visitors’ center and the locations of the natural landmarks they want to make accessible, but they need your help to decide where to put the hiking trails connecting them all. To save on costs, they want to build as little trail as possible while respecting the following design constraints. CourseNana.COM

The trails must connect the visitors’ center and all natural landmarks in the park.
There are certain no-trail regions of the park where trails cannot pass through (e.g., lakes, sensitive CourseNana.COM

nesting areas, excessively steep terrain).
Trails connecting two locations of interest must be built in a straight line; they cannot curve or bend. CourseNana.COM

Once the trail network is built, the park service is also hoping you can help them calculate trail distances and other interesting measurements for their trail maps and brochures. CourseNana.COM

2 Modeling CourseNana.COM

You ask the park service for the relevant data, and they provide you with (1) a list of latitude-longitude coordinates for the visitors’ center and natural landmarks, and (2) a list of no-trail regions, each expressed as a pair of latitude-longitude coordinates for the region’s northwest and southeast corners. An example set of locations and no-trail regions from ASU campus might look like: CourseNana.COM

As you start to think about the problem, you realize that the Minimum-Spanning-Tree problem—which you conveniently studied recently in CSE 450—might be helpful for this hiking trail task. You imagine the park as a graph G = (V,E) where the nodes V = {v0,...,vn1} are the visitors’ center and natural landmarks, and the edges E represent the possible trails between them. You observe that since trails can be walked in either direction, these edges are undirected. You also realize that some pairs of locations shouldn’t have edges between them because they would involve a possible trail crossing through a no-trail region. You aren’t totally sure at this moment how to test which edges are valid and which should be removed, but you know it’s something you need to solve eventually. CourseNana.COM

You next consider how to assign edge weights w : E R+ based on the distance between any pair of locations. You’re more used to working with Cartesian coordinates on a 2D grid. In that setting, you know that the distance between any two points p1 = (x1, y1) and p2 = (x2, y2) is given by CourseNana.COM

22 d(p1,p2)= (x1x2) +(y1y2). CourseNana.COM

But this hiking trail task deals with latitude-longitude—and the Earth is round! You aren’t sure how to calculate distance over a spherical surface (even if you ignore elevation changes), but after some digging around on the Internet you discover the haversine formula does exactly what you need. Using haversines, the distance between two points p1 = (lat1, lng1) and p2 = (lat2, lng2) is very closely approximated by CourseNana.COM

r6,367.5 km is the radius of the Earth and the latitudes/longitudes are given in radians. CourseNana.COM

With this modeling and brainstorming done, you feel ready to start implementing your algorithm. CourseNana.COM

The codePost environment will autograde your project using python 3.7 in a Linux environment. Use other versions of python at your own risk. You may use any standard packages shipped with core python in your implementation, but you only need os.path (for handling OS-independent filepaths), csv (for reading the input data) and math (for trigonometric functions). The numpy package (v1.21.6) is also available in the codePost environment if you want to use it, but it is not necessary. Structure your directory as: CourseNana.COM

|--- hikingtrails.py // Start with the template. All implementation goes here. |--- inputs // Directory of .csv input files.
|--- |--- <id1>_landmarks.csv
|--- |--- <id1>_notrails.csv
|--- |--- <id2>_landmarks.csv
|--- |--- <id2>_notrails.csv
|--- |--- ...

According to their documentation, any autograded test on codePost will timeout after 30 seconds. You will not be graded based on the runtime of your code, but it does need to be efficient enough that it does not run longer than codePost will allow. CourseNana.COM

3.2 Input Data CourseNana.COM

Each test case involves two input files: landmarks and no-trail regions. Landmarks files have filenames <id> + "_landmarks.csv" CourseNana.COM

1In reality, even when ignoring elevation changes, the Earth is not a perfect sphere and thus using haversines can yield up to a 0.5% error when calculating distances. Alternative (but more complicated) metrics like Vincenty’s formulae accurately estimate distances—without elevation and assuming an ellipsoidal Earth—within 0.5 mm. CourseNana.COM

3 Implementation
3.1 Environment, Packages, and Directory Structure CourseNana.COM

and no-trail regions files have filenames CourseNana.COM

<id> + "_notrails.csv" CourseNana.COM

where id is the string identifier of the test case. Since your code will be tested in a Linux environment, it is important to avoid hardcoding your filepaths. For example, loading the file inputs\file.csv on Windows will break on Linux, which expects inputs/file.csv. Instead, use os.path.join("inputs", "file.csv") for OS-independent filepaths. CourseNana.COM

Each landmarks file contains one latitude-longitude location per row, in degrees. Each row corresponds to a landmark, and the first row specifies the location of the visitors’ center. Each no-trail region file contains two latitude-longitude locations per row indicating the northwest and southeast corners of a rectangular no-trail region. For example, the ASU location data generating the map in Section 2 is: CourseNana.COM

asu_landmarks.csv: 33.4235199204736,-111.9389895178650 33.4161999268015,-111.9379442781375 33.4204818018029,-111.9339702789114 33.4264120936318,-111.9326212152087 33.4189540042138,-111.9345724451219 33.4153789823921,-111.9285127742504 33.4196990211426,-111.9283729910807 CourseNana.COM

asu_notrails.csv: 33.4173262237920,-111.9326952069888,33.4160122364887,-111.930216085321 33.4255050937388,-111.9366697810203,33.4232222352196,-111.934977523185 CourseNana.COM

Throughout the project, landmarks will be referred to as integers corresponding to their index in the land- marks file; the visitors’ center is landmark v0, the next row is the location of landmark v1, and so on. CourseNana.COM

3.3 Task 1: Helper Functions CourseNana.COM

There are two helper functions to implement before tackling the core problems. CourseNana.COM

haversine_distance(lat1, lng1, lat2, lng2) CourseNana.COM

  • Description. Computes the distance in kilometers between two latitude-longitude locations accounting for the curvature of the Earth using the haversine formula. See Section 2 for details.
  • Parameters. Four float values representing two latitude-longitude locations in degrees.
  • Returns. The float distance between the two locations in kilometers. intersect(lat1, lng1, lat2, lng2, latNW, lngNW, latSE, lngSE)
  • Description. Determines if the line segment between (lat1, lng1) and (lat2, lng2) intersects with the region defined by its northwest corner (latNW, lngNW) and southeast corner (latSE, lngSE).
  • Parameters. Eight float values representing four latitude-longitude locations in degrees; the first two locations are the start and endpoints of the line segment and the second two locations are the northwest and southeast corners of the region, respectively.
  • Assumptions. You may assume that the region does not contain the north or south pole. You may also assume it does not intersect the prime meridian, i.e., 0 longitude.
  • Returns. True if the line segment between the specified locations intersects with the specified region; False otherwise.

3.4 Task 2: Graph Construction CourseNana.COM

The first core task is to construct an undirected graph G = (V, E) representing the landmarks and possible trails between them as discussed in Section 2. You are required to use the provided template Graph class and implement its functions, but how you implement it and what internal data structures you use are up to you. The functions you need to implement for this class are: CourseNana.COM

Graph.__init__(self, id) CourseNana.COM

  • Description. Initializes a new Graph with nodes, edges, and edge weights based on the input data.
  • Parameters. A string identifier for the input data. Corresponds to the <id> part of the corresponding input filenames.
  • Returns. An instantiated Graph object. Graph.edge_query(self, i, j)

Description. Determines if the specified edge (vi,vj) exists in the graph and, if so, what its weight is. Parameters. Two int indices i and j corresponding to landmarks vi and vj.
Returns. A float weight of the edge (vi,vj) if the edge exists and None otherwise. CourseNana.COM

Graph.connected(self) CourseNana.COM

Description. Determines if the graph is connected.
Parameters. N/A.
Returns. True if the graph is connected and False otherwise. CourseNana.COM

3.5 Task 3: Trail Network Design CourseNana.COM

With a graph G instantiated, the next core task is to determine the optimal trail network using an algorithm for Minimum-Spanning-Tree. You may use any of the three algorithms we covered in class (Kruskal’s, Reverse- Delete, or Prim’s). Your implementation does not necessarily have to be optimized, but it does need to run fast enough to avoid timing out (see Section 3.1). You are required to use the provided template MST class and implement its functions, but you can implement it however you want. CourseNana.COM

MST.__init__(self, graph) CourseNana.COM

  • Description. Initializes a new MST by computing the minimum spanning tree of the input Graph object.
  • Parameters. A Graph object.
  • Exceptions. Raises a ValueError if the input graph is disconnected.
  • Assumptions. You may assume that the edge weights of the input Graph object are distinct and thus the resulting minimum spanning tree is unique.
  • Returns. An instantiated MST object. MST.edge_query(self, i, j)

Description. Determines if the specified edge (vi,vj) exists in the minimum spanning tree. Parameters. Two int indices i and j corresponding to landmarks vi and vj.
Returns. True if the edge (vi,vj) is in the minimum spanning tree and False otherwise. CourseNana.COM

Description. Computes w(e) for the minimum spanning tree T.
Parameters. N/A.
Returns. The float total length of the minimum spanning tree, in kilometers. CourseNana.COM

MST.visitor_length(self, i) CourseNana.COM

Description. Computes the walking distance from the visitors’ center to landmark vi along the trails. Parameters. An int index i corresponding to landmark vi.
Returns. A float distance from the visitors’ center to vi, in kilometers. CourseNana.COM

4 Grading and Evaluation CourseNana.COM

This project is graded out of 80 points, with the opportunity to earn an extra 20 points of extra credit (maximum score 100/80). The grade breakdown is: CourseNana.COM

  • Eight for-credit codePost test cases worth 10 points each. Each test case is autograded in an all-or- nothing, pass-or-fail manner. There is no partial credit.
  • One extra-credit codePost test case worth 10 points. This test case has significantly more landmarks than the for-credit cases and thus rewards carefully optimized code.
  • One extra-credit visualization task worth 10 points. The goal here is to produce a plot visualizing the landmarks, no-trail regions, and computed minimum spanning tree for a very large instance. I recommend using the matplotlib package for python, but you are free to choose your preferred tools.

The instance to visualize is Yellowstone National Park, corresponding to the yellowstone input files included in the .zip file on Canvas. Your completed visualization should have a dot for each landmark, a special dot for the visitors’ center, boxes for each no-trail region, and edges connecting dots for your minimum spanning tree. Upload your completed figure to Canvas as a .png or .jpg for extra credit. CourseNana.COM


Get Expert Help On This Assignment

Scan above qrcode with Wechat

US代写,ASU代写,CSE 450代写,CSE450代写,Design and Analysis of Algorithms代写,Hiking Trails代写,Python代写,US代编,ASU代编,CSE 450代编,CSE450代编,Design and Analysis of Algorithms代编,Hiking Trails代编,Python代编,US代考,ASU代考,CSE 450代考,CSE450代考,Design and Analysis of Algorithms代考,Hiking Trails代考,Python代考,UShelp,ASUhelp,CSE 450help,CSE450help,Design and Analysis of Algorithmshelp,Hiking Trailshelp,Pythonhelp,US作业代写,ASU作业代写,CSE 450作业代写,CSE450作业代写,Design and Analysis of Algorithms作业代写,Hiking Trails作业代写,Python作业代写,US编程代写,ASU编程代写,CSE 450编程代写,CSE450编程代写,Design and Analysis of Algorithms编程代写,Hiking Trails编程代写,Python编程代写,USprogramming help,ASUprogramming help,CSE 450programming help,CSE450programming help,Design and Analysis of Algorithmsprogramming help,Hiking Trailsprogramming help,Pythonprogramming help,USassignment help,ASUassignment help,CSE 450assignment help,CSE450assignment help,Design and Analysis of Algorithmsassignment help,Hiking Trailsassignment help,Pythonassignment help,USsolution,ASUsolution,CSE 450solution,CSE450solution,Design and Analysis of Algorithmssolution,Hiking Trailssolution,Pythonsolution,