CSE 551:Quiz and Solutions

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) 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. . O(nlogn) . O(n) . O(logn) . O(n2) 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 whenever 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. Determine 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. .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. 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