Data Structures and Algorithms
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP2003J: Data Structures and Algorithms
Introduction
The goal of this assignment is to program some graph implementations.
Download the file Assignment-2-Source.zip from Brightspace. The
contents of this file include the following important classes and interfaces:
• All the interfaces you require for making a Graph. In particular, the
IGraph interface includes comments describing all of the methods that
a graph implementation should contain (these are in the graph.core
package).
• An implementation of a Linked List, which you will need within your
implementation (this is in the graph.util package and is named
DLinkedList). You should not use built-in Java data structures for
this assignment.
• An example of a Graph implementation: EdgeListGraph. You should
study this file carefully, as the other implementations have some similar
characteristics (this is in the graph.impl package).
• A program called EdgeListTest that shows some examples of code
that can test some of the methods in the graph implementation (this is
in the default package).
You are required to:
1. Implement an Adjacency List graph (in a file called
AdjacencyListGraph)
2. Implement an Adjacency Matrix graph (in a file called
AdjacencyMatrixGraph).
In each case, you should also create a new testing class similar to
EdgeListTest to check that your implementation is correct. Note: The
program I have provided does not test all of the methods in the graph
implementation. You should add some more tests to check other methods
(e.g. removing the vertex HNL should mean that the number of incident edges
on LAX to decrease by one).Submission
This is an individual programming assignment. Therefore, all code
must be written by yourself. Assignment 1 contained some advice
about avoiding plagiarism in programming assignments.
• All code should be well-formatted and well-commented to describe
what it is trying to do.
• Submit a single zip file to Brightspace, with the following contents:
o The AdjacencyListGraph, AdjacencyMatrixGraph,
AdjacencyListTest and AdjacencyMatrixTest classes.
o If your testing code imports some other graphs from a text file,
this text file may be included also. Do not include any extra Java
files.Assignment 2 Grading Rubric
This document shows the grading guidelines for Assignment 2 (Implementation of
Adjacency List and Adjacency Matrix Graphs). Below are the main criteria that will be
applied for the major grades (A, B, C, etc.). Other aspects will also be taken into account
to decide minor grades (i.e. the difference between B+, B, B-, etc.), including:
- Readability and organisation of code (including use of appropriate functions,
variable names, helpful comments, etc.).
- Quality of solution (including code efficiency, minor bugs, etc.).
Passing Grades
D Grade
Good implementation of an Adjacency List Graph or Adjacency Matrix Graph, plus some
basic testing.