Question

3. (20 pts.) You are given two sorted lists of numbers with size m and n. Give an O(logn+ logm) time algorithm for computing the k-th smallest element in the union of the two lists. 4. (20 pts.) Solve the following recurrence relations and give a bound for each of them. CMPSC 465, Fall 2019, HW 2 (a) T(n) = 117(n/5)+13n!.3 (b) T(n) = 2T (n/4)+nlogn (c) T(n) = 5T (n/3) +log-n (d) T(n) = T(n/2) +1.5" (e) T(n) = T(n) + (log logn) (f) T(n) = 6T (n/2)+n2.8 (g) T(n) = T (n/2+ n) +230 (h) T(n) =T(n-2)+logn (i) T(n) = T(3n/5)+T(2n/5) + (j) T(n) = n(n)+30n (n)

Answer 1

3.

This problem can be easily solved using Divide and Conquer approach.
We compare the median of arrays arr1 and arr2, let us call these indices mid1 and mid2 respectively.

Let us assume arr1[mid1] is more than k, this means that the elements after  mid2 cannot be the required element. We then set the last element of arr2 to be arr2[mid2].

In this way, we define a new subproblem with half the size of one of the arrays.

PSEUDOCODE

int kth(int arr1[], int arr2[], int m, int n, int k, int st1, int st2)

{

if (st1 == m)

{

return arr2[st2 + k - 1];

}

if (st2 == n)

{

return arr1[st1 + k - 1];

}

if (k == 0 || k > (m - st1) + (n - st2))

{

return -1;

}

if (k == 1)

{

return (arr1[st1] < arr2[st2]) ? arr1[st1] : arr2[st2];

}

int curr = k / 2;

if (curr - 1 >= m - st1)

{

if (arr1[m - 1] < arr2[st2 + curr - 1])

{

return arr2[st2 + (k - (m - st1) - 1)];

}

else

{

return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);

}

}

if (curr - 1 >= n - st2)

{

if (arr2[n - 1] < arr1[st1 + curr - 1])

{

return arr1[st1 + (k - (n - st2) - 1)];

}

else

{

return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);

}

}

else

if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])

{

return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);

}

else

{

return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);

}

}

NOTE: As per HOMEWORKLIB POLICY, I am allowed to answer specific number of questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.