ECE-QE CE1-2015 - Rhea

Question

Part 1.

In the proof of the Master Theorem, a recursion tree is considered for the general recurrence form shown below, representing the contribution of $ f() $ at internal nodes of the tree and of the $ \Theta $(1) base case at the leaves of the tree.

$ T(n) = \begin{cases} \Theta (1) & if\,n = 1 \\ aT(n/b)+f(n) & if\,n=b^i,\,for\,i>0\\ \end{cases} $

Analyzing the recurrence tree for $ n $ an exact power of $ b $, all cases of the proof rely on a $ \Theta $ bound on the contribution of the base case leaves to the sum $ T(n) $. (By asymptotically bounding this expression under the different case assumptions, each case of the Master Theorem is proven.)

$ \bullet $ What is the depth of the tree in terms of $ n,\,a\, $, and $ b $?

$ \bullet $ State the $ \Theta $ bound on the total contribution of all the leaves in the tree. Explain briefly.

$ \bullet $ Give an expression representing the contribution of all the internal nodes of the recursion tree at a given depth $ j $, explaining briefly.

Click here to view student answers and discussions

Part 2.

Let $ Z(t), t\ge 0 $, be a random process obtained by switching between the values 0 and 1 according to the event times in a counting process $ N(t) $. Let $ P(Z(0)=0)=p $ and

$ P(N(t)=k) = \frac{1}{1+\lambda t}(\frac{\lambda t}{1+\lambda t})^k $

for $ k = 0, 1, ... $. Find the pmf of $ Z(t) $.

Click here to view student answers and discussions

Part 3.

Let $ X $ and $ Y $ be independent identically distributed exponential random variables with mean $ \mu $. Find the characteristic function of $ X+Y $.

Click here to view student answers and discussions

Part 4.

Consider a sequence of independent and identically distributed random variables $ X_1,X_2,... X_n $, where each $ X_i $ has mean $ \mu = 0 $ and variance $ \sigma^2 $. Show that for every $ i=1,...,n $ the random variables $ S_n $ and $ X_i-S_n $, where $ S_n=\sum_{j=1}^{n}X_j $ is the sample mean, are uncorrelated.

Click here to view student answers and discussions

Back to ECE Qualifying Exams (QE) page