CS170 - Spring 2010 Section April 5th, 2010Dynamic Programming1. The LAF (League of Acrobatic Ferrets) is putting together a tricky routine where a chain of ferretswill swing from a bar K centimeters above the crowd (the first ferret holds the bar and the rest holdthe ankles of the ferret above it). The goal of the routine is to have the bottom ferret swing exactly 1centimeter from the crowd (i.e., the ferret chain should have total length K − 1), thereby creating asuperbly thrilling experience. Each ferret i out of the n members of LAF has a length liin centimeters.a. Design an dynamic programming algorithm to determine whether this stunt can be pulled off,and which ferrets should do it.b. Identify other DP problems that are equivalent to this problem (and don’t involve ferrets) andexplain briefly what the equivalence is.Solutiona. We solve a more general problem: you are given totals T1, . . . , Tkand sizes a1, . . . , ansuch thatPjTj=Piai:= T . We wish to output disjoint subsets S1, . . . , Skof [n] such thatPi∈Sjai= Tjfor all j. That is, we wish to partition the {ai} to make the sums {Tj}. Let L[t1, . . . , tk, i] representwhether or not we can partition a1, . . . , aito sum to the {tj}. Then we do the following:1. Initialize L[0, . . . , 0, 0] = true.2. Recursively (with caching!) computeL[t1, . . . , tk, i] = maxj:tj−ai≥0L[t1, . . . , tj−1, (tj− ai), tj+1, . . . , tk, i − 1]and record the j that worked (if any) in J[t1, . . . , tk, i], starting with L[T 1, . . . , Tk, n].3. If we return ’true’, we can retrace our steps for the solution.The runtime of this algorithm is Θ(nkΠTj), since there are up to nΠTjentries in our table, andwe loop over all k choices for each entry. Actually, it’s really only Πj<kTjsince if we use recursionthe total tkis determined in this setting by the first k − 1 sums.To solve the k-partition problem, set Ti= T /k for i ∈ [k] (where T =Paias above). To solvethe ferret problem, set T1= K − 1 and T2= T ?T1(here we use ai= liof course). The runtimesfor these cases come out to Θ(nTk−1) and Θ(nK), respectively.2. Correction of last section: You are given a sequence of n positive integers, a1, . . . , an, say (4, 5, 3, 2, 1).You are asked to choose among them a set of numbers no two of which are adjacent, so that the sumis as large as possible. In the present case, the correct answer is 4, 3, 1. You want to solve this problemby dynamic programming, with prefixes of the sequence as subproblems.(d) Suppose that each number aicomes with its reach risuch that, if aiis included in the sum, thenany other number between i − riand i + rimust be excluded. That is, the original problem wasthe ri= 1 case. Write the formula for S(i + 1) now.1SolutionWe define the subproblem S(i) to be the maximum sum achievable when using the elementsa1, . . . , ai, and including aiin the chosen set.The formula for this subproblem isS(i) = ai+ maxj<i s.t. max{ri,rj}<(i−j)S(j)After computing S(i) for i = 1, . . . , n we find the maximum S(i) and trace back from it’s solutionto find the subset of elements we