Exercise 5.8. Suppose you are given a set of n points P={(x1,y1),,(xn,yn)} in the plane. 1. Design and analyze an algorithm computing the maximum cardinality S of any subset SP where every pair of points in S is comparable. (Cf. exercise 1.7 on page 31.) 2. Design and analyze an algorithm computing the maximum cardinality S of any subset SP where every pair of points in S is incomparable. Sample solution. Problem. The following problem models the line breaking problem from section 5.4. The input consists of an array X[1..n] where each X[i] represents a word. We are also given a "loss function" loss (i,j) that takes as input two indices ij, and outputs a numerical value that represents the "badness" of X[i],,X[j] as a line of text. For simplicity we assume that loss (i,j) takes constant time to evaluate. The high-level goal is to partition X into contiguous subsequences X[1..i1],X[i1+1..i2],X[i2+1..i3],,X[ik1+1..n] minimizing the total loss: loss(1,i1)+loss(i1+1,i2)+loss(i3+1,i4)++loss(ik1+1,n). Here the number of contiguous subsequences (above, k ) is arbitrary. The problem is to compute the minimum loss over all such partitions of X. Solution. 1. Recursive spec / induction hypothesis. For i=1,,n+1, we define min-loss (i)= the minimum loss over all partitions of X[i..n]. (For i>n,X[i..n] indicates the empty sequence.) 2. Recursive implementation. min-loss (i) 1. If i>n then return 0 . 2. Otherwise return the minimum, over all j=i,i+1,,n, of loss(i,j)+minloss(j+1). 3. Solving the original problem. The solution to the problem is given by min-loss(1). 4. Mention "dynamic programming" or "caching". We apply dynamic programming to the recursive algorithm and cache the solutions to the subproblems. 5. Running time. For i=1,,n, loss (i) has a loop with at most n iterations, and each iteration takes constant time. So each subproblem takes O(n) time. Over all n subproblems, the algorithm takes O(n2) time in total. Sample solution. Problem. (Exercise 5.1 problem 1) Let A[1..n] be an array of integers. A sequence of numbers x1,,xk is (strictly) increasing if xii then return 1 . 2. Otherwise return the maximum of 1+LIS(j) over all indices j>i with A[j]>A[i]. 3. Solving the original problem. The maximum of LIS (i) over all i[n] gives the length of the longest increasing subsequence in A. 4. Running time with caching / dynamic programming. With dynamic programming, the running time is O(n2), where we have n subproblems each of which take O(n) time (to iterate over j>i, in steps (1) and (2)). Remark 5.1. We emphasize that the recursive spec essentially solved the entire problem. Remark 5.2. It is well known that there are faster algorithms but that is besides the point