Algorithms and Data Structures (M)
Algorithms and Data Structures (M) Outline implementation of a Graph ADT. Note that graphs are covered in various textbooks but don’t be tempted to use···
This coursework should take between 2 and 3 hours to complete. It is divided into two parts: Algorithms and Data Structures (M)
- Outline 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 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. Do not submit full code (we will not run any code – we will be marking your descriptiononly).
- Some constructions of binary search trees (insertion and deletion to/from a BST, and insertion to an AVL tree). You will submit annotated drawings. Either use drawing software or draw it out by hand and submit a (clear) photo of your drawing (inserted into your pdf document). We will be marking the correctness of your answer, not your ability to use fancy
- 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 For any edge (vi, vj), the labelof vertex vi is smaller than the label of vertex vj.
For example Algorithms and Data Structures (M)
the first graph (i) in the illustration below 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.
Note that it is not possible to:
- add a new vertex to a graph whose label is the same as that for avertex already in the graph,
- remove a vertex v that is not in the graph (even if the graph contains avertex with the same label as v),
- add an edge between vertices that have not been added to thegraph,
- add an edge if it already exists in thegraph,
- remove an edge that is not in the
Box 1 contains a Java interface for a simplified graph, Graph (whose vertices can have labels of any comparable type F). Algorithms and Data Structures (M)
The interface refers to classes Vertex<F> and Edge<F> 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.
Describe how you would implement the Graph interface as a class
ArrayGraph.java whose instance variables consist of:
- two arrays vertices and edges of type Vertex<F> and Edge<F> respectively containing the current vertices and edges in the graph, eacharray sorted in ascending order, and
- two integer variables representing the current numbers of vertices and
Note that you must decide for yourself exactly how vertices and edges should be compared (and thus ordered). This information should be included in your description.
You may assume that any instantiation of your class has at most 20 vertices and at most 50 edges at any time.
Do not provide full Java code (although you may find that it helps to provide fragments), it is your description that is important. You also do not need to provide full implementations of the Vertex and Edge classes but should indicate their instance variables and the signatures of any methods you refer to in the rest of your answer. If you require any helper methods, give the signatures (and a commented description) of each method, but you do not need to implement them.
For each of the Graph methods, analyse the time complexity of the underlying (array) algorithms used. Algorithms and Data Structures (M)
Provide outline code with detailed, clear comments.
(12 marks)
- (a) Describe the process of inserting the values 12, 9, 4, 6, 5, 15, 14, 16, 17, 18 intoan empty binary search tree in the given order (i.e., without balancing).
Draw the tree after each insertion. If you just submit a complete graph without the intermediate steps you will lose marks.
- Now delete the value 12 from your tree. Explain the process involved and draw your new tree.
- Do the same as you did for (a), but this time add the vertices to an empty AVLtree (i.e., with balancing). If you use a rotation include details in your description (e.g. single left rotation about the node containing value 4, or double right-left rotation about the node containing 3 – which you can abbreviate as SL(4), or DRL(3) respectively, and so on).
(10 marks)
更多其他：代写作业 数学代写 物理代写 生物学代写 程序编程代写 英语单词语法（一）
