CSE 551 -Unit 4 Quiz solution

1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T(n) = 2T(n 2 ) + log(n) for n > 1; 0 otherwise  T(n) = O(n)  T(n) = O(nlogn)  T(n) = O(n2)  T(n) = ...

1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T(n) = 2T(n 2 ) + log(n) for n > 1; 0 otherwise  T(n) = O(n)  T(n) = O(nlogn)  T(n) = O(n2)  T(n) = O(logn) 2 Problem 2 Suppose we have a modied version of Merge-Sort that at each recursive level splits the array into two parts each of size 1 4 and 3 4 respectively. Also, assume the size of any given input array is a power of four. Give the asymptotic time complexity of this Merge-Sort variant. 1  O(nlogn)  O(n)  O(logn)  O(n2) 3 Problem 3 Suppose we modify the combine step of the closest pair of points algorithm such that distance  from dividing line L is updated immediately to 0 when- ever the distance between two points on either side of L is discovered to be less than . In this sense, we allow the two-dimensional range about L wherein we compare points to assume multiple areas (getting smaller as  becomes updated) during the same combine step for each recursive call. De- termine whether the following statement is true or false and explain your reasoning: The time complexity of the closest pair of points algorithm is guaranteed to be improved by a constant factor.  False: If  is reduced only after the last pair of points sorted by y-coordinate within  of L is compared, then no additional benet will be gained. 2  False: The number of comparisons made between points within  of L would necessarily be the same as without the modication.  True: If  is reduced every time a new closest pair of points is found during the combine step, then it will always be the case that a fewer number of future comparisons will be necessary after  is adjusted to0.  True: If  is reduced every time a new closest pair of points is found during the combine step, then it will sometimes be the case that a fewer number of future comparisons will be necessary after  is adjusted to 0. 4 Problem 4 Suppose there is a set of n points each with the same x-coordinate. Obvi- ously, this will cause the closest pair of points algorithm to fail. Since this is the case, what must be the smallest possible asymptotic time complexity required to nd the closest pair of points in this instance?  O(nlogn)  O(nlog2n)  O(n2)  O(n) 5 Problem 5 Given a two-dimensional plane with points (0,1),(1.5,2),(1,4),(4.8,2),(5,3), (7,3.5),(8,8),(7.5,9.5), give the numerical value of  before the combine step on the highest level of the recursive stack.  1.58  1.80  1.02  2.06 6 Problem 6 Given a two-dimensional plane with points (1.5,1), (2,3.8), (2.75,1), (5,3.3), (6,3.5), (7.5,2), (8.5,1.2), (8,5), give the numerical value of  after the com- bine step on the highest level of the recursive stack.  1.02  0.89  1.28  1.25 4 7 Problem 7 Identify which of the following statements are true regarding the Karatsuba multiplication algorithm. i.) The Karatsuba algorithm is asymptotically less complex than merge- sort with respect to the number of operations it requires to terminate. ii.) Each call to this algorithm produces three additional recursive calls on roughly half the number of bits as the previous call.  ii. only  i. only  i. and ii.  Neither of these are true 8 Problem 8 Suppose Anatolii Karatsuba had somehow discovered a way to produce the product of integers x and y with only two real multiplications and an asymp- totically linear number of adding, subtracting and shifting operations per recursive call to his algorithm. What would have been the asymptotic time complexity of his algorithm if x and y are each represented by n bits? (Hint: Read pages 215 to 218 in the Kleinberg and Tardos textbook carefully before answering.)  O(nlogn)  O(n1:585)  O(n)  O(n2) 9 Problem 9 Identify which of the following statements are true regarding Strassens fast matrix multiplication algorithm as applied to matrices of size n by n. i.) Strassens algorithm is the fastest known algorithm for matrix multi- plication. ii.) If n is not a power of 2, adding rows and columns of zero-entries until n is a power of 2 will allow the algorithm to run normally and produce the correct result.  ii. only  i. only