Difference between revisions of "ECE PhD QE CNSIP 2015 Problem1.3" - Rhea

Revision as of 20:55, 7 March 2016

Computer Engineering(CE)

Question 1: Algorithms

August 2015

Solution 3

For this problem, it is very useful to note that for any independent random variables $$ X $$ and $$ Y $$ and their characteristic functions $\phi_X(\omega),\,\phi_Y(\omega)$ we have the following property:

$\phi_{X+Y}(\omega) = \phi_X(\omega)\phi_Y(\omega)$

We then note that the characteristic function of an exponential random variable $$ Z $$ is written as

$\phi_Z (\omega) = \frac{\lambda}{\lambda - i\omega}$

where $\lambda$ parameterizes the exponential distribution. As such, we can write the characteristic function of $$ X+Y $$ as

$\phi_{X+Y}(\omega) &= \phi_X(\omega)\phi_Y(\omega) \\ &= \left(\frac{\lambda}{\lambda-i\omega}\right)^2$

Back to QE CE question 1, August 2015

Back to ECE Qualifying Exams (QE) page

@@ Line 20: / Line 20: @@
 </center>
 ----
-===Solution 1===
+===Solution 3===
-First, it is fairly straightforward to see that the depth of the tree is given by <math>\log_b n</math>. Observe that the cost of each leaf is <math>T(1) = \Theta(1)</math>. The subproblem size decreases by a factor of <math>b</math> every time we descend a level in the tree, so it must be true that when the subproblem size is 1, the equality <math>n/b^j = 1</math> must hold. Then the depth of the tree, <math>j</math>, must be <math>\log_b n</math>.
+For this problem, it is very useful to note that for any independent random variables <math>X</math> and <math>Y</math> and their characteristic functions <math>\phi_X(\omega),\,\phi_Y(\omega)</math> we have the following property:
-For the second part of the problem, not that the subproblem size of each leaf is <math>T(1)</math>, so the question of how many leaves are contained in the tree is equivalent to the question posed. Now let us consider the root of the tree. This node has <math>a</math> children, and each child will have <math>a</math> children of its own. Thus the number of nodes at level <math>j</math> of the tree is given by <math>a^j</math>. Thus since the depth of the leaves is <math>\log_b n</math>, we have that the number of leaves in the tree is <math>a^{\log_b n} = n^{\log_b a}</math>, and that the total contribution of the leaves is bounded by <math>\Theta(n^{\log_b a})</math>.
+<math>
+\phi_{X+Y}(\omega) = \phi_X(\omega)\phi_Y(\omega)
+</math>
-For the final part of the problem, recall that there are <math>j</math> nodes at the <math>j</math>-th level of the tree, so we are done if we can find the contribution of each node at the <math>j</math>-th level. Now recall that the cost of the root node is given by <math>f(n)</math>. The function <math>f(\cdot)</math> is independent of level, so it is easy to see that the cost of a node at the <math>j</math>-th level of the tree is given by <math>f(n/b^j)</math> (since the size of a subproblem at level <math>j</math> is given by <math>n/b^j</math>). Then it follows from the expressions for number of nodes at the <math>j</math>-th level and cost of each node at the <math>j</math>-th level that the cost of all the nodes on the <math>j</math>-th level is <math>a^j f(n/b^j)</math>.
+We then note that the characteristic function of an exponential random variable <math>Z</math> is written as
+<math>
+\phi_Z (\omega) = \frac{\lambda}{\lambda - i\omega}
+</math>
+where <math>\lambda</math> parameterizes the exponential distribution. As such, we can write the characteristic function of <math>X+Y</math> as
+<math>
+\phi_{X+Y}(\omega) &= \phi_X(\omega)\phi_Y(\omega) \\
+&= \left(\frac{\lambda}{\lambda-i\omega}\right)^2
+</math>
 [[ECE-QE_CE1-2015|Back to QE CE question 1, August 2015]]
 [[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]

Difference between revisions of "ECE PhD QE CNSIP 2015 Problem1.3" - Rhea

Revision as of 20:55, 7 March 2016

Solution 3

Alumni Liaison