CS 5343:  Final Project  
-----------------------

DUE DATE:  Saturday, April 28, 2005, by midnight
	   (NOTE:  Late submissions allowed till midnight the following day.)


Project Specifications:
----------------------

1.  Consider the entities of your first and second projects (such as 
    video, customer etc) as nodes in a graph.

2.  Now think of relationships between these entities (such as same
    director/actor/actress, rent(ed) same video, live on same street etc).

3.  Choose any ONE relationship, model it as an edge between the nodes.
    (For each relationship you choose to model, create a separate graph.
    For this project, ONE relationship/graph is sufficient.  Extra models
    are eligible for extra/bonus points, within limits, of course.  Remember
    that extra/bonus points are used only if necessary.)

4.  Choose any TWO of the following graph algorithms (one from each pair):
    DFS/BFS, MST/SSSP (Note that SCC or TopSort can substitute for DFS).

5.  Clearly state what aspect of your problem is solved by each of the two
    algorithms you have chosen.

6.  Now implement your algorithms and run them with the graphs you have 
    constructed as inputs.

7.  Document and describe the outputs of the algorithms.


Project Deliverables:
--------------------

1.  Monday, April 9:        Preliminary Design Report (strictly limited 
    (hardcopy, in class)    to 2 pages) addressing points 1 through 5 above.

3.  Monday, April 16:       Progress Report (strictly limited to 1 page)
    (hardcopy, in class)    detailing current implementation status.

4.  Monday, April 23:       Final Design Report (strictly limited to 3 pages).
    (hardcopy, in class)    

5.  Saturday, April 28:     Source code, sample input & output files to WebCT. 
    (softcopy, via WebCT)



Guidelines for Design Report:
----------------------------

--  Should have three clear sections:  
       1.  Problem Statement:  Graph composition (clearly identifying the
			       elements of the graph -- nodes, edges, 
			       directions (if any) and weights (if any) --
			       and their relationship to your problem) and
			       problem(s) to be solved on the graph.
       2.  Algorithms Chosen:  Reasons for the choices and solution relation
			       to underlying problem(s).
       3.  Results Obtained:   Discuss the results and their relationship to
			       to underlying problem(s).