CE204-5-SP
2
Candidates must answer ALL questions.
Question 1
(a) (i)
Prove directly from the definition of big O that 5n2+9n+7 is O(n2).
[3%]
(ii)
State with reasons a big O estimate for the worst-case time complexity of the following
[5%]
function.
int myfunc(int n)
{ int result = 0;
for (int i = 0; i
if (i%j == 0)
result += j;
return result;
}
(b) Provide a complete Java class that implements the interface
[17%]
interface StringStack
{ boolean isEmpty(); void push(String s); String top();
void pop();
}
The class should provide an implementation of a first-in-last-out stack and use a linked list to store the contents of the stack. The linked list must be implemented using list cells (i.e. you are not allowed to use the LinkedList class from the collections framework); the cell class should be written as an inner class. If applied to an empty stack the pop and top methods should throw an exception – you may assume that an appropriate StackException class has been declared. A no-argument constructor should be provided to ensure that a newly-created stack will be empty.
.
3 CE204-5-SP
Question 2
(a) Explain what is meant by a non-computable function, and give an outline of a proof [10%] that such a function exists.
(b) Describe the insertion sort algorithm and comment briefly on its time complexity.
[7%]
(c) The following interface specifies the binary tree type.
[8%]
interface BinaryTree
{ boolean isEmpty(); T rootValue(); BinaryTree
}
Write a method that takes an argument of type BinaryTree
CE204-5-SP
4
Question 3
(a) Explain what is meant by the term connected as used to describe undirected graphs.
[2%]
(b) Describe Kruskal’s algorithm for finding shortest paths in a connected undirected
[10%]
graph.
(c) Show, step by step, the use of Kruskal’s algorithm to find a minimum cost spanning [13%] tree for the graph shown below. At each stage you should show the connection sets.
A
8
B
7
9
4
2
CDE10
5
5
CE204-5-SP
Question 4
(a) Explain the meaning of the terms balanced and AVL-balanced as used to describe
[4%]
binary trees.
(b) Give examples of binary search trees containing exactly 5 nodes that are (i) neither [3%] balanced nor AVL-balanced, (ii) AVL-balanced but not balanced, and (iii) both balanced and AVL-balanced.
(c) 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.
2 23 8 33 45 1117
END OF PAPER CE204-5-SP