Line 1: Line 1:
 
[[Category:ECE]]
 
[[Category:ECE]]
 
[[Category:QE]]
 
[[Category:QE]]
−
[[Category:CNSIP]]
+
[[Category:CE]]
 
[[Category:problem solving]]
 
[[Category:problem solving]]
−
[[Category:random variables]]
+
[[Category:algorithms]]
−
[[Category:probability]]
+
  
  
Line 13: Line 12:
  
 
<font size= 4>
 
<font size= 4>
−
Communication, Networking, Signal and Image Processing (CS)
+
Computer Engineering(CE)
  
−
Question 1: Probability and Random Processes
+
Question 1: Algorithms
 
</font size>
 
</font size>
  
Line 22: Line 21:
 
----
 
----
 
===Solution 1===
 
===Solution 1===
−
Let <math>\lambda = \frac{1}{\mu}</math>, then <math>E(X)=E(Y)=\frac{1}{\lambda}</math>.  
+
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>.
  
−
<math>
+
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>.
−
\phi_{X+Y}=E[e^{it(X+Y)}]=\int_{X}\int_{Y}e^{it(X+Y)}p(x,y)dxdy
+
−
</math>
+
  
−
As X and Y are independent
+
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>.
  
−
<math>
+
[[ECE-QE_CE1-2015|Back to QE CE question 1, August 2015]]
−
\phi_{X+Y}=\int_{X}\int_{Y}e^{it(x+y)}p(x)p(y)dxdy = \int_{X}e^{itx}p(x)dx\int_{Y}e^{ity}p(y)dy=\phi_{X}\phi_{Y}
+
−
</math>
+
−
 
+
−
And
+
−
<math>
+
−
\phi_{X}=E[e^{itX}]=\int_{-\infty}^{\infty}e^{itx}\lambda e^{-\lambda x} dx \\
+
−
= \lambda \int_{-\infty}^{\infty}e^{-(\lambda -iu)x} dx = -\frac{\lambda}{\lambda-iu}e^{-(\lambda-iu)x}|_0^\infty\\
+
−
=\frac{\lambda}{\lambda-iu}
+
−
</math>
+
−
 
+
−
So
+
−
<math>
+
−
\phi_{X+Y}=E[e^{it(X+Y)}]=\phi_{X}\phi_{Y} =( \frac{\lambda}{\lambda-iu})^2=\frac{1}{(1+iu\mu)^2}
+
−
</math>
+
−
 
+
−
===Solution 2===
+
−
<math>
+
−
\phi_X(w)=E[e^{iwX}]=\int_0^{+\infty}e^{iwX}\frac{1}{\mu}e^{-\frac{x}{\mu}}dx=e^{X(iw-\frac{1}{\mu})}\frac{1}{\mu}\frac{1}{iw-\frac{1}{\mu}}|_0^{+\infty}\\
+
−
= 0 - \frac{1}{\mu}\cdot\frac{1}{iw-\frac{1}{\mu}}=\frac{1}{1-iw\mu}\\
+
−
\phi_{X+Y}(w)=E[e^{iw(X+Y)}]\\
+
−
=\int\int e^{iw(X+Y)}f_X(x)f_Y(y)dxdy = \int e^{iwx}f_X(x)dx \cdot \int e^{iwy}f_Y(y)dy=\phi_X(w)\phi_Y(w)\\
+
−
=\frac{1}{(1+iw\mu)^2}
+
−
</math>
+
−
 
+
−
===Solution 3===
+
−
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:
+
−
 
+
−
<math>
+
−
\phi_{X+Y}(\omega) = \phi_X(\omega)\phi_Y(\omega)
+
−
</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>.
+
−
 
+
−
Next, we recall that the mean of an exponential random variable is equal to the inverse of its parameter, i.e. <math>\frac{1}{\lambda}</math>. Then the above expression becomes
+
−
 
+
−
<math>
+
−
\phi_{X+Y}(\omega) = \left(\frac{\frac{1}{\mu}}{\frac{1}{\mu} - i\omega}\right)^2.
+
−
</math>.
+
−
 
+
−
Multiplying by <math>\frac{\mu}{\mu}</math> gives
+
−
 
+
−
<math>
+
−
\phi_{X+Y}(\omega) = \left(\frac{1}{1-i\omega\mu}\right)^2
+
−
</math>
+
−
 
+
−
===Similar Problem===
+
−
 
+
−
Let <math>X(t)</math> be a Poisson random process with mean function <math>\mu(t)</math> and covariance function <math>C_{xx}(t_1,t_2)</math>. Find the <math>n^{th}</math>-order characteristic function of <math>X(t)</math>.
+
−
----
+
−
[[ECE-QE_CS1-2015|Back to QE CS question 1, August 2015]]
+
  
 
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]
 
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]

Revision as of 20:45, 7 March 2016


ECE Ph.D. Qualifying Exam

Computer Engineering(CE)

Question 1: Algorithms

August 2015

Solution 1

First, it is fairly straightforward to see that the depth of the tree is given by $ \log_b n $. Observe that the cost of each leaf is $ T(1) = \Theta(1) $. The subproblem size decreases by a factor of $ b $ every time we descend a level in the tree, so it must be true that when the subproblem size is 1, the equality $ n/b^j = 1 $ must hold. Then the depth of the tree, $ j $, must be $ \log_b n $.

For the second part of the problem, not that the subproblem size of each leaf is $ T(1) $, 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 $ a $ children, and each child will have $ a $ children of its own. Thus the number of nodes at level $ j $ of the tree is given by $ a^j $. Thus since the depth of the leaves is $ \log_b n $, we have that the number of leaves in the tree is $ a^{\log_b n} = n^{\log_b a} $, and that the total contribution of the leaves is bounded by $ \Theta(n^{\log_b a}) $.

For the final part of the problem, recall that there are $ j $ nodes at the $ j $-th level of the tree, so we are done if we can find the contribution of each node at the $ j $-th level. Now recall that the cost of the root node is given by $ f(n) $. The function $ f(\cdot) $ is independent of level, so it is easy to see that the cost of a node at the $ j $-th level of the tree is given by $ f(n/b^j) $ (since the size of a subproblem at level $ j $ is given by $ n/b^j $). Then it follows from the expressions for number of nodes at the $ j $-th level and cost of each node at the $ j $-th level that the cost of all the nodes on the $ j $-th level is $ a^j f(n/b^j) $.

Back to QE CE question 1, August 2015

Back to ECE Qualifying Exams (QE) page

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=ECE_PhD_QE_CNSIP_2015_Problem1.3&oldid=71259"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood