CSC 505 Design and Analysis of Algorithms CSC 505 651 Summer Midterm

CSC 505 651 Summer 2022 Midterm Instructions: You have 90 minutes to complete this exam. An extension will not be granted. Please work carefully and print answers neatly. Write your answers in the allotted spaces or pr ...

CSC 505 651 Summer 2022 Midterm Instructions: You have 90 minutes to complete this exam. An extension will not be granted. Please work carefully and print answers neatly. Write your answers in the allotted spaces or provide a reference to the place where your answer continues. Since the exams will be scanned, please do not use the backs of your pages. Good luck! Honor Pledge: I pledge that I have neither given nor received any aid while taking this exam. I will not discuss the content or difficulty of this exam with anyone before June 27, three days after the exam window closes. I also understand that except for writing utensils and a calculator (not programmable) no further tools – including cell phones – are allowed during the exam. Signature _________________________________________________________________________________ Problem Score 1 15 points 2 12 points 3 14 points 4 14 points 5 20 points Σ 75 pointsName: Problem 1. (15 points) Prove rigorously (ie give values for c and n0 that will make your argument work, and justify the values) each of the following statements using the formal definitions of O, , and Θ. The function lg(n) indicates the binary logarithm of n. Warning: testing individual values for n is NOT a proof. A) (4 points, new) n3/2 - n2.5  (n3). Determine pos. constants c1, c2 and n0 such that c1 n3 <= n3/2 - n2.5 <= c2 n3 for all n >=n0. For n>=1, dividing by n3 yields c1 <= ½-1/sqrt(n) <= c2 (*). Choosing any c2>=1/2 makes the right-hand side true. For n>=8 the left-hand side holds for any c1<=1/4. Thus, by choosing c1=1/4, c2=1/2, and n0=8 we see that n3/2 - n2.5  (n3). Other choices will work as well. B) (4 points, new) n + sqrt(n)  ω(sqrt(n )). The statement is true. We have to show that for all c>0 there is a n0(c)>0 such that f>cg for all n>n0. Assume 01sqrt(n)<=csqrt(n) for n>0, the inequality is true for n0(c)>0. Now assume c>1. Choose n0(c)=ceiling(sqrt(c)). For n>n0(c) we have n + sqrt(n) = sqrt(n)*sqrt(n) + sqrt(n)>=c*sqrt(n)+sqrt(n)>csqrt(n). This shows that with n0(c)=ceiling(sqrt(c)) the inequality is also true for c>1. This proves n + sqrt(n)  ω(sqrt(n )). C) (7 points, new) Rank the following functions by order of asymptotic growth; that is, find an arrangement g1, g2, … with gi(gi+1), gi+1( gi+2). This arrangement is not unique. Please mark the functions in the table that can be exchanged (i.e. gi (gi+1)) by ‘*’. No justification is required. Here, lg indicates the binary logarithm