1. Engineering
  2. Computer Science
  3. computer algorithms hw quotwe will implement a class called nset...

Question: computer algorithms hw quotwe will implement a class called nset...

Question details

Computer Algorithms HW "We will implement a class called nSet, for operations over sets of natural numbers."
We will implement a class called nSet, for operations over sets of natural numbers. 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) f // 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) I // 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) f // 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 the following test in the method mainO 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 efficiencyThe following is Java code is required to solve and is from the link nSet.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import static java.lang.Integer.max;
import static java.lang.Integer.min;

/**
 * For complexity analysis, let m be this.max and n be the number of elements in this set.
 */

public class nSet {
    // this class implements the set operations over sets of natural numbers.
    public int Max;        // maximal natural number in any set
    private int n_long;    // the number of long integers: 64*n_long > Max
    private long[] store;  // the store has n_long longs
    private int size;      // remember the size of the current set

    // Constructor: runtime = O(m), with a small constant less than 1
    public nSet(int n) {
        this.Max = n;
        if (n < 0) { this.Max = 1; }
        this.n_long = (n >> 6) + 1; // n_long = n/64+1, number of longs
        this.store = new long[n_long];
        for (int i = 0; i this.Max) return;
        int i = (x>>6);     // i = x/64
        int j = x - (i<<6); // j = x % 64, i.e., 64i + j = x
        long y = this.store[i];
        if (((y>>j) & 1) == 1) return;   // if x is present, do nothing
        this.store[i] |= ((long) 1< this.Max) return false;
        int i = (x>>6);     // i = x/64
        int j = x - (i<<6); // j = x % 64, i.e., 64i + j = x
        long y = this.store[i];
        return ((y>>j) & 1) == 1; // "&" is the bitwise OR operation
    }


    //O(m) runtime, with a small constant less than 1
    public void clear () {
        for(int i = 0; i>j) & 1) == 1)
                    counter++;
            }
        }
        this.size = counter;
    }

    // Constant runtime
    public void print () {
        // print up to 30 numbers in the current nSet
        System.out.print("{ ");
        int count = 0;
        for(int i=0; i> j) & 1) == 1) {                        
                    System.out.print(((i << 6) + j)+", ");    
                    if (++count >= 30) {
                        System.out.println("... }");
                        return;
                    }
                }
        System.out.println("}");
    }


    // O(m) runtime
    public nSet union (nSet X) {
        int maximum = max(this.Max, X.Max);
        nSet A = new nSet(maximum);

        for(int i=0 ;i < n_long; i++) {
            A.store[i] = this.store[i] | X.store[i];
        }
        
        A.set_size();
        return A;
    }


    /* You need to complete the implementation of the following operations:

    public boolean isEmpty () {
        // return true iff the current nSet is empty
    }

    public boolean delete (int x) {
        // return false if x isn't in the set;
        // delete the number x from the current set and return true.
    }


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


    public static void main(String[] args) {
        // testing
        nSet A = new nSet(1000);

        for (int i = 1; i

Thank you for your help.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution