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.
A company has built houses on $ n $ lots and needs to decide on where to build streets connecting the houses. Modeling this as selecting a set of pairs of houses to connect so that all houses in the end have a connected path between them, the company assigns a positive cost $ \alpha(x,y) $ for constructing each possible street connecting two of the houses $ x $ and $ y $ (the streets will all be two-way). However, some of the possible streets cross (and would thus damage) environmentally sensitive sites and it is required to minimize the number of such streets. It is a political constraint that a minimum number of such streets will be selected for being built. Subject to this political constraint, the company wishes to build the cheapest-cost street network (by connecting pairs of houses as above) that connects all the houses.
- Click here to view student answers and discussions
