Suppose youre managing a consulting team of expert computer

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 arelow-stress (e.g., settingupaWebsiteforaclassatthelocalelementary 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 lowstress 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 hi 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 1, 2,...,n 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 i 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.

(a) Show that the following algorithm does not correctly solve this problem,bygiving an instance on which it does not return the correct answer.

To avoid problems with overflowing array bounds, we define hi=i=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 1, 2,...,n and h1,h2,...,hn and returns the value of an optimal plan.

(a)

Consider the given algorithm is as follows:

Why this error occurred is as explain below:

Initially declare hi = i = 0; to avoid the overflowing array bounds.

Suppose n= 4.

For iteration i = 0 to n

Here, we enter in the for loop for i = 0 then check the condition

If h_i+1 >l_i + l_i+1 then

Check h₁ > l₀ + l₁

Means, 5 > 10 +1 = 5 > 11, so condition is false go for the else part

Else

Output “choose a low stress job in week i+1” = 10

Continue with iteration i+1 = means i = 1

Endif

---------------------------------------------------------------------------------------------------------------

When i = 1

Now again go for “for” loop, now increment the i, here i = 2

Check the condition in for loop i is less than 4 means 2 < 4

Then check the condition in

If h_i+1 >l_i + l_i+1 then

Check h₂ > l₂ +l₃

Means, 50 > 11 condition is true

So, output “Choose a high stress job in week i” = 50

Continue with iteration i+2. Means 2 + 2 = 4

Endif

--------------------------------------------------------------------------------------------------------------

When i = 4

now, again for going to for loop then increment the i, so i = 5

Check the condition in for loop i < n = 5 < 4 so condition is false.

Thus, the above algorithm finds 0 + 10 + 50 = 60.

Hence, the answer is 60.

End

--------------------------------------------------------------------------------------------------------------

An instance the algorithm does not return correct output because:

In the given algorithm i is increment in the for loop, when

i = 3

then if condition is check for h_i+1 > l_i + l_i+1

thus, h₃+1 > l₃ + l₄

In the increment of for loop, it increments one extra every time which is not needy here, because increment is already in if and else condition according to the requirement.

Note: As the algorithm required modification, in the given algorithm for loop increments and decrements the value of i. But to get the optimal solution, need modification in for loop. Increment and decrement of i variable will be done only in if-else statement not in the for loop. This change in the code returns the optimal plan.

------------------------------------------------------------------------------------------------------------

(b)

Efficient algorithm is as follows:

For iteration i = 0 to n without increment the i is as shown below:

For iterations (i =0; i<n;)

If h_i+1 >l_i + l_i+1 then

Output “Choose no job in week i”

Output “Choose a high-stress job in week i+1”

Continue with iteration i+2

Else

Output “Choose a low-stress job in week i”

Continue with iteration i+1.

Endif

End

---------------------------------------------------------------------------------------------------------------

Explanation: Initially hi = i = 0 and n = 4 then go into the loop then go for if else condition, condition is false so output is display for low stress is10.

After that check for i = 1

Check the for-loop condition true then check ifelse condition

Here, condition is true so, output is display for high stress is 50.

Now, i = 3

Check the for condition after that check if condition which is false, then going for else part and display the low stress job is 10.

Now, i is 4 for loop condition false, terminate to out of the program.

The total result display of low and high stress job is: 0+10+50+10 =70

Thus, 70 is the optimum result.

Hence, in the modification of the for loop, the efficient algorithm got the optimum result.