# Assignment 5: Graphs

The Acme computer company has hired you to program their automated wire-wrap and printed-circuit board machines. You may write in C, Java, or C++; your choice.

You are to write two programs. Both will take as input a series of coordinate pairs, one per line. Each pair will consist of two non-negative integers. To facilitate testing, we are providing a test case generator that will output sets of points. The tool takes one or two command-line arguments. The first argument is the number of desired points. The second, optional argument is a "seed" that determines which set of points to output.

Your first program will interpret its input as the locations of power pins on a wire-wrap breadboard. All these pins must be connected to each other. Your job is to choose, and output, a set of straight-line wire runs between pins that minimizes the total amount of wire used. This is basically the minimum spanning tree problem on a densely connected graph.

Your second program will interpret its input as the locations of holes to be drilled in a printed-circuit board. Your job is to choose, and output, a sequence of holes that minimizes the total distance moved by the robot arm that holds the drill. Since the arm must return to the starting location in order to drill the next board on the assembly line, your task amounts to an instance of the traveling salesperson problem.

While there are many possible ways that you could format your output, you are required, for the sake of testing and grading, to use the following. We are providing a tool that will read the standard format and display it graphically on your screen. The format consists of

• two integers N and M, giving the number of points and the number of edges, respectively;
• a sequence of N pairs of integers, giving the X Y coordinates of the N points;
• a sequence of M pairs of integers, giving the endpoints of the M edges. Each endpoint must lie between 0 and N-1, inclusive.

For the wire-wrap problem, your output graph should obviously be a tree. For the hole-drilling output, it should be a path that visits every point.

As you will have learned from lecture and the textbook, the wire-wrap problem can be solved precisely in time O(N3). The hole-drilling problem cannot: it's NP-hard. Solving it precisely for as few as 20 holes will take more compute time than you'll be willing to spend. For boards with, say, 100 holes, it would take more time than the age of the universe. So you'll need to design an heuristic algorithm that finds a good, though not necessarily optimal, sequence of holes. The trivia exercise should suggest one possible heuristic to you. Many others are possible. Some are "greedy". Some take advantage of the fact that this particular instance of the general problem is geometric and planar. Feel free to experiment for extra credit. To help us assess the quality of your heuristic, your program to solve the hole-generating problem should print the cost of the chosen cyclic path to standard error.

## Trivia assignment

Send email to the TAs containing an answer to the following question.

Suppose that S is a set of points in the plane. Let G be the undirected completely-connected weighted graph induced by straight-line Euclidian distance among the points in S. Let T be a minimum spanning tree for G. Let P be a cyclic path through G obtained by visiting nodes in the order they first appear in a depth-first traversal of T, starting at (and, with one extra edge, returning to) some arbitrary node. Prove that the length of P is no more than twice the length of the minimum traveling sales path through G.

## DUE DATES:

• For the trivia assignment: 5:00 pm, Friday November 16.
• For the main assignment: 11:59 pm, Monday December 3.

NO EXTENSIONS.

### What/how to turn in

Please be sure that your program accepts input as generated by the test case generator, and produces output that can be read by the DisplayGraph tool.

Also be sure to follow the standard guidelines for your `README` file, and turn in your code using the `turnin` script. Both your code and your `README` file should, as usual, reside in the directory in which you run the `turnin` script. Keep an eye on the newsgroup in case there are any updates.

## Extra Credit Suggestions

For extra credit (to be used for grade adjustment at the end of the semester — see here), experiment with a variety heuristics to find as good a hole-drilling order as you can. Compare the results of different heuristics on different inputs (sets of pin locations). For each heuristic, try to devise an input for which the heuristic does as badly as possible. Discuss your findings.

To put a little spice into the extra credit race, I challenge anyone who's interested to find the best possible solution to problem produced by the test case generator with (single) argument 100. (Be sure to run the generator on the CSUG machines; it may generate a different set of points if run elsewhere. If you want to be sure, you can grab the points from THIS FILE. If you want to see what they look like when plotted in the plane, CLICK HERE.) If you think you have a good solution, post it to the newsgroup. (When you post, please include both the total cost and the output of your tool, so we can display it with the DisplayGraph tool. Let's see who can find the best solution!