Question

In: Computer Science

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n]...

Divide and conquer problem.

Suppose we are given two sorted arrays A[1 . . . n] and B[1 . . . n] and an integer k. Describe an algorithm to find the kth smallest element in the union of A and B in O(log n) time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B; if k = n, your algorithm should return the median of A ∪ B.)
You can assume that the arrays contain no duplicate elements using divide and conquer.
(b) Now suppose we are given three sorted arrays A[1 . . . n], B[1 . . . n], and C[1 . . . n], and an integer k. Describe an algorithm to find the kth smallest element in A ∪ B ∪ C in O(log n) time using divide and conquer (not heap)

Solutions

Expert Solution

Solution:

  • Using the divide and conquer approach, below solution time complexity is: O(log n)
  • Check whether kth element lies in first half of either of the 2 arrays.
  • If yes, only seek kth element in first half only, else seek only in second half.
  • This recursively, reduce the original problem into a subproblem with smaller search space.
  • Check comments in the code section for a better understanding

Code: O(log n) solution

#include <bits/stdc++.h>   
using namespace std;

int kSmallest(int A[], int B[], int *endA, int *endB, int k)
{ 
    // if array A is empty, then return kth value in B 
    if(A==endA)
        return B[k];
    
    // if array B is empty, then return kth value in A
    if(B==endB)
        return A[k];
        
    // Find mid index of array A and B
    int midA = (endA - A)/2;
    int midB = (endB - B)/2;

    // If condition checks whether k lies in second half of either of the arrays 
    if(midA + midB < k){
        // when array A has more elements than B, ignore first half of B
        if(A[midA] > B[midB])
            return kSmallest(A, (B+midB+1), endA, endB, (k-midB-1));
        // otherwise first half of A
        else
            return kSmallest((A+midA+1), B, endA, endB, (k-midA-1));
    }
    // Else k lies in first half of either array A or B
    else{
        if(A[midA] > B[midB])
            return kSmallest(A, B, A+midA, endB, k);
        else
            return kSmallest(A, B, endA, B+midB, k);
    }
    
    return -1;
} 
  
// Driver code 
int main() 
{ 
    int A[6] = {1, 2, 5, 6, 7, 9}; 
    int B[4] = {0, 3, 8, 10}; 
  
    int k = 4;
    
    cout<<"Kth smallest number in union of A and B : "<< kSmallest(A, B, A+6, B+4, k-1); 
    return 0; 
} 

Input: (hardcoded)

int A[6] = {1, 2, 5, 6, 7, 9}; 
int B[4] = {0, 3, 8, 10}; 
int k = 4;
    

Output:

Kth smallest number in union of A and B : 3

Attached screenshot of code:

For question 2, extend same idea for 3 arrays, try do it on your own. Ask if you face any issue in implementation.

PS: Let me know if you have any doubt.


Related Solutions

3. Suppose that a divide and conquer algorithm for multiplication of n x n matrices is...
3. Suppose that a divide and conquer algorithm for multiplication of n x n matrices is found such that it requires 6 multiplications and 31 additions of n/2 x n/2 submatrices. Write the recurrence for the running time T(n) of this algorithm and find the order of T(n).
A: Write a divide-and-conquer program to solve the following problem:
in Java A: Write a divide-and-conquer program to solve the following problem:     1. Let A[1..n] and B[1..n] be two arrays of distinct integers, each sorted in an increasing order.      2. Find the nth smallest of the 2n combined elements. Your program must run in O(log n) time. For example: n = 4If A[1..n] = {2, 5, 8, 9} and B[1..n] = {1, 4, 6, 7}The nth (i.e. 4th) smallest integer is 5.If A[1..n] = {2, 5, 8, 13}...
1. If we view the selection sort as an application of "divide and conquer" strategy, what...
1. If we view the selection sort as an application of "divide and conquer" strategy, what is the two-part partitioning of the index range [0, n)? Is it a balanced partition? 2. For the "divide and conquer" strategy for developing algorithm, do we pursue balanced partitioning or unbalanced partitioning? Why? 3. For the quicksort, the selection of pivot determines the quality of partitioning. Do we have any easy or cheap way for selecting a good pivot that always leads to...
Polynomial Multiplication by Divide-&-Conquer A degree n-1 polynomial ? (?) =Σ(n-1)(i=0) ???i = ?0 + ?1?...
Polynomial Multiplication by Divide-&-Conquer A degree n-1 polynomial ? (?) =Σ(n-1)(i=0) ???i = ?0 + ?1? + ?2?2 ... + ??−1?n-1 can be represented by an array ?[0. . ? − 1] of its n coefficients. Suppose P(x) and Q(x) are two polynomials of degree n-1, each given by its coefficient array representation. Their product P(x)Q(x) is a polynomial of degree 2(n-1), and hence can be represented by its coefficient array of length 2n-1. The polynomial multiplication problem is to...
Write the algorithm, following the ideas given in class, for merging two sorted arrays into one...
Write the algorithm, following the ideas given in class, for merging two sorted arrays into one sorted array. Note the algorithm is not the one for merge sort. 2) What is the best asymptotic upper bound for the algorithm? List reasoning steps.
Let A be an integer array of length n. Design a divide and conquer algorithm (description...
Let A be an integer array of length n. Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array. If there are several such elements, your algorithm must return the index of the rightmost element. For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.
You are given 2 sorted sequences of log(n) and n-1 keys. We would like to merge...
You are given 2 sorted sequences of log(n) and n-1 keys. We would like to merge those 2 sorted sequences by performing o(n) comparisons.[Note that we are interested in the comparisons and not the running time.] Show how this can be done or argue how this cannot be done. In class we show that ordinary merging would require no more than lg(n)+n-1+1 = n+lg(n) comparisons.
Design and analyze a divide-and-conquer algorithm for finding the maximum element in a list: L[0: n – 1].
The following submission rules apply:·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.o Solutions must be provided in plain text so that formatting is not lost.·    All answers must be provided in this document.·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.Design and analyze a divide-and-conquer algorithm for finding the maximum...
Step (D) of the divide-and-conquer strategy (i.e. combine the solutions to smaller instances of the problem...
Step (D) of the divide-and-conquer strategy (i.e. combine the solutions to smaller instances of the problem to obtain the solution of the original instance) is not a necessary step for this design strategy. Mergesort is an example of such cases. Select one: True False
Given an array of n numbers, not necessarily in sorted order, we wish to find: (i)...
Given an array of n numbers, not necessarily in sorted order, we wish to find: (i) the range (max - min) and (ii) the interquartile range (IQR) of the numbers. IQR is defined as the difference between the number at the 25% percentile and the number at the 75% percentile. What is the exact number of comparisons needed for computing the range and why? Using any algorithm from the chapters of the textbook covered so far as a subroutine, give...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT