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:

Consider the partition method in Quicksort. It positions the pivot to the correct location and returns the index of the pivot element. Now, suppose the partition returns k; can you determine what the kth smallest element is?

Yes, that's correct – the pivot element is the kth smallest element. (Please take a moment to think about it).
 

The Select algorithm operates similarly. The function Select(S, r) not only returns the rth smallest element but also positions it correctly within the array, same as the behavior of the partition method in quicksort. (If their implementation of Select(S, r) is not doing so, then I will find the rth smallest and rearrange my array manually, but let's not worry about it).

Now, let's focus on the main part: How to efficiently implement the MultiSelect() function?

To explain the idea, let's consider an example. Suppose R = {2, 4, 6, 8, 10, 12}, indicating that you want the 2nd smallest, 4th smallest, 6th smallest, and so on.

Here's the approach:

1. Select the middle element of R (e.g., 8) and search for the 8th smallest element in O(S) time.
2. After finding the 8th smallest, observe that it is in its correct position in the array. The elements smaller than 8 are on the left side, and those larger are on the right side.
3. Now, search for the 4th smallest element. Rather than searching the entire array, focus on the left side of the 8th smallest element. Suppose there are K elements on the left and |S| - K on the right.
4. Find the 4th smallest on the left and the 10th smallest on the right, all within |S| comparisons.
5. The array now has the 4th, 8th, and 10th smallest elements in their correct positions, allowing it to be divided into four parts.
   - 1st part: Left side of the 4th smallest
   - 2nd part: Between the 4th and 8th smallest
   - 3rd part: Between the 8th and 10th smallest
    - 4th part: After the 10th smallest
6. Repeat the process. At each level of the tree, divide the array into twice as many parts as the previous level.
7. The pattern: initially, |S| comparisons for 1 element (8th smallest), followed by |S| comparisons for 2 elements (4th and 10th smallest), and then |S| comparisons for 4 elements.
8.  Visualizing this as a tree, starting with the array and dividing it into 2, 4, and so on, the total comparisons become |S| log |R|, where |R| is the total number of elements in the set.
9. Carefully considering the levels of the tree, the total number of levels is log |R| + 1, resulting in the answer E.

A similar question can be found on page 6, question number 5, available at the following link: practicefinalsol.pdf.

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.