Computer Science > Questions and Answers > 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 modied version of Merge-Sort that at eac ... h 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 benet will be gained. .False: The number of comparisons made between points within of L would necessarily be the same as without the modication. . 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 [Show More]
Category:
Questions and Answers
Course:
Computer Science
Last updated at :
1 year ago