CSE 551: Quiz 4 Solutions : week 3 ,unit 4.

New descriptionSolve 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

2 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.

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 when-
ever 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. De-
termine 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.

4 Problem 4
Suppose there is a set of n points each with the same x-coordinate. Obvi-
ously, this will cause the closest pair of points algorithm to fail. Since this
is the case, what must be the smallest possible asymptotic time complexity
required to nd the closest pair of points in this instance?

5 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.

6 Problem 6
Given a two-dimensional plane with points (1.5,1), (2,3.8), (2.75,1), (5,3.3),
(6,3.5), (7.5,2), (8.5,1.2), (8,5), give the numerical value of  after the com-
bine step on the highest level of the recursive stack.