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.