辅导 program、讲解 Java程序语言
Algorithms and Data Structures (M)
Assessed Coursework
This coursework is worth a total of 30 marks and contributes 20% towards the course credit.
This coursework should take between 6 and 8 hours to complete. It is divided into two parts:
1.Exercise in using the Java Map interface and in using a Map implementation (namely, HashMap). Note that we do not study the Map ADT until the end of the course. The purpose
of this exercise is not to know how a hashmap is implemented, rather how to use it. That is, to demonstrate that you understand how to use Java interfaces and implementation classes (from your experience with other ADTs, and the examples using interfaces and implementations, like those from the introduction slides seen in Lecture 1).
2.Implementation of a Graph ADT. Note that graphs are covered in various textbooks but
don’t be tempted to use any implementation you see in them. This question is very specific, and you must follow the instructions completely. You will submit your code for testing together with a description document. In your description document you should provide outline code containing method signatures and detailed comments explaining how your methods work, what underlying (array) algorithms you would use and the complexity of each of the algorithms used. Most of the marks will be awarded for your description.
Submit all required parts of your solutions to both parts of the assignment (see full submission details near the end of this document). All classes and pdf documents should contain your name and student number. You should submit your coursework by Monday
March 18th at 4.30 pm.
1.[5 marks]
This part of the exercise is to show that you understand the Java interface Map and how to use one of its implementations, HashMap.
You have been provided with an outline of a class, AssE1_outline.java. You should make a copy of AssE1_outline.java and rename it AssE1.java.
ADS Assessed Coursework 2024 1
Complete the AssE1.java class as instructed in the comments within the file (address issues 1-8). Do not include any package declaration. You should include any import statements necessary for me to run the program from the command line thus:
javac AssE1.java
java AssE1 readersAndBooks1.txt readersAndBooks2.txt
You may add helper methods if you need to, but any unnecessary complexity (of code) will be penalized. Note that your program should still run if I replace the arguments in the above with other similar files (containing lines of pairs of strings), but text files readersAndBooks1.txt and readersAndBooks2.txt have been provided for illustration and to help you test your class.
When you are happy with your class, run it and store the output in a pdf document called AssE1_output.pdf (remove any additional print statements you may have added to your methods for testing purposes first). You should include your name and student number at the top of this document.
Full submission instructions will be included at the end of this document, but for this part of the exercise you will submit your two files: AssE1.java and AssE1_output.pdf.
2.[25 marks] A graph is an abstract data type (ADT) which consists of a set of labelled points, or vertices and a set of pairs of vertices, called edges. For any edge (vi, vj), the label of vertex vi is smaller than the label of vertex vj.
For example, the first graph (i) in Fig. 1 has vertices which are labelled using characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘f’. The vertex set is {v1, v2, v3, v4, v5} and the edge set is {e1, e2, e3, e4} where e1 is (v1, v2), e2 is (v2, v3), e3 is (v2, v4) and e4 is (v4, v5). Graph (ii) is the result of adding a new vertex and a new edge. Graph (iii) is the result of an attempt to add a new vertex with a label identical to that of an existing vertex, and graph (iv) is the result of deleting a vertex. Note that if a vertex is deleted, all edges associated with that vertex are deleted.
ADS Assessed Coursework 2024 2
Figure 1: Example graphs and operations
Note that it is not possible to:
-add a new vertex to a graph whose label is the same as that for a vertex already in the graph,
-remove a vertex v that is not in the graph (even if the graph contains a vertex with the same label as v),
-add an edge between vertices that have not been added to the graph,
-add an edge if it already exists in the graph,
-remove an edge that is not in the graph.
Box 1 contains a Java interface for a simplified graph, Graph (whose vertices can have labels of any comparable type F). The interface refers to classes Vertex and Edge which define a vertex of type F and an edge of type F respectively. Note that if e=(v1,v2) we say that e contains v1 and v2.
ADS Assessed Coursework 2024 3
public interface Graph>
{ public boolean addEdge (Edge e);
//add edge e to graph if its vertices are already in graph
//and e doesn’t already exist in graph
//return true if successful and false otherwise
public boolean addVertex (Vertex v);
//Add vertex v to graph if graph doesn’t already contain v
//or any vertex with the same label as v
//return true if successful and false otherwise
public boolean deleteEdge (Edge e);
//delete edge e if it is present in graph
//return true if successful and false otherwise
public boolean deleteVertex (Vertex v);
//delete vertex v if it is present in graph, and all edges that contain v
//return true if successful and false otherwise.
public Set> vertexSet();
//return a set containing all vertices
public Set> edgeSet();
//return a set containing all edges
}
Box 1: Graph interface
Implement the Graph interface as a class ArrayGraph.java whose instance variables consist of:
-two arrays: vertices and edges, of type Vertex and Edge
respectively containing the current vertices and edges in the graph, each array sorted in ascending order, and
-two integer variables representing the current numbers of vertices and edges.
Note that you must also implement (generic) Vertex and Edge classes, and you must decide for yourself exactly how vertices and edges should be compared (and thus ordered). This information should be included in your description document, which is described below.
You may assume that any instantiation of your class has at most 20 vertices and at most 50 edges at any time.
You will be submitting your full Java code, which I will run using a test program like
ADS Assessed Coursework 2024 4
the one provided – TestGraph.java. I will not be looking at your code in detail other than for this testing stage, although I may look closer to determine why it doesn’t run. You must ensure that your program runs with the provided test class (e.g., ensure that your classes contain the necessary constructors).
In addition to your code, you should include a pdf document graphDescription.pdf, describing your implementation. This document should not contain large amounts of code (although you may find that it helps to provide fragments, and you should include important parts of your code, such as your class signatures and instance variables), it is your description that is important. You also do not need to provide full implementations of the Vertex and Edge classes within the document but should indicate their instance variables and the signatures of any methods within those classes that you refer to in your description. If you require any helper methods, give the signatures (and a commented description) of each method in your document, but you should not include the full implementation. Note that if you program does not work, include details of why you believe it does not in this document.
For each of the Graph methods, analyse the time complexity of the underlying (array) algorithms used (and state what these underlying algorithms are).
Summary: Provide full code plus description document containing outline code with detailed, clear comments, and complexity analysis of your implementation of the Graph methods.
Submission instructions:
You should submit a single zipped folder named xxxxxxxx.zip where xxxxxxxx is replaced with your student id (e.g. 0123456a). The folder should contain two subfolders: AEx1 and AEx2 containing your solutions for parts 1 and 2.
AEx1 will contain two files: AssE1.java, and AssE1_output.pdf only.
AEx2 will contain four files: Vertex.java, Edge.java, ArrayGraph.java, and graphDescription.pdf only.
Marking scheme:
1.program runs as expected and output provided: 5 marks.
2.Vertex.java, Edge.java, ArrayGraph.java work with test class: 5 marks. Class signatures : 4 marks.
Node and Edge descriptions: 6 marks.
graphDescription:
Descriptions of Graph methods (including descriptions of any helper methods): 6 marks.
Complexity analysis of Graph: 4 marks.
ADS Assessed Coursework 2024 5