COMP2003J代写、代写java设计编程

日期：2022-06-20 10:15

Assignment 3: Shortest Paths and

Minimum Spanning Trees

COMP2003J: Data Structures and Algorithms 2

Weight: 50% of final grade

Document Version: 1.0

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 and

demonstrate 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.

Submission

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 provide

your 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 the

purpose of originality checking.