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.
T(n) = T(1/2 n) + T(1/4 n) + T(1/6 n) + n.
T(n) = 9T(1/3 n) + 2n2.
T(n) = T(SQAUREROOT(n)) + 1.
Given a sequence a1, a2, ...,
anand a permutation
pi(1), pi(2), ..., pi(n), give an
O(n) algorithm
to rearrange the sequence in place into the order
api(1),
api(2), ...,
api(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.)
State the definition of a binomial tree Bk.
Prove that a binomial tree Bk has C(i,k) = k! / i!(k-1)! nodes at depth i.
Given a directed, acyclic graph G = (V,E) and a pair of
vertices v1 and v2 in V, describe
an O(V + E) algorithm for computing the total number
of distinct paths from v1 to v2 in
G.