Sample problems for tutorial #7

  1. Assume that the cost of multiplying an array A, with size x×y, and an array B, with size y×z, costs xyz, and results in an array of size x×z. Now consider the problem of multiplying the sequence of arrays A1A2A3…An. Each array Ai has size pi-1×pi. Although these multiplications could be performed in any order (due to associative property of the multiplication), the order in which we perform these multiplications can have an effect on the cost. For example, assume arrays A1A2A3 with sizes 10×100, 100×5, and 5×50. The multiplication (A1A2)A3 costs 10⋅100⋅5+10⋅5⋅50=7500, while the multiplication A1(A2A3) costs 100⋅5⋅50+10⋅100⋅50=75000.

    Using dynamic programming, given a set of sizes pi, find the best parenthesization of the matrices (i.e., find in which order the arrays should be multiplied). Hint: look at the last multiplication of the optimal result, and its operands as its subproblems.

  2. Let A be an array of n distinct integers. In this problem, we are interested in finding the longest increasing subsequence of A. That is, we want to find elements A[i1], A[i2], ... A[it] such that i1 < i2 < ... < it, A[i1] < A[i2] < ... < A[it], and t is as big as possible.

    For instance, if A = (1, 9, 17, 5, 8, 6, 4, 7, 12, 3), then both (1, 9, 17) and (1, 5, 6, 7, 12) are increasing subsequences. Note that the subsequence given by the greedy algorithm, that is the subsequence (1, 9, 17), is not the longest one.

    In order to find the longest increasing subsequence in the array, you can compute for each position i the length L[i] of the longest subsequence that ends with element A[i].