Line 30: Line 30:
 
The pseudo code for dynamic programming is showing below. Note we use bottom up to fill up <math>R</math> and <math>L</math>.
 
The pseudo code for dynamic programming is showing below. Note we use bottom up to fill up <math>R</math> and <math>L</math>.
  
[[File:Dynamic.png|800px|Pseudo code for dynamic programming]]
+
[[File:Dynamic.png|600px|Pseudo code for dynamic programming]]
  
 
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 19:08, 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 $.

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

Alumni Liaison

Have a piece of advice for Purdue students? Share it through Rhea!

Alumni Liaison