Question

Q1. In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. Do not write a program. Write pseudo codes or explain in words.

(A) Find an efficient data structure supporting the following operations. Insert(S, x), Delete−Max(S), and Delete−100'th(S) which deletes from H the 100 largest element in the structure. Assume that the number of elements is more than 100. Also assume that the numbers are pairwise distinct and so the 100”th largest element is well defined.

(B): Recall the problem in which you have k sorted array each of size n, which need to make one single sorted array. Find another fast way to unite the arrays that does not use Priority Queue.

Answer 1

(A) Find an efficient data structure supporting the following operations. Insert(S, x), Delete−Max(S), and Delete−100'th(S) which deletes from H the 100 largest element in the structure. Assume that the number of elements is more than 100. Also assume that the numbers are pairwise distinct and so the 100”th largest element is well defined.

Ans:

You can use max Heap data Structure to store the value. Max heap always keep the largest elements at the top. Priority Queue is one of the applications of Heap where you can store the data pairwise and get the largest element at the top.

In C++ it is really easy to implement using the STL library. In other languages, you can find the alternative as well.

Just insert all the elements in max heap pop top 100 elements and here you go, your work is done.

(B): Recall the problem in which you have k sorted array each of size n, which need to make one single sorted array. Find another fast way to unite the arrays that does not use Priority Queue.

Ans:

Given, k sorted arrays each of size n.

Creating a single sorted array by combining all the arrays makes an array of size (n * k).

To sort this in an efficient way i.e. with less time complexity and less space complexity, we can use the merge sort algorithm.

The array is first divided into 2 arrays with size k/2. Later the array is further divided into k/4 on both the arrays. This recursive process is done until the size of array becomes 1. Finally, it follows a bottom up process by combining the elements to give a sorted array.

The algorithm is explained below.

ALGORITHM

1. Create a recursive function which takes k arrays and returns the output array
2. In the function, if the value of k is 1, return the input array else, merge the two arrays in linear time and then return it.
3. If the value of k is greater is than 2, split the array into two equal parts and then apply the function recursively until k size is either 1 or 2.
4. Output the sorted array.

Hope I answered the question.

If you have any doubts, or queries, feel free to ask

I'll respond to you as soon as I can.

Have a nice day