2 CE204-5-SP
SECTION A
Candidates must answer Question 1 in Section A.
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 5n3+7n+1 is O(n3).
[3%]
(b) (i)
Describe what is meant by the halting problem
[2%]
(ii)
Give a brief outline of how it can be proved that it has no algorithmic solution.
[10%]
(c) Describe the mergesort algorithm and comment briefly on its time complexity.
[7%]
(d) (i) Show the result of inserting the numbers
[5%]
5512517354347247719into an empty binary search tree, in the order given (from left to right), without
performing any rebalancing.
(ii) A class to implement binary search trees of strings is given by the declarations.
[8%]
class BTNode
{ T value;
BTNode
}
public class BST
{ private BTNode
public void insert(String s) {………}
public boolean find(String s) {………}
}
Provide a complete body for the find method.
END OF SECTION A
3
SECTION B
Candidates must answer TWO questions from Section B.
Question 2
Provide a complete Java class that implements the interface
interface CharStack
{ boolean isEmpty(); void push(char i);
void pop();
char top();
}
CE204-5-SP
[26%]
The characters in the stack should be stored in an array. A no-argument constructor should be provided to ensure that a newly-created stack will be empty; in addition a constructor with an argument should be provided to allow the user to specify an initial array size. If the array becomes full the contents of the stack should be copied into a new larger array. If either of the top or pop methods is applied to an empty stack, or if an invalid argument is supplied to the constructor, an exception of type StackException should be thrown; you should provide an appropriate StackException class.
(b) Comment briefly on the time complexity of the operations provided in your answer to [4%] part (a).
4 CE204-5-SP
Question 3
Show how the following graph would be represented using:
(i)
an adjacency matrix; and
[3%]
(ii)
adjacency lists.
[3%]
A
7
B
9
2
3
4
C
D
E
4
9
(b) Describe Dijkstra’s algorithm for finding shortest paths in a directed graph.
[10%]
(c) Show, step by step, the use of Dijkstra’s algorithm to find the shortest path from the [14%] 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 grammar describes a simple language of arithmetic expressions.
[9%]
exp → lp exp rp | exp op exp | number
op → plus | 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.
(b) (i)
State the meaning of the term AVL-balanced as used to describe binary trees.
[2%]
(ii)
Show, step by step, the results of inserting the following numbers (in the order in
[19%]
which 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 5 17 36 25 1115
END OF SECTION B
END OF PAPER CE204-5-SP