TIFR CSE 2011 | Part B | Question: 31

Question

Given a set of $n=2^{k}$ distinct numbers, we would like to determine the smallest and the second smallest using comparisons. Which of the following statements is TRUE?

• A. Both these elements can be determined using $2k$ comparisons.
• B. Both these elements can be determined using $n - 2$ comparisons.
• C. Both these elements can be determined using $n + k - 2$ comparisons.
• D. $2n - 3$ comparisons are necessary to determine these two elements.
• E. $nk$ comparisons are necessary to determine these two elements.

Comments

What is $\mathbf k$ here?

Is it the $\mathbf 2$ elements which we need to compare finally?

Or is it just the representation?

---

elements are in 2 POWER k

---

WATCH THIS  FOR BETTER UNDERSTANDING CLEARLY EXPLAINED ALL THESE TYPE OF PROBLEMS 

Answer 1

Option (c) $n+k-2$

Here is a nice explanation of the algorithm: http://www.codinghelmet.com/?path=exercises/two-smallest

it is solution to the problem known for ages, and it has to do with tennis tournaments. The question was, knowing the outcome of the tennis tournament, how can we tell which player was the second best? The defeated finalist is a good candidate, but there are other players that were defeated directly by the tournament winner and any of them could also be a good candidate for the second best. So the solution to the problem is quite simple: Once the tournament finishes, pick up the $\log N$ competitors that were beaten by the tournament winner and hold a mini-tournament to find which one is the best among them. If we imagine that better players correspond with smaller numbers, the algorithm now goes like this. Hold the tournament to find the smallest number (requires $N-1$ comparisons). During this step, for each number construct the list of numbers it was smaller than. Finally, pick the list of numbers associated with the smallest number and find their minimum in $\log N-1$ steps. This algorithm requires $N+\log N-2$ comparisons to complete, but unfortunately it requires additional space proportional to N (each element except the winner will ultimately be added to someone’s list); it also requires more time per step because of the relatively complex enlisting logic involved in each comparison. When this optimized algorithm is applied to example array, we get the following figure.

Tournament held among numbers promotes value $1$ as the smallest number. That operation, performed on an array with nine numbers, requires exactly eight comparisons. While promoting the smallest number, this operation has also flagged four numbers that were removed from competition by direct comparison with the future winner: $6, 2, 3$ and $8$ in that order. Another sequence of three comparisons is required to promote number $2$ as the second-smallest number in the array. This totals $11$ comparisons, while naive algorithm requires $17$ comparisons to come up with the same result.

All in all, this algorithm that minimizes number of comparisons looks to be good only for real tournaments, while number cracking algorithms should keep with the simple logic explained above. Implementation of simple algorithm may look like this:

a – array containing n elements  
min1 = a[0] – candidate for the smallest value  
min2 = a[1] – candidate for the second smallest value
if min2 < min1
    min1 = a[1]
    min2 = a[0]
for i = 2 to n – 1
    if a[i] < min1
        min2 = min1
        min1 = a[i]
    else if a[i] < min2
        min2 = a[i]

by Zoran Horvat @zoranh75

Comments

Tournament method for finding second smallest??

---

The above method is Tournament method, isn’t it?

---

No @neel19 if we apply naive algorithm then it would take 2n-1 comparisons when we apply tournament method then it would take n+logn-2

Answer 2

Second smallest of n elements can be found with n+ceil(lg n)-2 comparisons in worst case .This result is present in exercise question of CLRS book Edition 3 chapter 9 - Medians and Order Statistics

First we do n-1 comparisons to find first smallest among n element.Now there are lg(n) element left who lost to first smallest element.Take lg(n) element find second smallest element in lg(n) -1 comparisons.Note:For finding second smallest we need to find first smallest.

Total comparisons=n-1+lg(n)-1=n+lg(n)-2

ATQ

n=2^k distinct number 

Use above result n+lg(n)-2=n+lg(2^k)-2=n+k-2

So c is ans.

 

Comments

@himanshu26 ,Thanks !, but , My doubt is how to implement in program to save these lost elements ?, like how to get that 8,2,4 are defeated ?

---

Gfg have algorithm for this. Refer:

https://www.google.com/amp/s/www.geeksforgeeks.org/second-minimum-element-using-minimum-comparisons/amp/

---

In the question, it is mentioned that all values are distinct and the size of the array is of the order of  $2^k$. This will yield the same type of complete binary tree for any value of $k$. If we do a heapify then we can get the smallest element with an $n-1$ number of comparisons. Next, for finding the second smallest number we just have to do one more comparison with the children of the root element. Therefore, the total number of comparisons will equal to $n – 1 +1 = n$ according to me.

Please let me know if there is any fault with this argument.

Answer 3

this can be done by OPTION ELIMINATION too

let us assume k=5 for all cases (n=32)

 

a.) 2k = 10

if array is already sorted(descending order) , then smallest will be last , so WRONG

 

b.)n-2=30

same explaination as above , bcz to find smallest and 2nd smallest, each cell is compared TWICE . WRONG

 

e.)nk = nlogn

that is merge sort , thus this is NOT the Optimal as it sorts the array too . WRONG

 

d.)2n-3 = 2(n-1)-1

these number of comparison will be MORE than suffice , assume min=A[0] and min_2 =A[0] , compare min and min_2 with remaining cells (ie n-1 cells) twice (WRONG bcz option says NECESSARY , which is not true)

 

c.) n+k-2 = n+logn -2

this is the BEST OPTION

build min heap =O(n)

extract Min = O(log n)

then compare the 2 elements after removing min

Answer 4

For the problem of finding minimum and second minimum, there is a better algorithm based on tournaments. Here we compare A[2i−1] with A[2i] for i = 1 to n. (We assume for simplicity that n is even.) We compare the ”winners” in pairs and so on. For example, see the diagram below:

The light blue cells are those that lost to the final winner (in green). The red are those that lost to the light blue ones and dark blue is one that lost to a red. So for the second minimum we need only compare the light blue ones. There is exactly one of these per level and there are log n levels and hence we get a total of n + log n − 2 comparisons in all.