CpSc 241, Section 1
                             Assignment 8
                             27 March 2000


Due: Monday, April 10, at midnight

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

Total point value of assignment:  100 points

Late submissions not accepted after: Thursday, April 13, at midnight

This assignment is to be done INDIVIDUALLY.



Create a directory, A8, which will contain all parts of this assignment.
You will need a classes for lists, Binary Heap, and Disjoint Sets ADT.
  

The objectives of this program are to give you experience using
multiple data structures to solve a classic algorithms/data structures
problem, the minimum spanning tree (MST), using Kruskal's Algorithm.


The main() will be called a8.cc or a8.cpp, whichever you choose.  Submit
all files in directory A8 using handin. An outline of code using
Kruskal's algorithm is given on page 361 of the text.  You should use
this basic algorithm and the data structures shown in class.  


Input:

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

        Atlanta      Chattanooga      115
        Columbia     Atlanta          213          
        ...

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.

    Print a list of pairs of cities, together with distances, that
    comprise a minimum spanning tree of the input graph.


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 3, 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 produces correct output for input data given in class. (10 pts.)
    Program produces correct output for grader's input file. (30 pts.)
    Efficient use of algorithms and data structures.  (20 pts.)


Comment:  For this program, it is recommended, but not required, that
    you store the edge information in adjacency lists.  You will find
    future programs easier if you do store the graph in adjacency lists
    before constructing the BinaryHeap.  However, use of the adjacency
    matrix instead of adjacency lists will deduct 10 points.