CS 252: Algorithms

Problem Set #1: Asymptotics review; playing with the Python set data type

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.

1. Do problems 4, 6, and 7 on pages 67-69 of Kleinberg & Tardos. For problem 7, do the problem for "The N Days of Christmas." (If you are unfamiliar with this song you can search on-line for the lyrics of "The Twelve Days of Christmas.")

2. (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.

   1. What do the set operations intersection, union, intersection_update, and update do? (Use the Python help command to get these answers, or search http://docs.python.org/.)
   2. Predict the time complexity of these four operations in terms of |s|, |t|, |s ∪ t|, and |s ∩ t|. Use Θ notation to express your predictions. Give your reasons for your predictions.
   3. Collect timing data to help you observe the time complexity of these four operations empirically. Present your data in an easily read tabular form. Discuss your results, including explanations of differences between your predictions and your observations. To collect timing data, you may use Python's cProfile or timeit modules, or the Unix time command. Update: Here are a test program for cProfile and a test program for timeit.