=========================preview======================
(COMP271)[2009](f)final~tm_clh^_10190.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms (Fake) Fall 2009 Final Exam
1. Quick-Answer Questions (34 =12pts)
Foreach questionbelow,writedowntheasymptotic(using ) result. Youdonotneed to justify your answers.
1.3 In a divide-and-conquer algorithm, we .rst divide the problem in O(n) time into 3 subproblems, each of size n/3, recursively solve each of them, and then combine the results together in O(n) time. What is the total running time of this algorithm on an input size of n?
2. Multiple Choice (24 =8pts)
For each of the following statements, indicate whether it is (a) true, (b) false, or (c) unknown based on our current scienti.c knowledge. For any statements that you mark false, please give a brief explanation why it is wrong. Youdo not needtojustify the true and unknown answers.
1.4 Because if we can solve UNSAT in polynomial time, we can also solve SAT in poly-
nomial time, so UNSAT is also an NP-complete problem.
(UNSAT is the following problem: Given a Boolean formula, if for all assignments
to the variables, is always false, then return yes; if there is one assignment that
makes true, then return no.)

3. (20 pts) There have been a few objects-dropped-from-height incidents in Hong Kong. For investigation, the police need to determine the height at which a certain type of glass bottles will break when dropped, and you have been asked to help. More precisely, in a tall building with n .oors, this type of bottles will break when dropped at or above the k-th .oor, and will not break when dropped below the k-th .oor, for some 1 k n. Yourjobistodeterminethe value of k.
(a)
(10pts)Supposeyouhave an unlimitednumber of suchbottles. Design an algorithm to determine k with at most O(logn)trials.

(b)
(10 pts) Of course a bottle cannot be used after it breaks. Thus, if you only have one such bottle, the only thing you can do is to try dropping the bottle from .oor 1,2,..., until it breaks. This requires O(n) trials in the worst case. Suppose now



you have 2 bottles, can you determine k with O( n)trials?
4. (15 pts) You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 <a2 < ...<an, where ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choosewhich ofthehotelsyoustop at. Youmuststop atthe .nalhotel(atdistance an) which is your destination. You would ideally like to travel 200 miles a day: if you travel morethanthisyou willhavetodrivefastorforlong hours;ifyoutravellessthanthisyou will be behind schedule and possibly get bored at the hotel. However, traveling exactly 200 miles aday may notbepossible,depending onthehotellocations. So on any dayyou are allowed to travel x miles for any x> 0, but the penalty for that day will be de.ned to be(x .200)2 . You want to plan your trip so as to minimize the total penalty, that is,the sum of thedailypen