For this homework, there is no starter file. You have to create your own .py file and submit it to Autolab. You can take a previous starter file and modify it appropriately.
Please add your name, Andrew id, and section at the top of the file.
APPLY TOP-DOWN DESIGN, USE LOTS OF HELPER FUNCTIONS.
This homework will be manually graded.
You will be graded on style. You can lose up to 10 poins for style (out of 100 points). Please see here for the style rubric.
You may not use recursion, or any other constructs that we have not yet covered in class.
You will have 2 submissions on Autolab for this homework.
Questions
- Write a class called mySet that works like the built-in set class. Before you start this problem, first review how sets work internally by rewatching the relevant portion of Lecture 3.3. In particular, you should understand how a hashtable works. Sets cannot contain mutable elements. For example, if you tried to do s = set([1,2,[3]]), you would get the error "unhashable type: list". In our implementation of mySet, we will ignore this issue and assume that the user will always add immutable elements to the set.
- Class attributes: There should be one class attribute called maxBucketSize. It should be set to 10 and you should never change its value.
- Data members: There should be 2 data members: numBuckets and hashTable. Initially numBuckets is set to 2 and hashTable is [ [ ], [ ] ].
- Constructor: The constructor should take self and an optional parameter L as input. If the optional argument is not provided, then you should be creating an empty set. If L is provided, then you should create a set from the elements in L. To do this, you might want to call the add method listed below. For example, mySet() would create the empty set {}, and mySet([1,1,2,3]) would create the set {1,2,3} (note that the order of the elements in a set is not important).
- Methods: The class should have the following methods. (See here to recall what these methods are supposed to do.)
- add(self, element)
- remove(self, element)
- clear(self)
- __contains__(self, element) (the built-in in operator calls the __contains__method)
- __len__(self) (the built-in len function calls the __len__ method)
- isSubset(self, other)
- isSuperset(self, other)
- __eq__(self, other) (the built-in == operator calls the __eq__ method)
- __str__(self) (the built-in str function calls the __str__ method)
- union(self, other)
- intersection(self, other)
- difference(self, other)
- symmetricDifference(self, other)
- update(self, other)
- intersectionUpdate(self, other)
- differenceUpdate(self, other)
- symmetricDifferenceUpdate(self, other)
Note1: Some of these methods are destructive and some are not. Be careful about the distinction and what each method should return (if anything).
Note2: As you add elements to the set, if the size of a bucket exceeds maxBucketSize, then you should resize and rehash. To resize, double the number of buckets. Use the built-in hash function for hashing.
-
Do OopyInvaders from here.
