Computer Engineering (CE)

Question 1: Algorithms

August 2013

Question

Problem 1.

(a) Assume the run time for some algorithm is given by the following recurrence:
$$$T(n) = 2T(\sqrt[]{n}) + \log n$$$

Find the asymptotic run time complexity of this algorithm. Give details of your computation.

(b) Assume functions $f$ and $g$ such that $f(n)$ is $O(g(n))$. Prove or disprove that $3^{f(n)}$ is $O(3^{g(n)})$.

Problem 2.

Suppose your company develops and manages construction of boat launching docks along a downstream stretch of the Wabash river. This stretch runs north-south for $L$ miles within the State of Indiana. The possible sites for docks are given by numbers $x_1 < x_2 < x_3 < ... < x_n$, each in the interval $[0,L]$, specifying their positions in miles measured from the northern end of this stretch of the Wabash river. If your company constructs a dock at position $x_i$, it receives a revenue of $r_i >0$. Regulations imposed by the Indiana Department of Water Resource Management require that no two docks should be built within a distance of less than 5 miles from each other. Your company plans to construct docks at a subset of the potential sites so as to maximize the total revenue., subject to this distance restriction. For example, suppose $L=20$ and $n=5$ with potential sites given by $\lbrace x_1, x_2, x_3, x_4, x_5 \rbrace = \lbrace 6,7,12,13,14\rbrace$ and $\lbrace r_1, r_2, r_3, r_4, r_5 \rbrace = \lbrace 5,6,5,3,1\rbrace$. Then the best solution is to construct docks at locations $x_1$ and $x_3$ to achieve a revenue of 10. Describe a dynamic programming formulation to find a solution for this optimization problem. Compute the complexity of solving your dynamic programming formulation of this problem.

Problem 3. The minimum bottle neck spanning tree (MBST) is a spanning tree that seeks to minimize the use of most expensive (the largest weight) edge in the tree. More specifically, for a tree $T$ over a graph G, we define $e$ to be a bottleneck edge of $T$ if it's an edge with the largest weight. Note, multiple edges may have the same weight. The tree $T$ is an MBST if it is a spanning tree and there is no other spanning tree of G with a cheaper bottleneck edge. Prove or disprove that an MBST for a graph G is always a minimum spanning tree for G.

Problem 4. A project management firm needs to hire technical experts for a project with requires $s$ different specialist. The project requires at least one expert in each of the specialties. The firm has received job application from $t$ potential individuals. An applicant may have multiple areas of expertise. For each of the $s$ specialties, there is some subset of the $t$ applicants qualified in the required technical areas. For a given number $k<t$, is it possible to hire at most $k$ applicants and have at least one expert qualified in each of the $s$ specialties? Prove or disprove that this problem is NP-Complete.