You’ve been asked to throw a party for the newly formed Pet Alliance, an uneasy
ID: 3143873 • Letter: Y
Question
You’ve been asked to throw a party for the newly formed Pet Alliance, an uneasy truce between the university’s cat lovers, dog lovers, parrot lovers, etc. Everybody is very passionate and only loves their one favorite kind of pet. In fact, you have heard that one animal in particular is loved by strictly more than half the guests, and you need to keep a close eye on them to make sure they do not taunt the other guests with more eccentric tastes. Unfortunately, it is rude to simply ask participants their favorite animal. You should just know; do they look like a lover to you? All you can do is introduce pairs of guests; if they get along then they must love the same animal, if they turn their noses at each other, they must love different animals. How do you find this majority of guests that love the same animal?
More formally, you are given an array X[1..n]. The only access you have to X’s data is a procedure Same(x, y) that returns True if x and y are equivalent and False otherwise. Design and analyze a reccurence algorithm to output a member of X whose equivalence class contains strictly greater than n/2 members. For your analysis, give an asymptotic bound on the number of times your algorithm calls Same.
Explanation / Answer
X[1..100]; \array for storing given data
Y[1..100]; \array for counting number of matches for given data. \Initially all Y[i] are set to 0.
int i,j,max=0;
string m; \ for storing True or False value
for(i=1,i<=100,i++)
{
for(j=1,j<=100,j++)
{
m=Same(X[i],X[j]);
if (m="true")
then {Y[i]=Y[i]+1;}
}
}
ow we find member of X[i] whose equivalence class contains strictly greater than n/2 members. that will be the element X[i] for which corresponding Y[i]>100/2 that is more than 50
for(i=1,i<=100,i++)
{
if Y[i]>50
then max=i;
}
Print("Answer is :" X[i]);
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.