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.
Show a directed acyclic graph with no more than 5 vertices with edge costs in the real numbers and a designated source vertex for which Dijkstra's algorithm does not compute correct shortest path costs. Label the vertices with letter from $ \{a,b,c,d,e\} $, using $ a $ as the source; but note you do not necessarily need all five. Also show the order in which Dijkstra's algorithm will assign shortest path costs and what those assigned costs are, as well as what the correct values are.
- 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.
Describe an efficient algorithm for finding this network, given the costs $ \alpha(\cdot,\cdot) $ and the set $ E $ of environmentally sensitive pairs $ (x,y) $. Sketch a correctness argument for the algorithm. State the worst case asymptotic complexity of your algorithm in terms of $ n $. You may use any algorithm defined in the reading list without presenting its details as long as you are clear about how it is used. In fact, your solution should be a small adaptation of an algorithm defined in the reading list to ensure that the network returned will respect the political constraint.
- Click here to view student answers and discussions
