In class, we discussed a recursive algorithm for generating the power set of a s

Question

In class, we discussed a recursive algorithm for generating the power set of a set T, i.e., the set of all possible subsets of T. In this assignment, you will develop a well-documented pseudocode that generates all possible subsets of a given set of size n with the following requirements: your solution must be non-recursive, and must use a stack and a queue to solve the problem. For example: if set T = {2, 4, 7, 9} then your algorithm would generate: {}, {2}, {4}, {7}, {9}, {2, 4}, {2, 7}, {2, 9}, {4, 7}, {4, 9}, {7, 9}, ...etc. b) Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations.

Explanation / Answer

//pseudocode to generate power set..
//non-recursive algorithm
void printPowerSet(char set[], int size)
{
  
    unsigned int pow_set_size = pow(2, size);///calculating the power set size...
    int counter, j;//setting counter variables to generate all possible values..

    //counter variable runs from 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < size; j++)
       {
          if(counter & (1<<j))//checking whether the jth bit in the counter is if yes then print jth element from set..
            printf("%c", set[j]);//printing the subset string elements...
       }
       printf(" ");//after printing one subset...printing line
    }
}

Complexity of this algorithm is: O(n2^n)//n is set size which is given

explanation:-

the outerloop runs..upto 2^setsize, means 2^n,

and inner loop runs upto given set size which is n..

hence total : n*2^n

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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