=========================preview======================
(COMP271)2006Spring_Final_SOL.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 271 Design and Analysis of Algorithms
Spring 2006
Final Examination (Suggested Solution & Marking Scheme)
LG4204, 8:30am -11:30am, Tuesday, 23 May, 2006
Name: Student No:
Department: Tutorial Section:
This is a closed book exam. You should put everything o. your desk except for stationaries and your student ID. You wont need a calculator.
You should use the back of the pages for rough work and, if necessary, for your .nal answers. There is one blank page at the end in case you need more space. Write legibly and dont usepencils for your .nal answers.
Be concise with your answers. Marks might be deducted for incorrect redundant statements. When describing algorithms, you can use either natural language or pseudo code as long as your descriptions are clear.
1. (5 Points)
Consider two complex numbers a +bi and c +di where i = .1. How to compute their product with only 3 numerical multiplications? (Note that there is no requirement on the number of additions and subtractions.)
Solution:
The productof thetwo complex numbers a+bi and c+di can be computed as follows:
(a + bi)(c + di)
= +( ..)i.
where = ac, =(a + b)(c + d)and = bd which require only 3 numerical multiplications.
2. (5 Points) Give an example of a graph for which Approx-Vertex-Cover always yields a suboptimal solution.
Solution:
An example of a graph for whichApprox-Vertex-Cover always yields a suboptimalsolution is as follows.
Otherpossible solutions:
3. (10 Points) What are the operations in the disjoint set UNION-FIND data structure? How are they implemented? (Describe the basic implementation. There is no need mention path compression.) What is the time complexity of each operation?
Solution:
The UNION-FIND data structure supports the following3 operations. [3points]
( 1 point for each operation)
(1)
Create-Set(x): Create a set containing a single item x.
(2)
Find-Set(x): Find the set that contains x, and
(3)
Union(x,y): Merge the set containing x, and another set containing y to a single set.
Each of these operations are implemented as follows. [4points]
( 1 point for Create-Set(x), 1 point for Find-Set(x) and 2 points for Union(x,y))
(1) Create-Set(x):
Create-Set(x){
x->parent = x;
}
(2) Find-Set(x): We simply trace the parent pointer until we reach the root, then return the root element.
Find-Set(x){
while(x! = x->parent)
x = x->parent;
return x;
}
(3) Union(x,y): We always make the root of taller tree the parent of shorter tree. The root of every tree alsokeeps track of the height of the tree. In case two trees has the same height,wechoose the root of the .rst tree to point to the root of second. And the tree height is increased by 1.
Union(x,y){
a = Find-Set(x);
b = Find-Set(y);
if(a.height <= b.height){
if(a.height == height)
b.height++;
a->parent = b;
}
else
b->parent = a;
}
[3 poin