Bard College – Computer Science – Data Structures
In this lab we’ll solve the traveling salesperson problem(well, kinda). Specifically, we’ll develop linked-list implementations of graph tours. Finding an optimal tour of a graph is a big deal.
Again this week, we will follow our textbook authors’ project pretty closely:
First work to get Point to run, make sure your data files are in the right place and create a skeleton for Tour.(see note about Intellij below)
insertNearest(): before worrying about any of the heuristics, create a simpler version of Tour that more inserts points into the tour in the order they are inputted(LIFOpush).
Next, complete the show and distance methods.
SmallestInsertion and NearestInsertion are good test clients.
Even though a Tour is circular(mathematically), i.e., it wraps around from the end to the start, I recommend not making the linked list circular since it will be harder to iterate over.
Modifications
Include import edu.princeton.cs.algs4.* at the top of your java files.
No need for the second constructor: Tour(Point a, Point b, Point c, Point d)
NearestInsertion.java and SmallestInsertion.java calls Tour’s length() method, this is a bug, they should instead call distance() .
We’ll save the Analysis section for later. In this lab we are focused on implementing the methods in Tour.java; later, we’ll move onto performance comparison.
StdIn Woes with IntelliJ
IntelliJ users can manually read in the file rather than using file redirection(< tsp1000.txt ):
In in = new In ("tsp1000.txt");
in.isEmpty()
in.readDouble()
in.isEmpty()
Submission
Submit your Tour.java file in a zipped folder named cmsc201-lab4-lastname-firstname.
Be sure to include your name, date, email, lab description and collaboration statement in the README file. The final lab(and a small addition next week) will be due after the Spring Break on March 31st, 2022, but you will submit your work-in-progress next Thursday on the 17th. You should have a basic insert done and have made some progress on insertNearest.
Tips
Modifications
StdIn Woes with IntelliJ
In in = new In ("tsp1000.txt");in.isEmpty()in.readDouble()in.isEmpty()Submission
Bonus