CpSc 241, Section 1
                             Assignment 9
                             11 April 2000


Due: Tuesday, April 18, at midnight

Late penalties: 20 points per partial day late.  That is, programs
	turned in after midnight Tuesday and before midnight Wednesday
	will have 20 points deducted for late, programs turned in after
	midnight Wednesday and before midnight Thursday will have a total
	of 40 points deducted for late, etc.

Total point value of assignment:  100 points

Late submissions not accepted after: Saturday, April 22, at midnight

This assignment is to be done INDIVIDUALLY.



Create a directory, A9, which will contain all parts of this assignment.
You may include your AdjGraph class from lab.  If you use a graph
class, including any from this book, that you did not write yourself
you may be called upon to explain the code in that class as part
of the grade of this assignment.  Your graph class may use either
a matrix or lists to store the graph.    

The objectives of this program are to give you experience designing
your own algorithm to solve a problem and to give you experience
with a graph algorithm that does not run in linear time.


The main() will be called a9.cc or a9.cpp, whichever you choose.  Submit
all files in directory A9 using handin.  You may submit an algorithm
to the instructor for an opinion on whether or not the algorithm
will solve the problem.  Replies will probably be of the form
"yes," "no," or "I don't understand your algorithm."  Replies may
not be available from late Friday until mid-morning Monday.  Please
give this a try early in the week.


Input:

    Read information from a file, a9.dat, containing distances/costs
    between cities.  Your data should look something like:

        Atlanta      Chattanooga      115
        Columbia     Atlanta          213          
        ...

	Your program must work for a complete graph.  If your program
	also works for any graph an additional 20 points extra credit
	will be given.

Output:

	Before reading the input, print your name, the assignment number,
	and a short description of the assignment to the screen.

    Always "echo print" the input information.

	Choosing any city as the "start" city, you are to visit each
	city exactly once and return to the starting city with minimum
	total cost of the edges traversed.

    Print a list of pairs of cities, together with distances, that
    constitute a solution to the problem.  Also print the total 
	cost of the edges traversed.


Other requirements:

	Follow the style standards to be found from your instructor's
	web page for CPSC 241.


Grading rubric:

	In the opinion of the instructor the program is an honest attempt
		to complete the assignment as described  10 pts.

	If the above requirement is met:
		Required documentation and style standards 20 pts.
        (This 20 pts. includes required output to screen of
         your name, assignment 9, etc.)

	If the two previous requirements are not met or the program does
    not compile, no further points will be awarded.

    Program compiles without error. (10 pts.)
	Program gives correct minimum cost of cycle for grader's
	     input files (30 pts.)
	Program gives correct list of (city, city) edges on minimum
	     cycle for grader's input files (10 pts.)
	Extra credit:  Available only if program works correctly
	     for grader's input files.  If also works for graphs
	     that are not complete (20 pts.).

    Programmer can explain all code on request.  If you use a graph
 	   class other than your own, you will be requested to explain. (20 pts.)