Question

problem 2

can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1, n). You also need to provide the worst case time complexity analysis of your algorithm. 2. (20 points) Given a set of n distinct numbers, we wish to find the k largest in sorted order using a comparison-based algorithm. Give an algorithm that implements each of the following methods, and analyze the running times of the algorithms in terms of n and k - you should provide an upper bound for the worst-case time complexity if your algorithm is determinstic, and expected running time if your algorithm is randorized. You should make your algorithm as fast asymptotic) as possible and your bound tight. Slower algorithms analysis receive fewer point. (What we describe below are not full algorithms. You need to give pseudo-code to implement each idea as an algorithm, and output the k largest numbers in sorted order. In your pseudo-code, you can use any algorithm we described in class as subroutine: such as MergeSort(), Heap Extract Max(), etc.) 2.a Sort the numbers, and then list the k largest. 2.b Build a max-priority queue from the numbers, and then extract the largest k elements. 2.c Use a selection algorithm to find the k-th largest number, and the retrieve the largest k numbers. 3. / 5 points) Draw the binary tree produced by inserting the following elements in a max-heap in the given order:

Answer 1

Algorithm:

1. Build the min heap for first k element [0,k-1] of array. it will take O(k) time to build it.
2. Traverse the array from kth index to n-1 th index and check-
   1. if element is greater then root element of min heap then make it root and heapify it.
   2. else ignore it.

Step 1 will take O(k) time to build the min heap of k size.

Step 2 will take O(n-k log k), n-k for traversing remaining elements and log k for heapify.

So the total time will be O(k+ (n-k)log k). But it will generate unsorted greatest element. If you want that the sequence of greatest elements must be sorted then time complexity will be : O(k + (n-k)Logk + kLogk)

Function:

void KLargestelements(int A[],int n,int k){

    // Build the min heap for first k element [0,k-1] of array.

    MinHeap* m = new MinHeap(k, arr);

  

    // Traverse the array from kth index to n-1 th index and check-

    for (int i = k; i < n; i++) {

  

        // if current element is smaller

        // than minimum element, do nothing

        // and continue to next element

        if (A0] > A[i])

            continue;

  

        // if element is greater then root element of min heap then make it root and heapify it. restore the heap property

        else {

A[0] = A[i];

//Heapify is the method for heapify operation.  

m->heapify(0);

        }

    }