1. Give an asymptotically tight solution (big θ) for each of the following recurrences. You may assume that T (1) = 1. You need not prove your solution correct.

(a)

T (n) = T (\frac{1}{2}n) + T (\frac{1}{4}n) + T (\frac{1}{6}n) + n.

(b)

T (n) = 9T (\frac{1}{3}n) + 2n^{2}.

(c)

T (n) = T (\sqrt{n}) + 1.

2. Given a sequence a_{1}, a_{2}, ..., a_{n} and a permutation π(1), π(2), ..., π(n), give an O(n) algorithm to rearrange the sequence in place into the order a_{π(1)}, a_{π(2)}, ..., a_{π(n)}. Your algorithm may use at most n + O(1) extra bits of space. (Note that this restriction means you cannot copy into an auxiliary array or use recursion.)

3. State the definition of a binomial tree B_{k}. Prove that a binomial tree B_{k} has C(i, k) = \frac{k!}{i!(k−i)!} nodes at depth i.

4. Given a directed, acyclic graph G = (V, E) and a pair of vertices v_{1} and v_{2} in V, describe an O(V +E) algorithm for computing the total number of distinct paths from v_{1} to v_{2} in G.