| Line 54: | Line 54: | ||
Let <math>X</math> and <math>Y</math> be independent identically distributed exponential random variables with mean <math>\mu</math>. Find the characteristic function of <math>X+Y</math>. | Let <math>X</math> and <math>Y</math> be independent identically distributed exponential random variables with mean <math>\mu</math>. Find the characteristic function of <math>X+Y</math>. | ||
| − | :'''Click [[ | + | :'''Click [[ECE_PhD_QE_CE_2015_Problem1.3|here]] to view student [[ECE_PhD_QE_CE_2015_Problem1.3|answers and discussions]]''' |
---- | ---- | ||
'''Part 4.''' | '''Part 4.''' | ||
| Line 60: | Line 60: | ||
Consider a sequence of independent and identically distributed random variables <math>X_1,X_2,... X_n</math>, where each <math>X_i</math> has mean <math>\mu = 0</math> and variance <math> \sigma^2</math>. Show that for every <math>i=1,...,n</math> the random variables <math>S_n</math> and <math>X_i-S_n</math>, where <math>S_n=\sum_{j=1}^{n}X_j</math> is the sample mean, are uncorrelated. | Consider a sequence of independent and identically distributed random variables <math>X_1,X_2,... X_n</math>, where each <math>X_i</math> has mean <math>\mu = 0</math> and variance <math> \sigma^2</math>. Show that for every <math>i=1,...,n</math> the random variables <math>S_n</math> and <math>X_i-S_n</math>, where <math>S_n=\sum_{j=1}^{n}X_j</math> is the sample mean, are uncorrelated. | ||
| − | :'''Click [[ | + | :'''Click [[ECE_PhD_QE_CE_2015_Problem1.4|here]] to view student [[ECE_PhD_QE_CE_2015_Problem1.4|answers and discussions]]''' |
---- | ---- | ||
[[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 21:01, 7 March 2016
Computer Engineering (CE)
Question 1: Algorithms
August 2015
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.
Professor Stillinbed has constructed a polynomial-time-bounded program that converts 3-CNF Boolean formulas into graphs. A formula with $ n $ Boolean variables and $ k $ clauses is converted into a graph with $ nk $ vertices. The professor has proven that there is a size 3 clique in the graph if and only if the original 3-CNF formula was satisfiable. Is this a notable or significant result? (In other words, does it add significantly to what is known about efficient problem solution?) Why or why not?
- 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
