Pair programming. On this assignment, just like the last one, you are encouraged (not required) to work with a partner provided you practice pair programming. Pair programming "is a practice in which two programmers work side-by-side at one computer, continuously collaborating on the same design, algorithm, code, or test." One partner is driving (designing and typing the code) while the other is navigating (reviewing the work, identifying bugs, and asking questions). The two partners switch roles every 30-40 minutes, and on demand, brainstorm. Before pair programming, you must read the article All I really need to know about pair programming I learned in kindergarten.
You may choose a partner from the same or a different precept. You and your partner will each turn in a separate individually written readme.txt for the assignment, stating who your partner is and detailing your experience. However, only one of you should turn in the assignment (the .java files).
|
What are the main goals of this assignment? You should (i) learn about the notorious traveling salesperson problem, (ii) learn to use linked lists, and (iii) get more practice with data types.
How do I represent infinity in Java? Use Double.POSITIVE_INFINITY.
How long should my programs take to execute? It should take less than a minute for the 13,509 city example (substantially less if you have a fast computer). If your code takes much much longer, try to discover why (think analysis of algorithms), and explain it in your readme file. When timing your program, don't animate the results on the screen or this may become the bottleneck.
What is the file Tour$Node.class? When you declare a nested class like Node, the Java compiler uses the $ symbol to mark its name.
What is a NullPointerException? You can get one by initializing a variable of type Node, say x, to null and then accessing x.next or x.p. This can happen in your insertion routine if you inadvertently break up the circular linked list.
When should I create a new linked list node with the keyword new? To create a tour with N elements, you should use new exactly N times with Node, once per invocation of insert(). It is unnecessary (and bad style) to use new with your list traversal variables since this allocates memory that you never use.
How can I produce an animation of the heuristic in action? It's easy and instructive - just redraw the tour after each insertion. See the instructions in SmallestInsertionDraw.java. It could take a while on a big input file, so you might want to modify it so that it redraws only after every 20 insertions or so.
Can I use Java's built in LinkedList class? Absolutely not! One of the main goals of this assignment is to gain experience writing and using linked structures. The Java libraries can only take you so far, and you will quickly discover applications which cannot be solved without devising your own linked structures. Stay tuned.
For the extra credit, how fast should my solution be? It depends on the speed of your computer, but say around 5 minutes for usa13509.txt.
Do I have to use a linked list for the extra credit? No.
|
Input. There are many sample data files (with extension .txt) available from the tsp directory. Most are taken from TSPLIB.
Debugging. A good debugging strategy for most programs is to test your code on inputs that you can easily solve by hand. Start with 1 and 2 city problems. Then, do a 4 city problem. Choose the data so that it is easy to work through the code by hand. Draw pictures. If your code does not do exactly what your hand calculations indicate, determine where they differ. Use the System.out.println() method.
Compilation. Your program must be named Tour.java. (You will need Point.java to compile locally.) Don't forget to hit the Run Script button on the submission system to test that it compiles cleanly.
Checking your work. For usa13509.txt we get distances of 77449.97941714071 and 45074.77692017051 for nearest insertion and smallest insertion, respectively. For circuit1290.txt we get 25029.790452731024 and 14596.097124575306.
Timing. You may use the client program TSPTimer.java to help you estimate the running time as a function of the input size N. It takes a command-line argument N, runs the two heuristics on a random input of size N, and prints out how long each took.
|
Submission. Submit the following files: readme.txt, and Tour.java.
readme.txt. Use the following readme file template. You will lose points if you don't address these questions.
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
For debugging purposes only, make a constructor that takes four points as arguments, and constructs a circular linked list using those four Points. First, create four nodes and assign one point to each. Then, link the nodes one to another in a circle.
Test your method by writing a main() function that defines four points, creates a new Tour object using those four points, and calls its show() method. Below is a suggested four point main(). Use it for testing.
If your method is working properly, you will get the following output for the 4 city problem above.// main method for testing public static void main(String[] args) { // define 4 points forming a square Point a = new Point(100.0, 100.0); Point b = new Point(500.0, 100.0); Point c = new Point(500.0, 500.0); Point d = new Point(100.0, 500.0); // Set up a Tour with those four points // The constructor should link a->b->c->d->a Tour squareTour = new Tour(a, b, c, d); // Output the Tour squareTour.show(); }
Test your method show() on tours with 0, 1 and 2 points to check that it still works. You can create such instances by modifying the 4-node debugging constructor to only link 0, 1 or 2 of the four points to the Tour. (If you don't define first, you will have an empty Tour. If you define first and link it back to itself, you will have a 1 point Tour.)(100.0, 100.0) (500.0, 100.0) (500.0, 500.0) (100.0, 500.0)
Put the debugging constructor back to the original four point Tour before continuing.
in your main() before you call the Tour draw() method. The four point example above should produce a square.StdDraw.setXscale(0, 600); StdDraw.setYscale(0, 600);
|
Possibilities for improvement are endless. Here are some ideas. If you are shooting for an A or A+, this is a good opportunity to impress us. However, be warned, this is a difficult extra credit. If you complete the extra credit, submit a program ExtraCredit.java along with any accompanying files. You are not required to use the Tour data type or linked lists for the extra credit, but you should exercise good modular design.
|