[2022] UCD - COMP2003J: Data Structures and Algorithms 2 - Assignment 3: Shortest Paths and Minimum Spanning Trees
Introduction
The goal of this assignment is to analyze and program some graph algorithms and visualize them. This assignment includes three tasks.
Task 1 - Shortest Paths
1. (5%) A program called DijkstraLabeller.java tries to label the shortest path for a given weighted graph with a starting vertex by harnessing Dijkstra’s algorithm. It may work but not be perfect. Please study this
implementation carefully and point out its weakness(es), which can be such as lacking enough information in returned objects, low efficiency etc. When you find out a point, you need to make an in-depth analysis. For example, assume that this implementation has a low-efficiency issue; you need to specify where they are from, their time complexity, etc.
2. (10%) Based on the analysis from the previous step, you need to reimplement this solution to solve these issues. You need to create a new java class named DijkstraLabeller2.java within the package dsa.algorithms. If needed, you can create a few other classes. For example, as we mentioned in our lecture, if you want to use an adaptable priority queue, you may need to create a new interface and its implementation as well. In your solution, you can use java built-in data structures, such as Map, List etc. However, a graph and its edges
and vertices must be represented by the classes provided within the assignment.
3. (5%) Create a test class named TestDijkstraLabeller.java to check that your solution is correct and make comparisons with the previous solution.
Task 2 - Minimum Spanning Trees
1. (5%) A program called KruskalLabeller.java manages to label the minimum spanning tree in a given graph by utilizing Kruskal’s algorithm. Similar to Task 1, please study this implementation carefully and point out its weakness(es), particularly in terms of its efficiency.
2. (10%) Based on the analysis from the previous step, you need to reimplement this solution to solve these issues. You need to create a new java class named KruskalLabeller2.java within the package dsa.algorithms. If needed, you can create a few other classes. For example, you may need to implement Union-Find structure. In your solution, you can use java built-in data structures, such as Map, List etc. However, a graph and its edges and vertices must be represented by the classes provided within the assignment.
3. (5%) Create a test class named TestKruskalLabeller.java to check that your solution is correct and make comparisons with the previous solution.
Task 3 - Visualization
(10%) Visualization can help us to better understand graphs and examine our graph algorithms. This task requires you to study the existing java-based techniques for graph visualization and choose a suitable one to implement a solution to visualize the graphs used in your testing in Trask 2 and Task 3 anddemonstrate the process of Dijkstra's algorithm and Kruskal's algorithm.
Instructions
• Download the file Assignment3-Source.zip from Brightspace. The contents of this file include DijkstraLabeller.java and KruskalLabeller.java and all their dependent classes.
• When you study the weaknesses of the existing implementations, you need to record these weaknesses and your analysis in your report.
• In your solutions of Task 1 and Task 2, a graph must be represented by IGraph, and its vertices and edges must be represented by IVertex and IEdge, which are defined in dsa.iface package. a Graph implementation: EdgeListGraph is provided in dsa.impl package, you should use it in your testing to hold your graph data.
• You can design your own returned data type to hold any data you need for the next step to visualize graphs.
• This assignment requires you to do some independent research outside of what is directly covered in the lectures. For example, two chapters in Goodrich and Tamassia’s book are suggested to read, i.e., Chapter 9.5 Adaptable Priority Queues, Chapter 14.7.3 Disjoint Partitions and Union-Find Structures. You can learn the solutions provided by these chapters and then make your own solutions.
• When testing your implementation and making comparisons, you should compare their efficiencies at different graphs and record the results and analyze them in your report.
• In the task of visualization, you can use any java-based components.
• You should summarise the studies for graph visualization and briefly depict your solution. It is essential to put critical screenshots of the visualization produced by your program into the report. This is an individual assignment. Therefore, all code and the report must be written by yourself. Assignment 1 contained some advice about avoiding plagiarism in programming assignments.
• Submit a zip file to Brightspace, which should include all java files, libraries, and data used in your project. All code should be wellformatted and well-commented to describe what it is trying to do.
• Submit a pdf report to Brightspace. This report should be a humanreadable document (i.e., do not simply include code). In your report, it is recommended to have the following essential topics, but not limited:
o Record the weaknesses of the existing implementations and provide your in-depth analyses.
o Depict any tricks (novel or different ideas) used in your solution.
o Document the testing strategies and record results and provideyour analyses.
o Include a short literature review about Java-based graph visualization.
o Depict your visualization solution.
o List newly added java classes, and describe their functionalities.
• The pdf file of your report must be submitted as a separate file, i.e., it cannot be compressed into the zip file with your code or data, for thepurpose of originality checking.
