a) Describe a brute-force algorithm for computing the maximum jump in value as well

as identifying the specic buy and sell dates for this maximum jump. What is its running

time?

b) We will determine a divide-and-conquer approach to nding the best dates for buying

and selling the stocks as well as the value of the maximum prot. Fill in an appropriate action

for step (d) (seriously):

(a) Split the array in half

(b) Find the maximum jump and buy/sell dates entirely in the left half

(c) Find the maximum jump and buy/sell dates entirely in the right half

(d) ???

(e) Choose the overall maximum jump

(f) Prot!

c. For your step (d) above, what specic pieces of information do you need?

d. Write your complete divide and conquer algorithm for the stock market problem.

e. Give a recurrence relation for your algorithm, and solve it for an asymptotic running time.

"Computer scientist makes S0.38 a day working from home find out how!!!" A popular pastime of computer scientists (especially academics) is fantasizing about how to use our knowledge to get rich playing the stock market. The first advice one receives about playing with stocks is "buy low, sell high". Easier said than done. Suppose we have a set S-(s1, s2, . . . , sn} of integer values where si represents the price of a stock on day i. Given this historic price data, we wish to (retrospectively) find the best time to buy and sell the stock, which should be a contiguous interval with the highest jump in price. Example: S = {2, 10, 3,0,4,0,0,1, 3,3,9,0, 21, 15, 17,4) has a maximum jump of 21 if purchased on day i - 4 and sold on day j- 13