Algorithms B-Exam
January, 1997

1. Give an asymptotically tight solution (big Theta) for each of the following recurrences. You may assume that T(1) = 1. You need not prove your solution correct.
   1. T(n) = T(1/2 n) + T(1/4 n) + T(1/6 n) + n.
   2. T(n) = 9T(1/3 n) + 2n².
   3. T(n) = T(SQAUREROOT(n)) + 1.

2. Given a sequence a₁, a₂, ..., a_nand a permutation pi(1), pi(2), ..., pi(n), give an O(n) algorithm to rearrange the sequence in place into the order a_pi(1), a_pi(2), ..., a_pi(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) = k! / i!(k-1)!
   nodes at depth i.

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