In class we discussed a recursive algorithm for generating t

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. Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations

Solution

a) Algorithm logic explanation...

Iterating stack every element and push into queue which makes one set, then in second iteration pop one value from stack and with remaining elements make new set using queue and processs repeats until stack gets empty. Resultant will give required power set.

ALGORITHM

GeneratePowerset(Stack dataSet)
{
var powerSetQueue = new Queue { new Set() }; // declaring new queue which hold all power sets
while (!dataSet.IsEmpty)
{
var val = dataSet.Pop();
while (true)
{ // generating sets
var tempSubset = powerSetQueue.Dequeue();
if (tempSubset == new Set())
{
break; // if all sets are generated
}

var subsetEle = tempSubset.Clone();
subsetEle.Add(val);
// adding value into subset queue back.
powerSetQueue.Queue(tempSubset);
powerSetQueue.Queue(subsetEle);
}
}

return powerSetQueue; // final power set
}

-------------------------------------------------------------------------------------------------------------------------------------------------------------

b)

Here to get powerset, iterating the stack in binary form, pushing elements into subsequent two subsets every time, so complexity will be 2^n since binary tree height is 2ⁿ.
So complexity will be O(2ⁿ)