| Line 30: | Line 30: | ||
Find the asymptotic run time complexity of this algorithm. Give detail of your computation. | Find the asymptotic run time complexity of this algorithm. Give detail of your computation. | ||
| − | (b) Assume functions <math>f</math> and <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>. |
| + | |||
| + | ---- | ||
| + | '''Part 2.''' | ||
| + | |||
| + | Suppose your company develops and manage construction of boat launching docks along a downstream stretch of 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 < \dot{...} < x_n</math>, each in the interval <math>\left[ 0,L\right[</math>, specifying their position in miles measured from the northern end of this stretch of Wabash. 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 5 miles less 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 location </math>x_1</math> and <math>x_3</math> to achieve 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. | ||
Revision as of 16:31, 20 July 2017
Computer Engineering (CE)
Question 1: Algorithms
August 2013
Question
Part 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 detail 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)}) $.
Part 2.
Suppose your company develops and manage construction of boat launching docks along a downstream stretch of 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 < \dot{...} < x_n $, each in the interval $ \left[ 0,L\right[ $, specifying their position in miles measured from the northern end of this stretch of Wabash. 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 5 miles less 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 location </math>x_1</math> and $ x_3 $ to achieve 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.
