Lab 4 Specifications 311
CSCI 311: Data Structures and Algorithms in Java
Lab 4 Specifications
California State University, Chico
Department of Computer Science
Instructor: Anne Keuneke Assignment #4 Weight 100 points
GENERAL DESCRIPTION
In this assignment we will develop a toolset for a graph ADT.
Documentation should include a structure chart, a specification of
the ADT and program documentation. In addition, for each choice of
implementation or technique, you must specify what is its purpose
and why you chose the particular representation or technique.
THE MODULE TO BE IMPLEMENTED
Below is the formal descriptions of the ADT interface.
Note that these specifications are not complete ADT specifications;
they describe the ADTs in a "stylized" format, giving only suggested
declarations and operation parameter lists. The semantics of the
various operations have been specified in the lectures. A part of
your assignment is to complete the ADT specifications by describing
the Elements, the Structure and the Pre-conditions and Post-conditions
for each operation.
ADT Graphs;
{Exported Operations}
- (C)onnected() {Boolean that states if the graph is connected}
- (B)iConnected() {Boolean that states if the graph is biconnected}
- (A)rticulations() {Returns the articulation points of the graph}
- (M)inCostSpanTree() {Returns the minimun cost spanning tree of the graph}
- (S)SShortestPath(vertexA, vertexB ) {Single Source Shortest Path from A to B}
{Private Operations}
Any that you need to produce the above exports. Specify reasons for
each and why the particular implementation and technique was chosen.
PERFORMANCE MEASUREMENT for EXTRA CREDIT
For any choices made to produce the above operations, for that choice,
implement the alternative and compare (measure time differences).
Examples: Compare Kruskal and Prim, Compare adjacency matrices to
adjacency lists. For each comparison of significant aspects, you
will receive 20 points.
DELIVERABLES
I will produce 4 input files which will consist of graphs. The first line is
the set of vertices, then each edge is represented by a line which has form:
"vertex vertex length", followed by some questions about the graphs. (Questions
will concern only the five export operations since that is all that I,
from the outside, know your module has.) The deliverables include program
listings, documentation and sample output, tables of results for each
of the measured quantities.
You should hand in the following items:
- Program listings, documentation (with reasons for choices) and sample output.
- Tables of results for each of the measured quantities (extra credit problems).
- Comment on sources of errors in your measurements and try to correct for them.
Also explain any unusual or unexpected results to the best of your ability.
Lab 4 Input Files
See this IO shell to set up PARAMs and connect to multiple input URLs