Suppose you\'re managing a consulting team of expert computer hackers, and each

Question

Suppose you're managing a consulting team of expert computer hackers, and each week you have to choose a job for them to undertake. Now, as you can well imagine, the set of possible jobs is divided into those that are low-stress (e.g., setting up a Web site for a class at the local elementary school) and those that are high-stress (e.g., protecting the nation's most valuable secrets, or helping a desperate group of Cornell students finish a project that has something to do with compilers). The basic question, each week, is whether to take on a low-stress job or a high-stress job If you select a low-stress job for your team in week i, then you get a revenue of I> 0 dollars; if you select a high-stress job, you get a revenue of hi> 0 dollars. The catch, however, is that in order for the team to take on a high-stress job in week i, it's required that they do no job (of either type) in week i - 1; they need a full week of prep time to get ready for the crushing stress level On the other hand, it's okay for them to take a low-stress job in week i even if they have done a job (of either type) in week i -1 So, given a sequence of n weeks, a plan is specified by a choice of "low-stress," "high-stress," or none" for each of the n weeks, with the property that if "high-stress" is chosen for week i > 1, then "none" has to be chosen for week i - 1. (It's okay to choose a high-stress job in week 1.) The value of the plan is determined in the natural way: for each i, you add I to the value if you choose "low-stress in week I, and you add h to the value if you choose "high-stress" in week i. (You add 0 if you choose "none" in week i.) The problem. Given sets of values 11, 12,.in and h1, h2,..., hn, find a plan of maximum value Such a plan will be called optimal.) Example. Suppose n 4, and the values of li and hi are given by the following table. Then the plan of maximum value would be to choose "none" in week 1, a high-stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0+ 50+10 10 70 Week 1 Week 2 Week 3 Week 4 10 10 50 (a) Show that the following algorithm does not correctly solve this problem, by giving an instance on which it does not return the correct answer For iterations i = 1 to n If hi+i> &li; then Output "Choose no job in week " Output "Choose a high-stress job in week +1" Continue with iteration i+2 Else Output "Choose a low-stress job in veek " Continue with iteration i+1 Endif End To avoid problems with overflowing array bounds, we define h 0 when i > n. In your example, say what the correct answer is and also what the above algorithm finds (b) Give an efficient algorithm that takes values for 11,12.. in and h1, h2,...hn and returns the

Explanation / Answer

Algorithm to find optimal solution:

if number == 1
   then
   tempSolution= max(l[number],h[number])
else if number == 2 then
   tempSolution= max(optimalPlan(1, l, h)+ l[2], h[2])
else
   tempSolution= max(optimalPlan(number 1, l, h) + l[number], optimalPlan(number 2, l, h) + h[number])
end if
return Value

FindOptimalValue(number, l, h)

//Initialisation
for itterator = 1 ! number do
   tempSolution[itterator] = 0
end for

for itterator = 1 ! number do
   if itterator == 1 then
       tempSolution[itterator] max(l[itterator], h[itterator])
   else if itterator == 2 then
       tempSolution[itterator] max(tempSolution[1] + l[2], h[2])
   else
       tempSolution[itterator] max(tempSolution[itterator 1] + l[itterator], tempSolution[itterator 2] + h[itterator])
   end if
end for

return Value[number]
//Recurrsive function to find the optimal plan
OPtimalPlan(number, l, h, Value)

for itterator = 1 ! number do
   WeekVal[itterator]
end for
if tempSolution[number] l[number] = tempSolution[number 1] then
   WeekVal[number] ”Low stress”
   OPtimalPlan(number-1, l, h, Value)
else
   WeekVal[number] ”High stress”
   OPtimalPlan(number-2, l, h, Value)
end if
return WeekVal

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.