代写COMPSCI 5004、Software代做、Java代写、Java编程设计调试

日期：2020-05-07 11:09

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

public interface Graph<F extends Comparable<F>>

{ public boolean addEdge (Edge<F> 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<F> 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<F> e);

// delete edge edge if it is present in graph

// return true if successful and false otherwise

public boolean deleteVertex (Vertex<F> 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<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).

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<String> 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<K,V> {

// A Map<K,V> object represents a homogeneous map with keys of type

// K and values of type V.

public void clear ();

// Make this map empty.

public void put (K k, V v);

// Add an entry to this map with key k and value v, replacing any

// existing entry

public void remove (K k);

// Remove the entry with key k from this map, if any.

public V get (K k);

// Return the value from the entry with key k in this map, or null if there

// is no such entry.

public Set<K> keyset ();

// Return the set of all keys in this map.

public void putAll (Map<K,V> that);

// Overlay this map with that, i.e., add all entries of

// that to this map, replacing any existing entries

// with the same keys.

}

Box 2 A Map interface.