Algorithms and Data Structures (M)

Assessed Coursework

This coursework is worth a total of 22 marks

This coursework should take between 2 and 3 hours to complete. It is divided into two parts:

1. 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 description only).

2. 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 software.

Submit both parts of your solution as a single pdf report which contains your name and student number. The aim is for you to submit your coursework by Friday May 4th at 5pm.

Penalty-free submission will be open until Sunday 6 th June at 5.00 pm. This extra time is to allow you a little flexibility but should only be used if absolutely necessary.

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

Box 1: Graph interface

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, each array sorted in ascending order, and

- two integer variables representing the current numbers of vertices and edges.

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.

Provide outline code with detailed, clear comments.

(12 marks)

2. (a) Describe the process of inserting the values 12, 9, 4, 6, 5, 15, 14, 16, 17, 18 into an 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.

(b) Now delete the value 12 from your tree. Explain the process involved and draw your new tree.

(c) Do the same as you did for (a), but this time add the vertices to an empty AVL tree (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)