1,851 views

Let $S$ be a set of numbers. For $x \in S$, the rank of $x$ is the number of elements in $S$ that are less than or equal to $x$. The procedure $\textsf{Select}(S, r)$ takes a set $S$ of numbers and a rank $r\left(1 \leq r \leq |S|\right)$ and returns the element in $S$ of rank $r$. The procedure $\textsf{MultiSelect}(S,R)$ takes a set of numbers $S$ and a list of ranks $R=\left\{r_{1} < r_{2} < \ldots <r_{k}\right\}$, and returns the list $\left\{x_{1} < x_{2} < ...<x_{k}\right\}$ of elements of $S$, such that the rank of $x_{i}$ is $r_{i}$. Suppose there is an implementation for $\textsf{Select}(S, r)$ that uses at most  $($ constant ·$|S|)$ binary comparisons between elements of $S$. The minimum number of comparisons needed to implement $\textsf{MultiSelect}(S,R)$ is

1. constant · $|S| \log |S|$
2. constant · $|S|$
3. constant · $|S||R|$
4. constant · $|R| \log |S|$
5. constant · $|S|(1 + \log |R|)$

1 comment

Plz explain question as well as solutions???

Think about partition method in quick sort. it places pivot to correct location and return the index of pivot element. Now suppose partition returns k then can you tell me what is kth smallest element ?

Yes that’s right – Pivot element is kth smallest element. (Think about it).

Select also does same thing. 𝖲𝖾𝗅𝖾𝖼𝗍(S,r) will not only return rth smallest element but it also places rth smallest to its correct position just like pivot. (if their implementation of 𝖲𝖾𝗅𝖾𝖼𝗍(S,r) is not doing so then I will find rth smallest and i will rearrange my array manually but lets not worry about it).

Now comes main part. How to implement 𝖬𝗎𝗅𝗍𝗂𝖲𝖾𝗅𝖾𝖼𝗍() efficiently ?

I am taking an example to explain idea. Suppose R = {2,4,6,8,10,12}. which means you want 2nd smallest, 4th smallest, 6th smallest and so on.

I will pick middle element of R which is 8 and i will search for 8th smallest first. We can do it in O(S).

Here is an crucial observation-

Once we get 8th smallest then how our array looks like ? – 8th smallest is at its correct position.              if 8th smallest is at its correct position then where is 4th smallest ? – left side of array of 8th smallest.   where is 12th smallest? –  right side of array of 8th smallest.

Now I will search for 4th smallest. Now do i need to search 4th smallest in entire array ? – No, I can just search in left side of 8th smallest. Suppose there are K elements on left side and |S|-K elements on right side.

I will find 4th smallest in left side and 10th smallest in right side. but total only |S| comparisions (K for 4th smallest and |S|-K for 10th smallest). This says that we can find 2 elements in |S| comparisons.

After this my array is having 4th smallest, 8th smallest and 10th smallest at its correct position. basically i can divide my array in 4 parts now.

1st part  – left side of 4th smallest

2nd part – between 4th smallest and 8th smallest

3rd part – between 8th smallest and 10th smallest

4th part- after 10th smallest.

How many element i can find in just |S| comparisons now ? – yes 4 elements. Anything having rank smaller than 4 i will search in first part only and so on.

Whats the pattern ?

Initially We took |S| comparisions for 1 element (8th smallest)

then we took |S| comparisions for 2 elements (4th and 10th  smallest)

then we take |S| comparisions for 4 elements.

Just draw a tree. Start with array, then divide it into 2 parts and then 4 parts and so on.

Since there are total |R| elements so tree height will be log|R| and at each level we are spending |S| comparisions.

total |S|log|R| comparisons. If you do it carefully then there will be log|R|+1 levels. giving you E as answer.

1) Find rank of elements of S is Constant*|S|

2) Check for each member, take it's rank of element  and search in input list of required ranks; if found print it !

we have an entry in list of Ranks R, As R is given as sorted we perform binary search over it .

So Comparison : Constant * |S| * Log |R|

Total Comparison :  Constant * |S| + Constant * |S| * Log |R| = Constant  * |S| ( 1 + log |R| ) Ans (E)

Note :- assuming those are positive integers.

by

yes, thanks.

@Shaik Masthan

Can u tell me what is difference between Select(S,r) and MultiSelect(S,R)?

I am not getting it.

@Shaik Masthan

Suppose, list is like this

S=

 2 2 2 3 3 1 4 4 4 4 5 5

Now, rank(S)=

 4 4 4 6 6 1 10 10 10 10 12 12

but is it returning sorted list??

and what rank it actually doing??

this solution seems a little complex, can't this be done like this -> suppose R = [1,2,3,...n] (R is a sorted list as given in the question) and take any set S such that size(S) > size(R). The Algorithm does the following steps. It's a divide and conquer strategy. There is no base conditions and some other things in the below solution it's just an idea, it's not complete. All this can be avoided if we don't have to use select then we can just sort S and do it.

Multiselect(S, R)

1. Find the element with rank n/2 using select(S, n/2) (this is according to the assumed R don't get confused) let this be X.

2. Partition S using X.

3. Let List1 =  Multiselect(S[0.....n/2-1], R[0...n/2-1]) and List2 = Multiselect(S[n/2+1.....m], R[n/2+1....n])

4. return List1 + [X] + List2

Time Complexity:

step 1 - constant.|S| (given in the question)

step 2 - constant.|S|

step 4 - constant.|R|

so step 1,2 and 4 take time C.|S|. Assuming size(S) > size(R), every recursion step halfs the list R, so number of steps = log(R), and every step takes time C.|S|. So time complexity = C.|S|.log(R). Not an exact solution but i think if we implement this bottom up it might give the solution.

Reason: Sort the set. Initialize a counter to 1. Keep a parallel pointer to the sorted list of needed ranks. Keep incrementing the counter as you traverse the sorted set. As soon as counter matches the first needed rank, add this to the required output. Increment the parallel pointer.
by

If I am not wrong this is TC and not the number of comparisons.
I think C should be the answer. Using randomized partition algo of quick sort, we can find out kth smallest element in S + S/2 + S/4 + S/8 + ...... = constant.|S| number of comparisions. For proof see Randomized quick sort algo works in nlogn time in worst case also.

So for R (equal to S in worst case) number of comparisions equals to constant.|S|.|R|. Correct me if i am wrong.
by