CS 351: Design of Large Programs
                --------------------------------

               Assignment # 2, Due Date  02/20/02
               ----------------------------------


The goal of this assignment is to gain familiarity/confidence in the use of 
the Standard Template Library (STL) containers, iterators, STL algorithms 
and function objects.
     

*******************************************************************************

PART A
------


Write a program to sort the elements in a container in ascending order.

1. To save time, start by coding a simple algorithm such as Bubble sort.

2. The same program should work (with minimal modification) for a vector,
   deque or list.

3. Populate the container with integers and use different initial orderings
   such as:
             	- already sorted
		- reverse sorted
		- random
		- random with 80% of the keys being duplicates (optional)

4. To get random data in a vector v1, use the STL algorithm 
    	random_shuffle(v1.begin(), v1.end())

   assuming v1 is already populated using, for example,
  	vector <int> v1;
   	for (i=0; i<max; i++) v1[i]=i;

5. Record the execution times for the sort with different containers, 
   different initial orderings and with at least two different and
   sufficiently large number of keys.

6. Repeat 5 above using the built-in sort algorithm provided by STL. 
   This will not work for a list (why?), instead use the sort method 
   of the list container.

7. Organize your results in two or three matrices and explain them.
   
   
*******************************************************************************



PART B
-------

Implementation of Prim's Minimum Spanning Tree Algorithm using STL
------------------------------------------------------------------


We are given an undirected but weighted graph (each edge has an associated 
cost.) 
A graph is usually represented as G = (V,E) where V is the set of vertices
(or nodes) and E is the set of edges (or links). (v1, v2) belongs to E 
if there exists an edge between vertices v1 and v2. 
(Since G is undirected, (v1, v2) is the same as (v2, v1). )  
cost(v1, v2) is the cost of traversing edge (v1, v2).

The following is the pseudo-code for Prim's MST algorithm.

   Let ES be the set of edges so far included in the MST.
   Let VS be the set of vertices so far included in the MST.

   ES = NULL;
   Initialize VS = {x} where x is any vertex in V. 

   while ( VS != V) {
     Let (a,b) be the lowest cost edge such that 
         a is a MEMBER of VS and b is a MEMBER of V - VS.
     VS = VS UNION {b}  and
     ES = ES UNION {(a,b)}
   }
     
************

The input file contains the edges, one per line.
Each edge is represented by a triplet. The first two elements are the 
vertices on which it is incident, the third element is the edge cost.


************
Your program should output the cost of the MST and the edges included.