Summer Diet 1 /Turn over
Tuesday 5 May 2020, 14:15 BST
(24 hour open online assessment – Indicative duration 2 hours)
DEGREES of MSc Information Technology, Software Development and IT
Cyber Security
Algorithms and Data Structures (M)
COMPSCI 5004
Answer All 3 Questions
This examination paper is worth a total of 60 marks
There are 3 questions, worth 26, 12 and 22 marks respectively
Summer Diet 1 Continued Overleaf/
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.
(i)
Add new vertex
v6 with label g
Add new edge
(v3, v6)
Summer Diet 2 Continued Overleaf/
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.
public interface Graph>
{ public boolean addEdge (Edge e);
// add edge e to graph g if its vertices are already in g
// and e doesn’t already exist in g
// return true if successful and false otherwise
public boolean addVertex (Vertex v);
// Add vertex v to graph g if g 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 edge 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
}
Box 1: a Graph interface
Summer Diet 3 Continued Overleaf/
(a) Describe how you would implement Graph 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 decide for yourself exactly how vertices and edges should be
compared (and thus ordered).
You may assume that any instantiation of your class has at most 20 vertices and at
most 50 edges at any time.
You do not need to 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.
[18]
For each of the Graph methods, analyse the time complexity of the underlying
algorithms used.
[2]
(b) Suppose that you have application code that employs a graph myGraph declared
thus:
Graph myGraph;
You realise that it would be useful to print the vertices of myGraph in ascending order
(regardless of whether your ArrayGraph implementation is used, or any other).
Describe how you would use an iterator to do this. Show how you would include a
suitable iterator method in your interface, and how you would implement it for your
ArrayGraph. Describe then how could use your iterator to print the vertices of
myGraph from the application code, and any other changes you must make.
[6]
(26 marks)
2. (a) Describe the process of inserting the values 9, 4, 7, 5, 1, 3, 8, 11 into an empty
Binary Search tree in the given order (i.e. without balancing).
Summer Diet 4 Continued Overleaf/
Describe the tree after each insertion. If you are unable to draw the tree, you can
describe it by describing where the each new vertex is placed (e.g. “as the right child
of the node containing the value 5”) and by giving the preorder traversal after each
insertion.
[4]
(b) Now delete the value 4 from your tree. Explain the process involved and describe
your new tree as above.
[2]
(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).
[6]
(12 marks)
3. (a) Box 2 shows an interface for a Map abstract data type. Explain carefully what is
meant by a map.
[2]
(b) Using the contract of Box 2, write application code to do the following:
(i) Declare a map that will be used to record the surnames, addresses, and
current balance (in whole pounds) of users of an online shopping site.
Assume that users may have the same surname, but no two users have the
same name and address combination.
(ii) Add the following to your map:
- a user with surrname Smith, address 5 Wilson Street, and balance
150,
- a user with surname Smith, address 12 Vine Crescent, and balance
440,
- a user with surname Jones, address 160 Rose Lane, and balance
60.
(iii) Remove the user with name Smith and address 5 Wilson Street.
(iv) Combine the entries of this map with another map, newMap of the same
type, ensuring that for any user that appears in both maps, the balance
from newMap is maintained.
(v) Increase the balance of all users by 15 pounds.
Summer Diet 5 Continued Overleaf/
[6]
(c) Explain how a map could be represented by a closed-bucket Hash Table (CBHT).
Briefly explain how each of the operations of Box 2 apart from the putAll
operation would be implemented.
[5]
(d) Suppose that the names and details of about 100 mail servers are to be stored. It is
essential that we can retrieve a server’s details efficiently given its name. Assume
that a server name consists of letters and full-stops (such as “Glasgow.ac.uk” or
“dcs.gla.ac.uk” or “gmail.com”), with no distinction between upper-case and
lower-case letters.
Design an efficient hash-table customized for this application.
[5]
(e) Suppose that M1 and M2 are two maps storing the same type of data, and that M1
is implemented using a CBHT with a table of size m. If M1 and M2 contain n1 and
n2 elements respectively, what are the best-case and worst-case time complexities
of the putAll operation (see Box 2) in terms of n1 and n2, when this and
that are assumed to be M1 and M2 respectively? You may assume that M2 has
an iterator that allows each element to be accessed in O(1) time. Explain your
answers.
[4]
(22 marks)
Summer Diet 6 /END
public interface Map