ECE Ph.D. Qualifying Exam

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:
$ \begin{equation} T(n) = 2T(\sqrt[]{n}) + \log n \end{equation} $

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)}) $.

Click here to view student answers and discussions

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.

Click here to view student answers and discussions

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.

Click here to view student answers and discussions

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.

Click here to view student answers and discussions

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett