CSE 551: Foundations of Algorithms - Arizona State University. CSE 551 Design and Analysis of Algorithms Week 3 Unit 4 Quiz Solutions, April 6, 2020. Problem, Solutions and Rationale.

CSE 551: Foundations of Algorithms - Arizona State University. CSE 551 Design and Analysis of Algorithms Week 3 Unit 4 Quiz Solutions, April 6, 2020. Problem, Solutions and Rationale. CSE 551: Foundations of Algorithms - Arizona State University. CSE 551 Design and Analysis of Algorithms Quiz 4 Solutions, April 6, 2020. Problem, Solutions and Rationale. CSE 551: Quiz 4 Solutions J amison Weber April 6, 2020 1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T (n) = 2T (n2 ) + log(n) for n > 1; 0 otherwise • T (n) = O(n) • T (n) = O(nlogn) • T (n) = O(n2) • T (n) = O(logn) 1.1 Rationale This recurrence relation can be tricky to solve using iterative substitution or tree-based methods. It’s best to use the Master theorem here. Recall the form: T (n) = aT (n=b) + f(n) Since f(n) = log(n) = n where  < log2(2) = 1, the Master method gives: T (n) = O(nlog2(2)) = O(n) 2 Problem 2 Suppose we have a modified 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) 2.1 Rationale This gives the recurrence relation T(n) = T(3 4) + T(14) + cn. Using the Akra-Bazzi method: We must satisfy kXi =1 aibP i = 1 Where ai is the coefficent in front of recursive call i and bi is the divisor of n in recursive call i. Thus, we have: 1(3 4 ) + 1(1 4 )P = 1 ) P = 1 Now we use the Akra-Bazzi formula to find: T(n) 2 Θ(nP (1 + Z1n ugP(u+1 ) du)) = Θ(n(1 + Z1n cn n2 dn)) = Θ(n(1 + cZ1n n1 dn)) = Θ(n + ncln(n)) = Θ(nlog(n)) 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 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.