You were given a kettle of n birds, which look all thesame to you. To decide if two birds are of the same species, youperform the following experiment – you put the two of them in acage together. If they are friendly to each other, then they are ofthe same species. Otherwise, you separate them quickly beforesurvival of the fittest kicks in.
1. Suppose that there are exactly p species present in yourkettle of n birds. and one species has a plurality: more birdsbelong to that species than to any other species. Present aprocedure to pick out the birds from the plurality species asefficiently as possible (i.e., minimize the number of experimentsyou have to do as a function of n and p). Do not assume that p =O(1).
