**Candidate**:
You must prepare your solution to
this programming exercise *in advance*.
The designated platform, on which your solution must be demonstrated and on
which it will be marked, is the `**gcc**' compiler running on `**Linux**'.
If you develop a solution on another platform, it is your responsibility
to ensure that it works correctly on the designated platform.
Read the information under the [prac' guide],
[on C and code modularity], [missed pracs]
and [plagiarism] links on the
[home page].
It is better to have a program that does only part of the prac'
but that compiles and runs than to have a more complex program
that crashes or, even worse, does not compile.
So keep copies of old working partial solutions.

Unless otherwise noted, you must write all the code yourself, and may not use any external library routines, the usual I/O (e.g. printf) and mathematical (e.g. log) routines excepted.

*Prac's are marked on the performance of your program
and on your understanding of it.
I.e. Perfect program with zero understanding => zero marks!
``Forgetting'' is not an acceptable explanation for lack of understanding.*

The *on-line* versions of the prac's
may include [links], corrections and supplementary material and are to
be taken as the reference documents.

**Demonstrators**: Are not obliged to mark programs
that do not compile or that crash.
Time allowing, they will try to help in tracking down errors,
but they are not required to mark programs in such a state,
particularly those that do not compile.
Therefore keep backup copies of working partial-solutions (also see above).

**NB.**
Recall that each week's prac' groups are set their own specific problems.
Make sure that you do the correct problem for *your* week!
*You will get zero marks if you solve the wrong problem*.

The exam, and the prac' work (1--5), are both hurdles (half-marks) for CSE2304. If you fail one, or the other, or both, the highest mark that you can get for the subject is 44%(N).

**Objectives**: Graph algorithms.

You need your solution to the previous prac'.

Consider the m×m adjacency-matrix calculated by your previous program.
It is the adjacency matrix of a directed(D) graph,
but it can be made undirected(U) by using

d_{U}(x,y) =
d_{U}(y,x) =
(d_{D}(x,y) + d_{D}(y,x))/2

**Extend** your program to use
Prim's algorithm
to calculate
the *minimum spanning tree* (MST) of the undirected graph
of m DNA sequences and
print the MST in some simple, non-graphical, way.

(Recall that m<<100 and that a DNA sequence might contain millions of bases. [sample data (click)])

Solves prac 4A and also
calculates the weight of the minimum spanning tree
-->3 marks.

Prints the minimum spanning tree, i.e. its edges, in some simple way -->5 marks.

Program is elegant and totally correct with evidence (useful assertions for verification, and also programmer's own test data etc.) -->6 marks.

Prints the minimum spanning tree, i.e. its edges, in some simple way -->5 marks.

Program is elegant and totally correct with evidence (useful assertions for verification, and also programmer's own test data etc.) -->6 marks.

You need your solution to the previous prac'.

Consider the m×m (directed) adjacency-matrix of a graph TG over m texts as calculated by your previous program.

**Extend**your program to do the following:- Form a directed
*sub*-graph, G, of TG by starting with the vertices (texts) but no edges and joining each vertex to its*nearest neighbour*(other than itself). The nearest neighbour of x is some y, y!=x, that minimises the edge length <x,y> in TG; edge <x,y> is added to G. G might or might not be connected.

Print the adjacency matrix of G. Note that if x's nearest neighbour is y, y's nearest neighbour might not be x. - Now treating G as
*undirected*(i.e. if <x,y> is an edge in G, make sure <y,x> is also), find its connected components (there could be between 1 and m of them); you might consider Warshall's algorithm.

Print the connected components in some simple way.

(Recall that m<<100. [sample data (click)])

Solves prac 4B and also
finds the nearest neighbour of each vertex (text) correctly
-->3 marks.

Prints the connected components (sets of vertices) of the solution correctly in some simple way -->5 marks.

Program is elegant and totally correct with evidence (useful assertions for verification, and also programmer's own test data etc.) -->6 marks.

Prints the connected components (sets of vertices) of the solution correctly in some simple way -->5 marks.

Program is elegant and totally correct with evidence (useful assertions for verification, and also programmer's own test data etc.) -->6 marks.

© L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800. Created with "vi (Linux & IRIX)", charset=iso-8859-1