Question:

   

Frank the frog dabbles in prognostications. He has projected the number of flies that will be around his lilypad loft on each of the following n days. Thus, d days from now, there will be fa flies around his lilypad. Frank also is quite sleepy, and likes to rest for days at a time. The more he rests, the hungrier he gets. If Frank has rested for r days, he has the appetite for a, flies. Once he wakes on a day he eats and then his appetite resets and returns to 0. Recall, the more Frank rests, the hungrier he gets, so a; j: Return HUNGRYFROG(fi fn-j). (@j) Intuitively, the algorithm figures out how many days of rest j are needed to eat all of the flies on the last day. It wakes Frank up on the last day, and then accounts for the j days of rest needed to work up his appetite to eat as much as possible on the last day, and recursively considers the best solution for first n -j days. Explain why your instance causes the greedy algorithm to return the wrong answer. Solution: (b) Let OPT(j) be the maximum number of flies Frank can eat over the first days. Give a recurrence to compute OPT(j) from OPT(1)..... OPT(j-1). Give a few sentences justifying why your recurrence is correct. Solution: (c) Using your recurrence, design a dynamic programming algorithm to output the optimal set of days for Frank to wake up. You may use either a top-down or bottom-up approach.