Difference between revisions of "ECE PhD QE CE 2013 Problem1.2" - Rhea

Revision as of 17:38, 20 July 2017

Computer Engineering(CE)

Question 1: Algorithms

August 2013

Solution 1

This problem can be solved using dynamic programming. For each docks $$ x_i $$ , compute the revenue from $$ x_1 $$ to $$ x_i $$ , if $$ x_i $$ is selected, and the remaining docks $x_{i+1}$ to $$ x_n $$ , if $$ x_i $$ is not selected.

$$ R[i] $$ : denote the total revenue using only sites $x_1, \dots , x_i$ .

$$ L[i] $$ : denote $$ i $$ with the greatest value such that $$ x_i $$ is used for the solution in $$ R[i] $$ .

Initially, $$ L[<=0]=0 $$ , $$ R[<=0]=0 $$ , $x_0 = -\infty$ , $$ r_0=0 $$ . The pseudo code for dynamic programming is showing below. Note we use bottom up to fill up $$ R $$ and $$ L $$ .

pseudo code for dynamic programming

In the end of the program, $$ R[n] $$ will be the maximum revenue, and L[n], L[L[n]], ... will be the indices of locations to choose.

Back to QE CE question 2, August 2013

Back to ECE Qualifying Exams (QE) page

@@ Line 31: / Line 31: @@
 <gallery>
-File:dynamic.png|Caption1
+File:dynamic.png|pseudo code for dynamic programming
 </gallery>
-<math>
- \KwData{river stretch $L$, possible sites for docks:$x_1, x_2, x_3, ..., x_n$ , the possible revenue for each dock: $r_1, r_2, r_3, ..., r_n$ }
- \KwResult{The subset of docks that yields the greatest total revenue, with the restriction that the distance between each two docks are no less than 5 miles  }
- initialization: $L[<=0]=0$, $R[<=0]=0$, $x_0 = -\infty$, $r_0=0$\;
- \For {$i = 1$ to $n$}{
-  read $x_i$\;
-  \eIf{$|x_i-x_{L[i-1]}| >=5$}{
-   $R[i]=R[i-1]+r_i$\;
-   $L[i]=i$\;
-   }{
-   \For {$k=i-1$ down to $1$}{
-   		\If{$|k_k - x_i| >=5$}{
-   			\eIf{$R[k]+r_i > R[i-1]$}{
-   					$R[i]=R[k]+r_i$\;
-   					$L[i]=i$\;
-                    }
-   			{$R[i]=R[i-1]$\;
-  			 $L[i]=L[i-1]$\;
-             }
-             Break;
-   		}
-   }
-   }
- }
- \caption{Find the subset of docks with maximum revenue}
-</math>
 In the end of the program, <math>R[n]</math> will be the maximum revenue, and L[n], L[L[n]], ... will be the indices of locations to choose.

Difference between revisions of "ECE PhD QE CE 2013 Problem1.2" - Rhea

Revision as of 17:38, 20 July 2017

Solution 1

Alumni Liaison