程序代写代做 AVL algorithm graph C Java CE204-5-SP

CE204-5-SP
2

Question 1

(a)
(i) Explain precisely what is meant by the statement “T(n) is O(f(n))”.
[3%]

(ii) Prove directly from the definition of big O that 3n2+11n+6 is O(n2).
[3%]
(b)
Describe what is meant by the halting problem and give a brief outline of how it can be
[11%]

proven that it has no algorithmic solution.

(c)
Describe the mergesort algorithm and comment briefly on its time complexity.
[8%]
3 CE204-5-SP

Question 2

Provide a complete Java class that implements the interface
[25%]

interface CharQueue
{ boolean isEmpty();

void add(char c);
char front();
void removeFront();
}

The class should provide an implementation of a standard first-in-first-out queue. The characters in the queue should be stored in a singly-linked list constructed using of objects of type QueueCell; you must write this class as an inner class. (You must not use the LinkedList class from the Collections Framework).

A no-argument constructor should be provided to ensure that a newly-created queue will be empty.

If applied to an empty queue the front and removeFront methods should throw an exception; you may assume that an appropriate QueueException class has been declared.
CE204-5-SP
4

Question 3

Consider the following directed graph

A
6
B

8
1
4
3

C

D
E

5

8

(a)
Show how the above graph would be represented using an adjacency matrix.
[3%]
(b)
Describe Dijkstra’s algorithm for finding shortest paths in a weighted directed graph.
[10%]
(c)
Show, step by step, the use of Dijkstra’s algorithm to find the shortest path from the
[12%]

vertex A to each other vertex in the graph shown in part (a) above. At each step the known

and frontier sets should be clearly indicated.

5 CE204-5-SP

Question 4

(a) The following interface specifies the binary tree type.
[7%]

interface BinaryTree

{ boolean isEmpty(); T rootValue(); BinaryTree leftChild();
BinaryTree rightChild();
}

Write a method that takes an argument of type BinaryTree and uses an in-order traversal to calculate and return the number of strings of length less than 10 in the tree specified in the argument.

(b) Show, step by step, the results of inserting the following numbers (in the order in which [18%] they are listed) into an initially-empty binary search tree, using the AVL rebalancing algorithm when necessary in order to ensure that the tree is AVL-balanced after each insertion.

4 7 19 33 21 1115

END OF PAPER CE204-5-SP