Due Friday 12

1.  Problems 1 and 2 of Electronic notes on Sorting Lower bounds.

2.  Consider the randomized algorithm for selection (discussed earlier
    in class and also given in the text).  Adapt the analysis of
    quicksort to show that the expected number of comparisons is O(n).

3.  An independent set in a graph is a subset V' of vertices such that
    if any u,v belong to it then (u,v) must NOT be an edge.  Suppose
    you are given a graph and want to find the largest cardinality
    (also called maximum) independent set.  Suppose you were given a
    procedure to do Integer Programming.  Show how you would use this
    procedure to find the maximum independent set.

4.  Is Euclid's algorithm for GCD polynomial time or pseudo-polynomial
    time?  How about the high school algorithm -- find common factors
    etc.

----