Data Structures and Algorithms

Objectives

Design and implement a program based on a greedy algorithm to solve the Minimal Spanning Tree (MST) problem;

Choose and implement appropriate data structures for the algorithm;

Analyse the efficiency of different implementations of the algorithm in comparison with the brute force algorithm.

Task

You should write a single program which implements Prim's algorithm with different data structures, as well as the brute force search algorithm, to find the MST of an undirected, connected, weighted graph.

Program

Your program should read a symmetric matrix from a text file that describes weighted edges of an undirected, connected graph and find the MST that is saved in an output file as a sequence of edges of the MST. The program also displays the numbers of vertices and edges in the graph and the time spent to find its MST for each data structure used in Prim's and the brute force search algorithms, which can be saved in another output file as well for your later analysis.

Your program should only measure the time spent by the algorithm with its data structure to find the MST so that it is a proper design to use one method/function to implement an algorithm and its associated data structure. For an algorithm that operates on a weight matrix, it takes the weight matrix stored in a two-dimensional array as its parameter; for an algorithm that operates on adjacency lists, it takes adjacency lists you created from the weight matrix. You may create your own list data structures based on arrays. No STL or Java Collection or other collection framework can be used. In the part of the algorithm implementation, you should not use any library functions including maximal or minimal functions but create your own functions to operate on arrays.

Your program should be readable and well commented.

In addition, you needs to create a small program or script to generate the weight matrix for a graph of various vertices and edges, saved to a text file. When you create graphs, you need consider the density and connectivity of graphs. You may use a program/script by other people, with reference to the source, to generate these matrices.
Data Structures and Algorithms

Brute force search algorithm

The algorithm operates on a two-dimensional array that represents the weight matrix.

Prim's algorithm

The algorithm operates on one of the following data structures:

1. two-dimensional array that represents the weight matrix and unordered arrays;

2. adjacency lists and heaps.

Requirements

1. Program

Implement the brute force search algorithm and Prim's algorithm operating on two data structures: matrix and heaps.

2. Report
a. Cover page
Student name Subject code Student number Email ID

b. Introduction (around 200 words)

Describe application scenarios where the MST is applied and identify one application as the background and purpose of your experiments. You should interpret well the meanings of the vertices and edge weights, and why it is an MST problem in your identified application. Cite at least three references.

c. Methods (around 300 words)

Describe algorithms you used in your experiments and data you used to produce the results.

d. Result analysis (no more than 600 words)

Analyse the time complexity of your algorithms and discuss your results. You need to produce results with substantial differences in time spent for each algorithm and data structure. You should use at least one plot to present the results in terms of time spent and graph sizes.

e. Conclusion

Summarise your findings and interpretations.

f. References

Other requirements

You must cite references from academic sources. Internet URLs including Wiki pages are not generally acceptable except they are used for links to resources.

All your programs including scripts will have the following header:

Your programs can be compiled and executed with bash scripts called a3compile and a3run, respectively, on Ubuntu setup in the lab.

o The script a3run should be configured to run for a small graph that can finish within a fraction of a second.
o The script should be configurable to run for a graph of any size.
o The script can execute a program/script to generate the matrix before execute your MST program.
o Failure to compile and run your program to produce results from your scripts will receive 0 mark.

Write a text ?le named readme to explain how your matrix is created, special consideration of your program compilation and execution, or any information related to your program that is necessary to configure and run your program to produce the results in your report. All your results reported in the report must be possibly produced by your submitted programs with easy configuration described in the readme file.

Report, named report.pdf, is created in the PDF format.

Failure to meet any requirements above may result in loss of marks.

Data Structures and Algorithms

Input/output Format

This format specification is to be read with the Assignment 3 tasks requirements.

Input

You program should read an input file name from the command line and uses the adjacency matrix read from the input file with a format as follows.

The integer number of vertices in the graph.
The positive real number weights of one vertex per line, delimited by a space. The value 0.0 is used as no connection.

A sample input file can be created using the provided program, generateAdjM.cpp. You may use the program directly, or adapt it, to create graphs for your algorithms without modifying the output format. If you adapt the program to generate adjacency matrices of different characteristics, you should add a header to the code to explain what you have modified.

Output

MST output

The MST from each algorithm should be saved in a text output file named with prefix, output_mst_*.txt, that contains the edges of MST as a sequence of edges, in selected order using the algorithm * from node 1, each edge and its weight per line and the minimal weight at the last line. Algorithm 1 is always for the brute-force algorithm and algorithm 2 and so on for your other algorithms. For instance,

1-4 2.3

4-3 1.9

4-2 3.2

...   

4-2 3.2

45.6

Statistics output

The output should be displayed to standard output. For each algorithm, the output should consist of the following data, clearly labelled:

Number of vertices: **

1. Brute-force algorithm 1: *** (time unit)

2. Prim's algorithm 2 (matrix): *** (time unit)

3. Prim's algorithm 3 (heaps): *** (time unit)

You may save this information to a file for your analysis and easy plotting later.

Attachment:- MatrixGeneration.zip