NOTE: Fill in with the appropriate items
Elapsed | Time | Activity |
---|---|---|
0:00 | 0:05 | Objectives |
0:05 | 0:15 | Overview |
0:20 | 0:45 | In Class Activity I |
1:05 | 0:10 | BREAK |
1:15 | 0:45 | In Class Activity II |
TOTAL | 2:00 |
NOTE: Fill in with the appropriate items
By this end of this lesson, students should be able to...
- Explain what a set is and what some varitions of a set are, such as a multiset
- Explain other types of queues such as a circuluar buffer
- Practice implementing more abstract data types backed by a data structure of their choice
- Abstract data types: set, multiset (bag)
- Concrete data structures: hash table, circular buffer (circular queue, ring buffer)
- Set operations
- Read Vaidehi Joshi's article on sets and their use in databases with beautiful drawings and excellent examples
- Implement
Set
class (abstract data type backed by data structure of your choice) 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)
- return a boolean indicating whetherelement
is in this setadd(element)
- addelement
to this set, if not present alreadyremove(element)
- removeelement
from this set, if present, or else raiseKeyError
union(other_set)
- return a new set that is the union of this set andother_set
intersection(other_set)
- return a new set that is the intersection of this set andother_set
difference(other_set)
- return a new set that is the difference of this set andother_set
is_subset(other_set)
- return a boolean indicating whetherother_set
is a subset of this set
- Write unit tests to ensure the
Set
class is robust- Include test cases for each class instance method
- Annotate all instance methods with complexity analysis of running time and space (memory)
- Compare the behaviors of your
Set
class to those of the Pythonset
type and SwiftSet
type
- Implement
CircularBuffer
class (backed by dynamic array) with the following instance methods and properties:__init__(max_size)
- initialize a new circular buffer that can store at mostmax_size
itemssize
- property that tracks the number of items in the bufferis_empty
- check if the buffer is emptyis_full
- check if the buffer is fullenqueue(item)
- insertitem
at the back of the bufferfront
- return the item at the front of the bufferdequeue
- remove and return the item at the front of the buffer
- Annotate
enqueue
anddequeue
methods with running time complexity analysis - Write unit tests to ensure the
CircularBuffer
class is robust- Include test cases for each class instance method and property
- Annotate
enqueue
anddequeue
methods with running time complexity analysis