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 only ChatGPT to complete this assignment. If you feel you need to use other resources, please ask me first. 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 as follows:
  2. Pick either Prim's algorithm or Kruskal's algorithm for determining an MST.
  3. Use ChatGPT 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 chatgpt, you need to verify that they are indeed good test cases.
  6. Conduct performance analyses of several 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.
  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.