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 a graph tour. 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)
insert(): before worrying about the heuristics, create a simpler version of Tour that simply inserts points into the tour in the order they are inputted(FIFO or LIFO).
Queue is a good place to look for inspiration for Tour; SmallestInsertion is a good test client.
Next, complete the show and distance methods.
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 heuristics 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. This lab is due after the exam on October 13th, 2020.
Tips
Modifications
StdIn Woes with IntelliJ
In in = new In ("tsp1000.txt");in.isEmpty()in.readDouble()in.isEmpty()Submission
Bonus