Question

**You were given a kettle of n birds, which look all the
same to you. To decide if two birds are of the same species, you
perform the following experiment – you put the two of them in a
cage together. If they are friendly to each other, then they are of
the same species. Otherwise, you separate them quickly before
survival of the fittest kicks in.**

1. Suppose that strictly more than half of the birds belong to the same species. Describe and analyze an efficient algorithm that identifies every bird among the n birds that belong to this dominant species.

Answer #1

the idea behind solving the above-given problem is through Moore’s Voting algorithm.

like, let's say that we have an array of a[] indicating the birds let's assume that the A, C, D belongs to the dominant species.

a[]= A B C D E

So here we keep two possible values and keep their count. these values indicate that they are the ones that are present in the majority in the group. Let's say these are first and second and c1=0,c2=0 are their respective counts.

so initially first='*' and second ='*' and c1=0,c2=0;

now we loop over all the species from i=0 to i=4. (n-1=4)

i=0 : first!='A'. && second !='A' but c1==0 so we make first='A' and c1=1;

i=1: first!='B'. && second !='B' && c1!=0 but c2==0 so we make second='B' and c2=1;

i=2 first!='C'. && second !='B' && c1!=0 but c2!=0 so we make c1--,c2-- both becomes 0. Here assuming that C don't belong to the group of both 'A' & 'B'.

i=3 first=='D' so make c1++; c1=1;

i=4 first=='E' so make c1++; c1=2;

Here first=='X' this means that it is checking if these two belong to the same group or not. See the code given below for more details

so the basic code behind this is given below

bool check( char x, char y){

return (fight(x,y)); // this will call some random function which will tell if thspecies x,y belong to same type or not

}

`for`

`(`

`int`

```
i = 0; i
< n; i++) {
```

` `

`if`

`(check(first,a[i]))`

` `

`count1++;`

` `

`else`

`if`

`(check(second,a[i]))`

` `

`count2++;`

` `

`else`

`if`

`(count1 == 0) {`

` `

`count1++;`

` `

```
first
= a[i];
```

` `

`}`

` `

`else`

`if`

`(count2 == 0) {`

` `

`count2++;`

` `

```
second
= a[i];
```

` `

`}`

` `

`else`

`{`

` `

`count1--;`

` `

`count2--;`

` `

`}`

`}`

Now we just need to loop one more time over all N species and check the number of counts that the species belong to the first and second. Fo any of these two whichever will have more than half of the species will be that answer;

int cnt1=0,cnt2=0;

for(int i=0;i<n;i++)

{

if(check(a[i],first)

cnt1++;

else if(check(a[i],second)

cnt2++;

}

if(cnt1>n/2)

cout<<first<<"\n;

else if(cnt2>n/2)

cout<<second <<"\n";

else

cout<<"answer not possible";

So the time complexity for the above code is O(n) where n is size of the array.

You were given a kettle of n birds, which look all the
same to you. To decide if two birds are of the same species, you
perform the following experiment – you put the two of them in a
cage together. If they are friendly to each other, then they are of
the same species. Otherwise, you separate them quickly before
survival of the fittest kicks in.
1. Suppose that there are exactly p species present in your
kettle of...

The assignment summary sheets will be submitted week 14 with
Test 3.
You are to personally experience the power and satisfaction of
developing these skills firsthand and to reflect and write about
this experience. Over the years, many students have shared
amazingly rewarding experiences as they worked on these skills.
The assignment will be evaluated and be weighted as 5% of your
final mark (together, they are worth 20% of your mark for Test 3,
which is worth 25% of...

What tools could AA leaders have used to increase their
awareness of internal and external issues?
???ALASKA AIRLINES: NAVIGATING CHANGE
In the autumn of 2007, Alaska Airlines executives adjourned at
the end of a long and stressful day in the
midst of a multi-day strategic planning session. Most headed
outside to relax, unwind and enjoy a bonfire
on the shore of Semiahmoo Spit, outside the meeting venue in
Blaine, a seaport town in northwest
Washington state.
Meanwhile, several members of...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 15 minutes ago

asked 16 minutes ago

asked 24 minutes ago

asked 53 minutes ago

asked 56 minutes ago

asked 56 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago