| (19 intermediate revisions by the same user not shown) | |||
| Line 21: | Line 21: | ||
---- | ---- | ||
==Question== | ==Question== | ||
| − | ''' | + | '''Problem 1. ''' |
| − | (a) Assume the run time for some algorithm is given by the following recurrence: | + | |
| + | (a) Assume the run time for some algorithm is given by the following recurrence: <br> | ||
<math> | <math> | ||
\begin{equation} | \begin{equation} | ||
| Line 28: | Line 29: | ||
\end{equation} | \end{equation} | ||
</math> | </math> | ||
| − | Find the asymptotic run time complexity of this algorithm. Give | + | |
| + | Find the asymptotic run time complexity of this algorithm. Give details of your computation. | ||
(b) Assume functions <math>f</math> and <math>g</math> such that <math>f(n)</math> is <math>O(g(n))</math>. Prove or disprove that <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math>. | (b) Assume functions <math>f</math> and <math>g</math> such that <math>f(n)</math> is <math>O(g(n))</math>. Prove or disprove that <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math>. | ||
| + | |||
| + | :'''Click [[ECE_PhD_QE_CE_2013_Problem1.1|here]] to view student [[ECE_PhD_QE_CE_2013_Problem1.1|answers and discussions]]''' | ||
---- | ---- | ||
| − | ''' | + | '''Problem 2.''' |
| − | Suppose your company develops and | + | 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 <math>L</math> miles within the State of Indiana. The possible sites for docks are given by numbers <math>x_1 < x_2 < x_3 < ... < x_n</math>, each in the interval <math>[0,L]</math>, 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 <math>x_i</math>, it receives a revenue of <math>r_i >0</math>. 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 <math>L=20</math> and <math>n=5</math> with potential sites given by <math>\lbrace x_1, x_2, x_3, x_4, x_5 \rbrace = \lbrace 6,7,12,13,14\rbrace</math> and <math>\lbrace r_1, r_2, r_3, r_4, r_5 \rbrace = \lbrace 5,6,5,3,1\rbrace</math>. Then the best solution is to construct docks at locations <math>x_1</math> and <math>x_3</math> 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. | 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 [[ECE_PhD_QE_CE_2013_Problem1.2|here]] to view student [[ECE_PhD_QE_CE_2013_Problem1.2|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 <math>T</math> over a graph G, we define <math>e</math> to be a bottleneck edge of <math>T</math> if it's an edge with the largest weight. Note, multiple edges may have the same weight. The tree <math>T</math> 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 [[ECE_PhD_QE_CE_2013_Problem1.3|here]] to view student [[ECE_PhD_QE_CE_2013_Problem1.3|answers and discussions]]''' | ||
| + | ---- | ||
| + | '''Problem 4.''' | ||
| + | A project management firm needs to hire technical experts for a project with requires <math>s</math> different specialist. The project requires at least one expert in each of the specialties. The firm has received job application from <math>t</math> potential individuals. An applicant may have multiple areas of expertise. For each of the <math>s</math> specialties, there is some subset of the <math>t</math> applicants qualified in the required technical areas. For a given number <math>k<t</math>, is it possible to hire at most <math>k</math> applicants and have at least one expert qualified in each of the <math>s</math> specialties? Prove or disprove that this problem is NP-Complete. | ||
| + | :'''Click [[ECE_PhD_QE_CE_2013_Problem1.4|here]] to view student [[ECE_PhD_QE_CE_2013_Problem1.4|answers and discussions]]''' | ||
Latest revision as of 19:23, 21 August 2017
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
