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 A₁A₂A₃…A_n. Each array A_i has size p_i-1×p_i. 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 A₁A₂A₃ with sizes 10×100, 100×5, and 5×50. The multiplication (A₁A₂)A₃ costs 10⋅100⋅5+10⋅5⋅50=7500, while the multiplication A₁(A₂A₃) costs 100⋅5⋅50+10⋅100⋅50=75000.

   Using dynamic programming, given a set of sizes p_i, 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].

   • Give a recurrence relation that expresses L[i] as a function of L[j] for values of j that are smaller than i. Hints: you need to consider the position of the previous element of the longest increasing subsequence.
   • Write pseudo-code for an algorithm that finds the longest increasing subsequence of an array with n elements.