Hi there! For my second year course Data Structures and Algorithms, I had an assignment where I had to create various programs, from linked list implementations of stacks to finding the largest submatrix sum in a given matrix. However, the final question was a research question, where I had to research and document the theoretical and emperical performance of two algorithms that are commonly used to extract the Minimum Weighted Spanning Tree (MWST) from a graph G, namely Prim’s and Kruskal’s algorithm. I found this research assignment fascinating and so would like to share it with you.

The actual emperical graphs were a bit wonky if you look, I need to spend more time on gnuplot to figure out how to fix this. I would want to run more comparisons between algorithm to verify them. This could be done with graphs with different densities with relative ease as the number of 0’s in the matrices used can easily be changed. Furthermore, I would like to implement Neeraj Mishra’s (thecrazyprogrammer.com) and fedelebron’s (fedelebron.com) code of Kruskal’s and Prim’s algorithm on my program for working out the runtime of the algorithm and plotting this in Gnuplot. This is empected to yield more accurate results. Another area of interest would be to investigate the possible minimum spanning forest case in Kruskal’s algorithm.

Enjoy the research report I created for this assignment below! This will give the the technical details such as the asymptotic growth of each algorithm and  which algorithm works best for dense graphs.

 

And if you have read this far, here is your reward (the original PDF!):

Jonathan_Taylor_1665909_COMS2004_Assignment_Q7