CSSE 230: Minimum Spanning Tree Assignment

In this assignment you will implement and analyze an algorithm for finding a minimum spanning tree of an undireted graph. You are asked to use the assistance of GenAI tools such as ChatGPT to complete this assignment. You will learn about prompt engineering and the power and limitations of Generative AI.
  1. Please work on this assignment with a partner from this class.
  2. Pick either Prim's algorithm or Kruskal's algorithm for determining an MST.
  3. Use ChatGPT and other resources to understand the algorithm. You will likely have to experiement with different prompts to get it to give you something you can understand. As part of your experience report, explain the algorithm.
  4. Use ChatGPT to implement the algorithm using proper O/O Java code.
  5. Develop unit test cases and use them to test and degug your code. If the unit test cases were provided by GenAI, you need to verify that they are indeed good test cases and you will likely have generate additional test cases.
  6. Conduct performance analyses of your implementation on several large graphs. Here too, try to use GenAI to give you some large graphs.
  7. Conduct a precise runtime analysis of your implemented algorithm. Notice that the runtime will depend on the data structures you chose to implement the algorithm. Please by mindful that some data structures may have poor runtime, depending on where you insert and remove thing as well as where you look up things. Again, feel free to use ChatGPT, but ensure you are precise about how the different functions contribute to the overall runtime. You could ask genAI to perform the analysis for you, but be weary of its response.
  8. Based on the prior item, provide the Big-Oh analysis.
  9. Submit a report which contains:
    1. your names,
    2. the name of the algorithm you picked,
    3. your responses or the data requested above
    4. a subjective evaluation of your experience of prompt engineering a solutions to a complex algorithm as well as its analysis.
    5. A diagram or screen shot of a small sparse graph and a small fully connected graph combined with the MST returned by your code.
    6. Anything else I should know about your code or anything interesting you discovered.
  10. Submit a zipped copy of your code, including the graph and any other classes you developed for your code.
  11. This assignment is worth 100 pts.