[Solved] CSE 310 Data Structures & Algorithms Midterm Exam 1- Part II

1. [30 Pts] Using master theorem, give the asymptotic bounds for T(n) defined by the following recurrences. Then use the recursion tree to show that the answer you have obtained using the master theorem is correct. Need to show your work clearly indicating required constants, recursion tree expansion and derivation of the running time:

1. T (n) = 3 T (n/3) + n

1. T (n) = 27T (n/3) + n

2. T(n) = 2.T(n/2) + n^2

2. [20 Pts] Given an array of numbers A={7, 2, 3, 5, 1, 6, 12, 18, 4}. Answer the following questions using algorithms given below:

(a) Build the array into a max-heap, following the build-max-heap algorithm. Show each intermediate step and the binary tree representation of your final result.

MAX-HEAPIFY (A, i)l = LEFT(i)r = RIGHT(i)if l < A.heap-size and A[l] > A[i]largest = l else largest = iif r < A.heap-size and A[r] > A[largest]largest = rif largest i exchange A[i] and A[largest] MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A)A.heap-size = A.length for i = A.length/2 down to 1 doMAX-HEAPIFY(A, i)

1. b) Suppose you need to develop MIN-HEAP where parent(i) is less than or equal to its children. How do you change the above MAX-HEAPIFY (A, i) and BUILD-MAX-HEAP(A) procedures to build the min heap? Write the modified pseudo-code here.

3. [20 Points] Suppose you are given set A of n points in the Cartesian coordinate system as follows.

A = {p₁, p₂, p₃, .p_n}

Each point in p A has x a coordinate and a y coordinate. However, the y coordinate of all the points in set

A is the same. For example,

p₁ (x1, y) p₂ (x2, y) , p₃ (x3, y) etc

Now, you need to design an algorithm to determine the two closest points. The running time of your algorithm should be O(nlogn).

1. Briefly explain your strategy in solving this problem in O(nlogn) running time. You can draw a diagram if needed.
2. Then, develop your algorithm and write it in the pseudocode format (similar to the algorithms discussed in the class).
3. Clearly Show that the upper bound of your algorithm is O(nlogn)