CSC373 Fall’20 Assignment 2 Solutions
Q1 [20 Points] Fruit Frenzy, Revisited
In the dilemma that you helped Dinosaur Bobby solve in Assignment 1, there were n gardens. Each garden i was described by two integers: ei, the easiness of reaching garden i, and qi, the number of fruits in garden i. Garden i was called a smarter choice than garden j if ei > ej and qi > qj .
Bobby is now employed at a circus and wants your help again in selecting a smart garden. But a couple of things are different this time around.
1. First, Bobby wants to find a sequence of gardens (i1, i2, . . . , ik) such that each garden ir+1 is a smarter choice than the previous garden ir; such a sequence is called a chain. Essentially, Bobby wants to impress his manager by saying “Look, I could’ve selected garden i1. But I found a smarter choice i2. And then an even smarter choice i3. . . And then an even smarter choice ik. That’s why I picked garden ik.”
2. Each garden i additionally has a non-negative weight wi. And Bobby wants you to find a chain with the highest total weight.
Design a dynamic programming algorithm to help Bobby.
(a) [5 Points] Define an array or arrays storing the necessary information from subproblems. Clearly define what each entry means, and how you would compute the final answer given the array entries.
(b) [5 Points] Write a Bellman equation and briefly justify its correctness.
(c) [5 Points] Describe a bottom-up implementation to compute the array entries.
(d) [5 Points] Analyze the worst-case running time and space complexity of your algorithm.
Solution to Q1
(a) Let us define the following array:
• X[i] = maximum weight of any chain ending at garden i
Given the array entries, the desired solution can be computed by following the maximum weight entries using the algorithm on the next page.
Justification: The Bellman equation utilizes the following optimal substructure property: a max- imum weight chain ending at garden i is formed by picking a maximum weight chain among all chains ending at some garden j with ej < ei and qj < qi, and adding garden i to it. The first iteration of the while loop simply picks a garden i with the highest X[i], as intended. Every future iteration, in Line 8, finds a garden which can be added to the chain before garden i and, among such gardens, has the highest X-value, as intended.
1
Algorithm 1: FindChain
1 2 3 4 5 6 7 8 9
10 11 12
Initialize an empty chain C
elast ←∞,qlast ←∞ // ei and qi of last garden i added to the chain while true do
S←setofgardensisuchthatei