TIFR CSE 2013 | Part B | Question: 18

Question

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

• A. constant · $|S| \log |S|$
• B. constant · $|S|$
• C. constant · $|S||R|$
• D. constant · $|R| \log |S|$
• E. constant · $|S|(1 + \log |R|)$

Comments

Plz explain question as well as solutions???

Answer 1

Answer-E

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 2^nd smallest, 4^th smallest, 6^th smallest and so on. 

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

Here is an crucial observation-

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

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

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

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

1^st part  – left side of 4^th smallest

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

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

4^th part- after 10^th 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 (8^th smallest)

then we took |S| comparisions for 2 elements (4^th and 10^th  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.

Answer 2

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)

 

For clarity image : https://drive.google.com/open?id=1hnIVb86YsTdDVPDbOXfOwlMCKL48z1Ks

Note :- assuming those are positive integers.

Comments

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.

Answer 3

a) should be the answer

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.

Comments

I'm not sure about the correct answer.

---

If I am not wrong this is TC and not the number of comparisons.

Answer 4

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.