Suppose we have a collection of n different subsets of the set { 1, 2, ..., n }

Question

Suppose we have a collection of n different subsets of the set { 1, 2, ..., n } and they are in some arbitrary order, that is, we have subsets S1, S2, ..., Sn, but how many and which elements are in each of these subsets is entirely arbitrary. Suppose also that we have another subset S' of { 1, 2, ..., n }.

(a) Express a brute-force algorithm that determines whether S' equal to one of the subsets in the collection.

(b) Give a big-O worst case estimate as a function of n for the time complexity of your algorithm. To receive full credit, you must explain how you obtained your answer.

Explanation / Answer

For all sets from S1 to Sn
{
   if Compare(Si,S')
   {
   print("Equal to subset "+i)
   }
}
Compare(S1,S2){
   l1 = len(S1);
   l2 = len(S2);
   if(l1!=l2)
   {
       return false;
   }
   hat=0;
   ans=0;
   for(i=0;i<l1;i++)
   {
       for(j=0;j<l2;j++)
       {
           if(S1[i]==S2[j])
           {
               S2[j] *= -1;
               hat=1;
               break;
           }
       }
       if(hat==1)
       {
           hat=0;
       }
       else
       {
           ans=1;
       }
   }
   if(ans==1)
   {
       return false;
   }
   else
   {
       return true;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.