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

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang