=========================preview======================
(COMP271)2006Fall_Final_SOL.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.
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.
Solution:
Step 1: (2 points, can be done implicitly) Build the frequency table:
Step 2: (3 points)We will use Hu.man coding since we know that it can build pre.x-free code with minimum encoding length. So we will build the binary tree for the Hu.man coding:
Step 3: (2 points)Extract the code from the binary tree:
2. (15 Points)
(a)
Give the next function for the pattern P : 110011. There is no need to show how the function is obtained.
Solution:
(6 points)The table for the next function:
(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. Start by aligning P withbeginning 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.
q 1 P[q] 1 2 1 3 0 4 0 5 1 6 1
next[q] 0 1 0 0 1 2
The following table is included for your convenience.
Solution:
i 1 2 3 4 5 6 7 8 9 10
T 1 i = 1 to 4, q = 0 to 3 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 (1 point for matching 110, 1 point for unmatch 0) T[4] .= P[4], so q = next[3] = 0
i = 4 to 6, q = 0 to 2 1 1 0 0 1 1 (1 point for correct shift, 1 point for matching 11, 1 point for unmatch 0) T[6] .= P[3], so q = next[2] = 1
i = 6 to 10, q = 1 to 6 1 1 0 0 1 1 (1 point for correct shift, 2 points for no compari-son at the .rst 1, 1 point for matching 10011) Pat-tern occurs with shift = 10 -6 = 4
(Note: q is the number of matched characters so far. Bold and large without underline means a match (with comparison), Large and italic without underline means a match (no comparison), Bold and large with underline means a mismatch.)
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 pr