Line 36: Line 36:
  
 
<math>
 
<math>
\begin{algorithm}[H]
 
 
  \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$ }
 
  \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  }
 
  \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  }
Line 62: Line 61:
 
  }
 
  }
 
  \caption{Find the subset of docks with maximum revenue}
 
  \caption{Find the subset of docks with maximum revenue}
\end{algorithm}
 
 
</math>
 
</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.
 
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.

Revision as of 18:36, 20 July 2017


ECE Ph.D. Qualifying Exam

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


$ \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} $ 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

Alumni Liaison

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

Dr. Paul Garrett