1 Dynamic Programming: Take 1We examine problems that can be solved by dynamic programming, perhapsthe single most useful algorithmic design technique. Dynamic programmingcan be explained many ways. Rather than explain what a dynamic program-ming algorithm is, we explai n how one might develop one:1. Find a recursive algorithm for the problem. It often helps to first find arecursive algorithm to count the number of feasible solutions.2. Spot redundancy in the calculation3. Eliminate the redundancy. This can often be best accompli shed by per-forming the calculations b ottom up, instead of top down.2 Fibonacci Numbers and Binomial Coeffi-cientsSee section 1.2.2 and section 3.1 from the text.3 Longest Common S ubsequence ProblemThe input to this problem is two sequences A = a1, . . . , amand B = b1, . . . , bn.The problem i s to find the longest sequence that is a subsequence of bothA and B. For example, i f A = ccdedcdec and B = cdedcdec, then cddec issubsequence of length 5 of both sequences. Let T (i, j) be the length of thelongest comm on subsequence of a1, . . . , aiand b1, . . . , bj. Then one can seethat if ai= bjthen T (i, j) = T (i − 1, j − 1) + 1. Other wise, one can see thatT (i, j) = max(T (i, j − 1), T (i − 1, j)).Note that there are only nm possible subproblems since there are only mchoices for i and n choices for j. Hence, by treati ng the T (i, j)’s as arrayentries (instead of r ecursive calls) and updating the table in the appropriateway we can get the fol lowing O(n2) time algorithm.1For i=0 to m do T(i,0)=0For j=0 to n do T(0,j)=0For i=1 to m doFor j= 1 to n doif a(i) = b(j) then T(i,j)=T(i-1,j-1) + 1else T(i,j)= MAX( T(i, j-1), T(i-1, j))4 Computing Number of Binary Search Treesand Optimal Binary Search TreesSection 3.5 from the text.5 Chained Matrix MultiplicationSection 3.4 from the text.6 Maximum Weight Independent Set in a TreeThe input to this problem is a tree T with weights on the vertices. The goalis to find the independent set in T with maximum aggregate weight. Anindependent set is a collection of mutually nonadjacent vertices.Root the tree at an arbitrary node r, and process the t r ee in postorder.We generalize the induction hypothesis. Consider an arbitrary node v wi t hbranches to k descendants w1, w2, . . . , wk. We can c reate an independent setfor the subtree ro oted at v in e ssentially two ways depending on whet heror not we include v in the i ndependent set. If we decide not to include v,Consider an arbitrary root v with branches to k descendants w1, w2, . . . , wk.We can create an independent set for the subtree rooted at v in essentially2two ways depending on whether or not we include v in the inde pendent set.If we decide not to include v, we can combine any independent sets for thesubtrees rooted at w1, w2, . . . , wkto cr eate an independent set for the subtreerooted at v since there are no edges between the subtrees. On the other hand,if we do i nclude v in the independent set we can only use independent se t sfor the subtrees that do not include their respective root w1, w2, . . . , wk.Otherwise we would have both v and some wjin t he set and it would not bean indepe ndent set anymore.Therefore for each node v the algorithm computes the following information:1. big(v) = the maximum weight of an independent set for the subtreerooted at v, and2. bignotroot(v) = the maximum weight of an independent set for thesubtree rooted at v that does not include v.At node v, the algorithm first recursively computes big(wi) and bignotroot(wi)for each descendant subtree w1, w2, . . . , wk. It the n computes bignotroot(v)and big(v) using the fol lowing recurrence relations that correspond to thetwo cases identified above:bignotroot(v) =kXi=1big(wi)big(v) = max(bignotroot(v), weight(v) +kXi=1bignotroot(wi)If v is a leaf then bignotroot(v) = 0 and big(v) = weight(v).7 Longest Increasing Subseq uenceThe longest increasing subsequence (LIS) problem is defined as follows.INPUT: A sequence X = x1, . . . , xnof integersOUTPUT: The longest increasing subsequenc e of X. A sequence is increasingif each number in the sequence is larger than the previous number.3Let us try to develop a re cursive algorithm for this problem. Let LIS(k) bethe longest increasing subsequence of the first k integers in X. Consider thefollowing first stab at an induction hypothesis:Induction Hypothesis 1: We know how to compute LIS(k).Assume that we have computed LIS(k − 1), and we now want to computeLIS(k). The following sequence 1, 4, 2, 3 shows that we can’t just know anylongest sequence. Before we consider 3, we need to know the LIS 1, 2, notthe LIS 1, 4. The obvious solution i s to remember the LIS that ends in thesmallest number. Hence we change the definition of LIS as fol lows: LetLIS(k) be t he the longest increasing subsequence of the first k integers in Xthat ends in the smallest number.Induction Hypothesis 2: We know how to compute LIS(k).The following sequence 12, 13, 14, 1, 2, 4 shows that knowing the LIS thatends in the smallest number is not suffi cient information. Notice that inthis example the length of the LIS doesn’t change, but a new one is formedwith a smaller last number. The most obvious way to fix this problem is toremember the best (the one that ends in the smallest number) sequence oflength one less than the LIS. Let LIS2(k) be the the increasing subsequenceof the first k integers in X that has length one less than the length of LIS(k)and that ends in the smallest number.Induction Hypothesis 3: We know how to compute LIS(k), and LIS2(k).The following se quence 12, 13, 14, 15, 1, 2, 3 shows that there is not sufficientinductive information to compute LIS2(k). We need to know the se quenceof the first k−1 integers in X of length two shorter than LIS(k−1) that endsin the smallest number. One can see t hat eventually we have to inductivelyknow the sequence of each length that ends in the smalle st number.Hence, we define LIS(k, s) as the the smallest last number of any subsequenceof length s from among t he first k numbers of X. This then leads us to thefollowing algorithm.For k= 0 to n dofor s= 1 to n doLIS(k, s) = plus infinity4For k= 0 to n doLIS(k, 0) = minus infinityFor k= 1 to n dofor s= 1 to n doif ( LIS(k-1, s-1) < x(k) < LIS(k-1, s)then LIS(k,s)=x(k)else LIS(k,s)=LIS(k-1,s)This is an example of where when trying to compute something recursively/inductiveit is sometimes easier to compute more i nformation than you need. This