Topics:
- abstract data types: set, multiset (bag)
- concrete data structures: hash table, circular buffer
- set operations
Challenges:
- implement
HashSet
class (set with hash table) with the following set operations as instance methods and properties:__init__(elements=None)
- initialize a new empty set structure, and add each element if a sequence is givensize
- property that tracks the number of elements in constant timecontains(element)
- check whetherelement
is in this setadd(element)
- addelement
to this set, if not present alreadyremove(element)
- removeelement
from this set, if presentunion(other_set)
- return the union of this set andother_set
intersection(other_set)
- return the intersection of this set andother_set
difference(other_set)
- return the difference of this set andother_set
is_subset(other_set)
- check whetherother_set
is a subset of this set
- write your own unit tests for your
HashSet
class- include test cases for each class instance method
- annotate all class instance methods with running time complexity analysis
Stretch Challenges:
- implement
CircularBuffer
class with dynamic array - write your own unit tests for your
CircularBuffer
class- include test cases for each class instance method
- annotate all class instance methods with running time complexity analysis