=========================preview======================
(COMP271)2006Fall_Final.pdf
Back to COMP271 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 271 Design and Analysis of Algorithms
Fall 2006
Final Examination
12:30-03:30 (pm), Saturday, 16 December 2006, LG4204

Name: Student No:
Department: Tutorial Section:
This is a closed-book and closed-notes exam. You should put everything o. your desk except for stationeries and your student ID.
There are 8 questions. You need to answer all questions in 180 minutes. 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.
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.

Question
Grade



1
2
3
4
5
6
7
8
Total


1.
(7 Points) Consider encoding bcbbbbbbaacaabbcade as a binary string. Give a pre.x-free code that minimizes the encoding length. Show the main steps that you take to reach the solution.

2.
(15 Points)

(a)
Give the next function for the pattern P : 110011. There is no need to show how the function is obtained.

(b)
Illustrate how the KMP algorithm uses the next function of the previous step to .nd all occur-rences of P in the text T :1101110011. Startby aligning P with beginning of T. Show how KMP shifts P to the right according to the next function and show the comparisons made by KMP at each shift.




The following table is included for your convenience.
3. (8 Points)
10)
Aliens from another world come to Earth and tell us that the 3-SAT problem is solvable in O(ntime. Which of the following statements follow as a consequence and which do not? Brie.y explain your answers.
10)
(a)
All NP-complete problems are solvable in O(ntime.

(b)
All problems in NP, even those that are not NP-complete, are solvable in polynomial time.


10)
(c) No NP-complete problem can be solved faster than in O(n time in the worst case.
(d) P =NP.
4. (10 Points) Consider the following algorithm for computing vertex cover:
Approx-VC2(G=(V, E))


C = emptyset; V = V;

while (V is not empty) do

pick vertex u from V and add it to C;

remove from V the vertex u and all its neighbors.
return C;

IsApprox-VC2a2-approximationalgorithmfortheoptimizationVCproblem? Ifyes,giveaproof. If no, explain with a counter example.
5. (15 Points) Consider a weighted directed graph G that does not contain any cycles of zero or negative weights. Suppose the vertices are labeled with integers 1,2,...,n. For any two vertices i and j and an integer k (k =1,2,...,n), de.ne
k =length of the shortestpathfor i and j with intermediate vertices from {k,k+1,...,n}.
ij
Derive a recursive equation that enables us to compute k (k<n)using one or more terms from the
ij

set {k+1 |i ,j =1,2,...,n}.
i j
6.
(10 Points)