[Solved] CS3001301 Homework4

Problem 4.1. In the code of LOOKUP-CHAIN (checking the slides or p.388 from the textbook), if the first two lines of code, namely,

• if m[i, j] <
• return m[i, j]

are removed, what will happen?

Problem 4.2. Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?

Problem 4.3. Determine an LCS of 1, 0, 1, 0, 0, 1, 0, 1 and 0, 1, 0, 1, 1, 0, 1, 1, 0. Moreover, as discussed in our class, generalize the recursive formula used in the textbook Eq. 15.9 (p.393) to the following one:

0 if i 0 or j 0 ,

^{c[i, j]} max(c[i 1, j 1] (x_i y _j ),c[i, j 1],c[i 1, j]) if i, j 0 ,

(x_i == y_j is 1 if x_i = y_j or 0 if not), so that all LCSs of two sequences can be found. Use the recursive formula to find all the LCSs.

Problem 4.4. Give an O(n²)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. Discuss two cases separately: (1) simple increasing subsequences (2) strictly increasing subsequences. (2pts)

Problem 4.5. Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.