CS:3330:0001 Algorithms Project 1: Due 9/26/2019

We will implement a class called nSet, for operations over sets of natural numbers (starting from 0). In this presentation, an element of a set is represented by a bit. We will use as much as possible bit-wise operations for set operations. To help you get started, we provide the following java code nSet.java which contains the constructor of the class and several methods. Some methods are implemented and some are to be implemented by you.

You are asked to complete the following methds/opertions: 

public boolean delete (int x) {
   // remove x from this set if x exists and return true;      
   // otherwise, return false.
} 
	 
public nSet intersect (nSet X) {
   // return a new nSet, the intersection of this nSet and X
} 
	
public nSet subtract (nSet X) {
   // return a new nSet, the subtraction of this nSet by X
} 
	
public nSet complement() {
   // return a new nSet, the complement of this nSet
} 
	
public boolean equal(nSet X) {
   // return true iff X and this nSet contain the same set of numbers
}
	
public boolean isSubset(nSet X) {
   // return true iff X is a subset of this nSet
}
	
public int[] toArray () {
   // return an int array which contains all the numbers in this nSet
} 
	
public void enumerate() {
   // Enumerate all subsets of this nSet and print them out.
   // You may assume this nSet contains less than 30 numbers.
}

Once you have finished the above methods, please run all the tests (including the ones commented out currently) in the method main().

Please analyze the time complexity of each method in terms of the maximal number in the set. The score will depend on the correctness of the implementations and how bit-wise operations are used to maximaze efficiency.

Submit your code and the transcript of the execution in the ICON dropbox for Project 1 before the deadline.

Thank you!