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(N^{3}). 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*.

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.

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

**NO EXTENSIONS.**

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.

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!

Back to the grading page

Last Change: 12 November 2001 /