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
