retagged by
2,425 views
18 votes
18 votes

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|)$
retagged by

6 Answers

Best answer
6 votes
6 votes

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.

6 votes
6 votes


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.

edited by
4 votes
4 votes
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.
0 votes
0 votes
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.
Answer:

Related questions