Statistics > EXAM > CSE 5518-W3-Unit 4 Quiz solution. Arizona State University (All)

CSE 5518-W3-Unit 4 Quiz solution. Arizona State University

Document Content and Description Below

CSE 551: Quiz 4 Solutions Jamison 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( n 2 ) + log(n) for n > 1, 0 otherwise • T(n) = O(n) • T(n) = O(nlogn) • T(n) = O(n 2 ) • 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(n log2(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(n 2 ) 2.1 Rationale This gives the recurrence relation T(n) = T( 3 4 ) + T( 1 4 ) + cn. Using the Akra-Bazzi method: We must satisfy X k i=1 aib P 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) ∈ Θ(n P (1 + Z n 1 g(u) u P +1 du)) = Θ(n(1 + Z n 1 cn n2 dn)) = Θ(n(1 + c Z n 1 1 n 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. • False: If δ is reduced only after the last pair of points sorted by y-coordinate within δ of L is compared, then no additional benefit will be gained. 2 • False: The number of comparisons made between points within δ of L would necessarily be the same as without the modification. • 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 toδ 0 . • 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 .

[Show More]

Last updated: 3 years ago

Preview 1 out of 7 pages

Buy Now

Instant download