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.
- Please work on this assignment with a partner from this class as
follows:
- Michael and Zach
- Sid and Andrew
- Eric and Irvan
- Dom and Amruth
- Pick either Prim's algorithm or Kruskal's algorithm for
determining an MST.
- 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.
- Use ChatGPT to implement the algorithm using proper O/O Java
code.
- 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.
- Conduct performance analyses of several large graphs.
- 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.
- Based on the prior item, provide the Big-Oh analysis.
- Submit a report which contains:
- your names,
- the name of the algorithm you picked,
- your responses or the data requested above
- a subjective evaluation of your experience of prompt engineering a
solutions to a complex algorithm as well as its analysis.
- A diagram or screen shot of a small
sparse graph and a small fully connected graph combined with the MST
returned by your code.
- Anything else I should know about your code or anything
interesting you discovered.
- Submit a zipped copy of your code, including the graph and any
other classes you developed for your code.
- This assignment is worth 100 pts.