CSE 551: Foundations of Algorithms - Arizona State University. CSE 551 Practice Quiz 4 Solutions (2021 Fall)

CSE 551 Practice Quiz 4 Solutions Jamison Weber June 1, 2021 Question 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T (n) = 2T (n2 ) + 1 for n > 1; 1 otherwise. 1. T (n) = O(n) 2. T (n) = O(n log n) 3. T (n) = O(n2) 4. T (n) = O(log n) Question 2 Determine whether the following statement is true or false and explain your reasoning: The divide-and-conquer approach can be applied to any problem that can be expressed as a linear recurrence relation. 1. False: If the recurrence relation produces subproblems that need to be recalculated over and over, the divide-and-conquer approach will fail. 1 2. False: Since there does not exist a closed form solution for every linear recurrence relation, the divide-and-conquer approach is not guaranteed to always work. 3. True: Since linear recurrence relations always break problems down into smaller subproblems, the divide-and-conquer approach is guaranteed to work. 4. True: Since there exists a closed form solution for every linear recurrence relation, the divide-and-conquer approach is guaranteed to always work. Question 3 Identify the reason why the combine step of the closest pair of points algorithm can be solved in linear time. 1. The number of comparisons made between points within distance δ of dividing line L can be shown to be a constant. 2. Keeping vectors of points presorted by x and y-coordinate allows for a linear time combine step because there is no need to re-sort for each recursive call. 3. Comparing every two points within distance δ of dividing line L will always require at most linear time. 4. We cannot necessarily guarantee linear time complexity for the combine step, but the time complexity of the full algorithm is still guaranteed to be O(nlogn) despite this fact. Question 4 Suppose we introduce a modified version of the closest pair of points algorithm that maintains a single presorted vector of only y-coordinates. What will be the guaranteed asymptotic time complexity of this variant? 1. O(n log2 n) 2. O(n log n) 3. O(n2 log n) 4. T(n) = O(n log n2) Show Less