1.In all of the following sub-questions, give an algorithm in recursive form and

Question

1.In all of the following sub-questions, give an algorithm in recursive form and show its running time using the Master Theorem or just by solving the recurrence in the simpler cases.

F) Describe an (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose difference is exactly x.

G) Describe an (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose difference is smaller or equal to x.

Explanation / Answer

F)

We first sort the elements in the array using a sorting algorit hm such as merge-sort which runs in time T(nlog n). Then, we can find if two elements exist in A whose sum is x as follows. For each element A [i] in A , set y = A [i] - x . Using binary search, find if the element y exists in A . If so, return A [i] and y . If we can’t find y for any A [ i ], then return that no such pair of elements exists.

Each binary search takes time T(log n ), and there are n of them. So, the total time for this procedure is T ( n ) = T( n log n )+T( n log n ) where the first term comes from sorting and the second term comes from performing binar y search for each of the n elements. Therefore, the total running time is T ( n ) = T(n log n )

public static boolean Sum(int [] arr, int x)
   {
        mergeSort(arr, 0, arr.length-1);
        return SumHelper(arr, x, 0);
   }
  
    public static boolean SumHelper(int [] a, int x, int i)
    {
        if(i >= a.length)
            return false;
        int n = a[i];
        int m = x-a[i];
        if(binarySearch(a, m, i+1, a.length-1) != -1)
            return true;
        return SumHelper(a, x, i+1);
    }

G)

Generally The sub-array will consist of elements of A[1 ... n] in sorted order and each of those elements will be smaller than (or equal) to those in the sub-array A[i ... n]. And, again, note that these elements are simply permuted from the original.The swap of inversions happens in the while loop although it skips the step of inserting the smaller value--the key in this case--back into the array until all swaps are completed. Thus, the more inversions are in the array, the more the second while loop will need to iterate which increases the running time.

    for j <- 2 to length[A]
        do key <- A[j]
             Insert A[j] into the sorted sequence A[1 ... j - 1].
            i <- j - 1
            while i > 0 and A[i] > key
                do A[i + 1] <- A[i]
                    i <- i - 1
            A[i + 1] <- key

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.