CE204-5-SP
2
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 7n2+11n+5 is O(n2).
[3%]
(b)
Describe what is meant by the halting problem and give a brief outline of how it can be
[12%]
proven that it has no algorithmic solution.
(c)
Describe, with the aid of pseudo-code, the mergesort algorithm and comment briefly on
[8%]
its time complexity.
(d)
(i)Explain what is meant by terms connected and acyclic as used to describe
[4%]
undirected graphs.
(ii) Explain what is meant by a spanning tree for a connected undirected graph.
[4%]
(iii) Draw any two spanning trees for the following undirected graph.
[4%]
A B
C D E
.
END OF SECTION A
3 CE204-5-SP
SECTION B
Candidates must answer TWO questions from Section B.
Question 2
(a) Provide a complete Java class that implements the interface
[28%]
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).
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. A no-argument constructor should be provided to ensure that a newly-created queue will be empty.
(b) Comment briefly on the time complexity of the operations provided in your answer to [2%] part (a).
Section B continues…
CE204-5-SP
4
Section B(continued)
Question 3
Show how the directed graph
7
A B
8 1 3 4
C
D
E
5
8
would be represented using:
(i)
an adjacency matrix; and
[3%]
(ii)
adjacency lists.
[3%]
(b) Describe, with the aid of pseudo-code, Dijkstra’s algorithm for finding shortest paths in [10%] a weighted directed graph.
(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.
Section B continues…
5 CE204-5-SP
Section B(continued)
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) State the meaning of the term AVL-balanced as used to describe binary trees.
[2%]
(c) Show, step by step, the results of inserting the following numbers (in the order in which [19%] 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 7 17 33 23 1113
END OF SECTION B
END OF EXAM PAPER CE204-5-SP