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