Note that for the four Python-inexperienced people I spoke with after class on Jan 5, the Python problem is due Monday, Jan 12 rather than Friday, Jan 9. For the rest of you, it's due Jan 9. The problems from the book are due on Jan 9 for everybody.
(Thanks to Ron Rivest for this problem idea.) The Python programming
language contains a class called
set.
The set
class supports the usual set theoretic operations like union
and intersection, plus a variety of operations that make working with
set objects convenient. In this exercise, you will predict the
time complexity of a few set operations, and collect timing data
to support (or refute) your predictions.
Here is a small program that uses the set data type, in case you want to see a few set operations in action.
set
operations intersection
,
union
, intersection_update
, and update
do? (Use the Python help
command to get these answers, or
search http://docs.python.org/.)