KXT201 Algorithms
Second (Individual) Assignment 2009
Standard Level
Due: 3pm 28th
May
Maximum Minimum Spanning Tree
Introduction
When Prim's algorithm is applied to a connected undirected graph, it computes (the weight
of) a minimum weight spanning tree. For this assignment you need to adapt and
implement Prim's algorithm such that when applied to a connected undirected graph it
computes (as usual) the weight of a minimum weight spanning tree for the graph, and
when applied to an unconnected undirected graph it computes the maximum of the weights
of the minimum weight spanning trees for the graph's connected components. For
example, for the graph below, the weights of the minimum weight spanning trees of the
connected components are (from left to right) 0 {a}, 5 {b, f, g}, 5 {c, d} and 3 {e, h, i},
and the maximum of those values is 5, so this is the value to be computed.
Hint about the adaptation: if you consider what happens when you apply the original
algorithm to an unconnected graph, you will notice that when all the vertices in the
connected component of the starting vertex have become "known", the "nearest unknown"
vertex, which is in a different connected component, is at distance "infinity". (Note: when
vertices tie to be "nearest unknown", you may break the tie as you wish.)
Similarly to the first assignment, this assignment, which is worth 12% of the unit mark,
and marked out of 24, can be attempted at two different levels – "standard" level, worth up
to 21 marks, and "challenge" level, which includes the standard level and is worth up to 3
more marks.
The standard level assignment is described here and the additional work for the challenge
level is described in a supplement.
The Graph
The graph will be a weighted undirected graph, with at least 1 vertex, and at most 10000
vertices, and at most 99999 edges. Vertices will be numbered 0, 1, 2, ...V-1, for a graph
with V vertices. Edge weights will be integers, each at least 0, and at most 1000. (Note that
the number of vertices and the edge weight limits affect the choice of an appropriate value
for "infinity" in the implementation.) The graph must be represented as required below, the
input read as required below, and the output produced as required below. (The input will
be correct, and no extra marks will be given for handling incorrect input.)
a b c
f g
d e
h i
2 4
5
3 2
3 1Testing
Programs will be tested automatically on alacritas / lawson similarly to the first
assignment and marks for each test will be awarded on a pass/fail basis.
System Availability
Experience shows that, unfortunately, the computer system will probably be unavailable or
practically unusable for much of the 72 hours before the deadline. This is not an
unforeseeable misfortune of the type that might justify a request for an assignment
extension.
Data Structure Requirements
The graph must be represented in an adjacency list form, with the implementation of the
lists based upon the dummy header linked list code of the weekly work, modified as little
as required. Each node in an adjacency list must be represented by a dynamically allocated
struct of a type defined (with associated pointer type) as follows:
typedef struct node *node_ptr;
struct node
{
int to_vertex;
int weight;
node_ptr next;
};
where (except for the dummy header node for which the first two items are irrelevant):
to_vertex is the vertex to which the edge goes;
weight is the weight of the edge;
next is the pointer to the next node (/ NULL if this is the last node in the list).
The adjacency list representation of the graph edges must be an array of size 10000 of
(pointers to the header nodes of) such lists, e.g.:
node_ptr g[10000];
(In addition to the representation of the graph, an int array of distances will be needed for
the standard level assignment. It will be acceptable for this to be either of a fixed size of
10000, or dynamically allocated to be of the right size for the number of vertices. Similarly
for a “known” array if you choose to have one. )
O() Running Time Requirements
The running time of your program (not just the Prim's part) must be at most O(V2
) for a
graph with V vertices. Note:
a) You can assume that no individual pair of vertices has more than one undirected edge
with this pair of vertices as the endpoints.
b) You can assume that each call to any of scanf, printf, malloc and free takes time that is
O(1).
c) Although the number of vertices is limited to 10000, and the number of edges to 99999,
the existence of these limits must be ignored for the purposes of the O() running time
requirements.
d) You do not need to make any special effort to have good constants in the running time
of your code, but equally, you must not make any effort to make it excessively inefficient
in constant terms – the marker will limit the length of time for which they wait for a test to
complete.Input and Output
Input must be read with scanf() and output written with printf(). The input will contain
only what is described here, e.g. there will be no spaces other than those mentioned. The
output should contain only the maximum weight on a line by itself, e.g. given the answer
answer, print it as follows:
printf("%d\n", answer);
The input will start with a line containing an integer specifying the number of vertices, a
space, then an integer specifying the number of edges. Then, there will be a series of lines,
one per (undirected) edge. Each such line will contain three integers, with a space between
the first and second, and a space between the second and third. The first integer will be the
weight of the edge. The second integer will be the lower numbered of the vertices at the
ends of the edge. The third integer will be the higher numbered of the vertices at the ends
of the edge. The edges will be in descending order of higher numbered vertex, with edges
of equal higher numbered vertex in descending order of lower numbered vertex.
The following input describes the graph of the Introduction, with vertex a becoming vertex
number 0, vertex b becoming vertex number 1, ... vertex i becoming vertex number 8:
9 7
2 7 8
3 4 8
1 4 7
3 5 6
4 1 6
2 1 5
5 2 3
The corresponding output would be:
5
Submission of the Assignment
Similarly to the first assignment, you must submit electronically the source files, an
appropriate README (plain text, with your name, your student ID number, and an
appropriate brief description of your solution), and a completed electronic individual
assignment cover sheet. However, the relevant directory is now named Standard2, and the
submit command is:
kxt201-submit2
(As mentioned in the first assignment it is possible to re-submit electronically if this
proves necessary.)
Assessment
The marker will assess your assignment as follows:
1. The marker will extract the files from your submission. If the files are present where
required, including a correctly named README file of the right form, with the right
information, this will be worth 2 marks.
2. The marker will attempt to compile (and link) your submission (unaltered) using
(exactly) the following command:
gcc –Wall –ansi –pedantic –O *.c
If this produces the assignment executable, a.out, without any warnings (or errors), this
will be worth 4 marks. If you do not get the 4 marks, but the marker is able to compile(and link) your submission (unaltered), as C, using gcc, to produce an a.out, this will be
worth 1 mark.
3. The marker will read your code. If it is easily readable and understandable, as is
required, and your code appears to make a serious attempt to implement at least an
unadapted Prim's algorithm, using the required data structures, they will assess the code
style in general, such as readability or comprehensibility beyond minimum, out of 4
marks. For example, your use of indentation and blank lines will affect readability. (You
should assume that the readability is judged in terms of what the code looks like, when
read with the "more" command, with standard tab settings of width 8.) Similarly your use
of comments, choice of variable and function names, division of code into functions, and
division of functions between files will affect comprehensibility.
4. If you have used the required data structures, and the marker has been able to compile
(and link) your code (unaltered) as C, using gcc, they will then assess code functionality
by running your code on those tests for which you appear to have made a serious attempt
to implement the relevant computation based upon Prim's algorithm. (An unaltered Prim's
is sufficient for Tests 1 and 2.) As shown in the table below, the marks obtained for
passing a test depend upon whether you have met the O() running time requirements. (As
tests are time limited, failing to meet running time requirements could cause a test to be
failed.)
Test 1
(The graph of
the weekly
work Prim's
example)
Test 2
(Another
connected
graph)
Test 3
(The example
graph of
earlier)
Test 4
(Another
unconnected
graph)
Passing with
both required
Data
Structures and
O()
4 marks 2 marks 2 marks 2 marks
Passing with
required Data
Structures, but
not O()
2 marks 1 mark 1 mark 1 mark
5. If it appears to the marker that your code might obtain more marks for functionality if a
trivial mistake were corrected (e.g. the code fails all tests because there is an additional
space being printed in the printf), then they will correct the mistake and retest, awarding
you half of any additional marks obtained as a result of their work. (You should not count
on the marker getting right in a couple of minutes something that you have got wrong over
a much longer period of time!)
6. If your code as submitted uses the required data structures, is based upon Prim's
algorithm, meets all the O() requirements, and passes all tests, the marker will check
whether all dynamically allocated memory is correctly explicitly freed before the program
terminates, if so, this will be worth 1 mark.
Assignment Individuality / Assignment Specification Clarifications /
Advice On Doing A Programming Assignment
The general remarks of the first assignment apply.