Final Project –
Circuit Board Testing
Due December 21, 2001
A small printed-circuit board testing company has customers with very high reliability requirements for their PC-boards. The testing company must check that each and every board has no wire breaks before filling it with components. This means testing that each and every pair of points on the board that are supposed to be connected are connected. They use a robot with two arms, each with electric probes. To test whether two points are properly connected, the arms simultaneously contact both of the points. If the two points are properly connected, then the probes will complete a circuit.
We are interested with testing nets. On a circuit board there are certain sets of points that are all connected together with a metal layer. This is a net. Sometimes a net consists of two points, i.e. is an isolated wire. Sometimes a net can have 100 to 200 points, like all the connections to power or ground.
For each net, the robot holds one arm fixed at one point and moves the other arm to cover the rest of the points.
The input for the testing program consists only of the coordinates of the net contact points. To verify that all the points in a net are connected together the left robot arm is put on the leftmost point in the net, then the right arm is moved around to all the other points in the net to test if they are connected to the left point. If they are all connected to the left point, it means that they must all be connected to each other. The motion of the right robot arm is determined by sorting the points it needs to visit from left to right and then visiting them in that order. The same type of motors is used to control horizontal and vertical arm movements. Further, since the two motors for each arm are independent, the robot can simultaneously move each arm both horizontally and vertically.
Your task is to find a better (less total time for a net test) algorithm for the robot motion. You may want to present several better algorithms.
The deliverables for this project are the following:
· A discussion of the problem, along with a formal proof as to whether this problem belongs in the class P, NP, or NPC. In order to do this you will have to restate this as a decision problem.
· A explanation of your algorithm to better solve the problem, and why it’s better
· A discussion of the process by which you arrived at your algorithm
· Some discussion of the algorithms which you found and discarded
· A detailed analysis of the run-time of your algorithm. This should include a proof of a tight bound on the run-time.
· An explanation of the program structure and any data structures used.
Unlike previous projects, this project is to be an individual effort. You are not permitted to consult with each other (or anyone else) on any part of the project. You are permitted to use the course text, any class notes, code from previous projects, and a programming guide (i.e. java or c++ programming reference), but nothing else (i.e. no web sites, outside code base, etc). The project will be graded on the creativity of the solution, the execution of the code, and the completeness of the paper. As always, if you have any questions you are free to email / call / stop by at any time.