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