Lab 4: Traveling Salesperson
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:

Tips

  • 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 (LIFO push).  
  • 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.

Bonus

Implement another heuristic