程序代写代做 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))” and explain its
[5%]

relevance when estimating the running times of programs.

(ii) Prove directly from the definition of big O that 5n2+11n+9 is O(n2).
[3%]
(b)
Describe the selection sort algorithm and comment briefly on its time complexity.
[8%]
(c)
The following grammar describes a simple language of arithmetic expressions.
[9%]

explp exp rp | exp op exp | number

opplus | minus | times

The symbols, lp, rp, plus, minus and times refer to the lexemes (, ), +, – and * respectively and the symbol number refers to any non-negative integer.

Provide a declaration for a Java class that could be used to store parse trees for this grammar. The methods of the class do not have to be declared.

.
3 CE204-5-SP

Question 2

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

interface StringQueue

{ boolean isEmpty(); void add(String c);

String 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). The front and removeFront methods should throw an exception of type QueueException when applied to an empty queue; you may assume that the QueueException class has already been written.
CE204-5-SP
4

Question 3

(a)
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.

(b)
Show how the following directed graph would be represented using adjacency lists.
[3%]

A
5
B

3
2
3
4

C

D
E

4

9

(c)
Show, step by step, the use of Prim’s algorithm to find a minimum cost spanning tree
[11%]

for the undirected graph shown below. The vertex labelled A should be used as the

starting point.

A

B

3

5
4
2
C

D

E
9

2

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 non-letters in the tree specified in the argument. (You should use the method static method isLetter from the Character class to check if a character is a letter.)

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

3 6 18 33 27 1215

END OF PAPER CE204-5-SP