=========================preview======================
(COMP271)[2009](s)final~cs_lcmaj^_10194.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms
Spring 2009 Final Exam
1. Quick-Answer Questions (34 =12pts)
Foreach questionbelow,writedowntheasymptotic(using ) result. Youdonotneed to justify your answers.
1.1 What is the solution of the recurrence T(n)= T(n/2) + 1,T(1) =1?Youcan assume that n is a power of 2.
1.2 .cWhat is the solution of the recurrence T(n)=2T(n/4) +1,T(1)=1?Youcan assume that n is a power of 4.
1.3 InRandomizedQuicksort, we select apivot randomly every time. Supposethat one day you got a small magic device that will tell you in O(1)time the perfect pivot (i.e., the median)every time,then whatisthe running time ofQuicksortifyou use thisdeviceinstead of choosing thepivots randomly?Notethat nowthe algorithmis deterministic.
1.4 Suppose we have an alphabet of n characters A = {a1 ,...,an}. We are given a text in which the frequencies of these characters are 20 ,21 ,22 ,..., 2n.1 , respectively. In the Hu.man code of A on this text, what is the length (in terms of bits) of the codewords for a1 , an/2 , and an, respectively?
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. You do not need to justify your answers.
1.1 P .NP.
1.2 NPC P = ..
1.3 If SAT can be solved in O(n9 )time, then all NP-complete problems can be solved in polynomial time.
1.4 UNSAT NP. (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. (20pts)Supposeyouhavek sorted arrays, each with n numbers, andyou want to combine theminto asingle sorted array of kn numbers. We aregoing to usethe Merge procedure in mergesort for this task. Recall that given two sorted arrays of sizes x and y, Merge combines them into one sorted array in O(x + y) time. (You dont need to describe the Merge procedure.)
(a)(10pts)Onestrategy isto .rst Merge the .rst two arrays, then merge in the third, then mergeinthefourth, and so on. Whatisthe running time of this algorithm(in terms of k and n)?
(b)(10pts)Give a more e.cient solutiontothisproblem, and analyzeits running time. For full credits your algorithm should run in time O(nk logk).
1
4. (15pts)Supposethatthe stairway fromthe studenthallstothe academicbuilding(LG7 to LG5) has n stairs. Being tired of climbing the stairs one by one, you decide to adopt a di.erent pattern every day to class, supposing that you can cover 1, 2, or 3 stairs with each step. For example,ifn =5, then(1,2,2),(2,1,2),(1,3,1),(3,2),... are all considered di.erent patterns. Design and analyze an algorithm that computes the total number of di.erent patterns for a given n. For full credits, your algorithm should run in O(n)time. For this problem, assume that addition, substraction, multiplication, or division between any twointegerstakes constan