1.  Solve the recurrence:

	T(n) = T(n/2) + O(log n)

2.  Consider the statements (1) "If f(i) >= f(j) then q(i) >= q(j)",
    and (2) "If q(i) < q(j) then f(i) <= f(j)".  Relate these
    statements, i.e. state if they are equivalent, or if one implies
    the other etc, or if they are unrelated.  Be sure that you would
    be able to solve this problem if one of the >= was changed to >.

3.  Suppose I toss a fair coin n times.  Show that the probability of
getting at least r heads is at most 

4.  Say that the Hamming distance between two bit strings of the same
    length is the number of positions in which they differ.  For
    example the distance between 10001 and 01001 is 2, since they
    differ in the most significant and the second most significant
    positions.  What is the number of bit strings that are at distance
    3 from the bit string 1001001?

5.  Suppose the average weight of a given set of 100 persons is 60 kg,
    and the average height is 160 cm.  Prove or disprove the following
    statements: 
(1) There must exist at least one person weighing at most 60 kg.
(2) There must exist at least one person weighing at most 60 kg and
    having height at most 160 cm. 
(3) There must exist at least one person weighing at most 120 kg and
    having height at most 320 cm. 

6.  Suppose x[0],...,x[n-1] are n variables.  Suppose you are given
    some m inequalities that these variables satisfy.  Each inequality
    has the form x[i] - x[j] >= q, where q is some positive integer,
    possibly different in each inequality.  You are also given an
    additional integer M.  You are to determine if there exists a
    solution to the inequalities such that each x[i] is between 0 and
    M.

    Give a polynomial time algorithm for this problem.  You are
    expected to observe that it is really a standard problem in
    disguise (or not so good disguise).

7.  Consider a tree with n vertices.  Show that there must exist a
    vertex whose removal disconnects the tree into subtrees each with
    at most n/2 vertices.

-----