WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS2223 Algorithms 
Homework 6 Solutions - D Term 2008

By Prof. Carolina Ruiz and Can Ozmen

------------------------------------------

  1. (50 Points) Problem 1. Consider the problem of finding the length of the longest (strictly) decreasing subsequence in a given sequence For instance, if the input sequence is:
      7  3  4  9  2  8  4  5  2  1  6  3  10
    
    then the length of the longest decreasing subsequence in this sequence is: 5, and in this case there are two such maximal subsequences:
      9  8  5  2  1 
    
      9  8  4  2  1 
    
    The input-output description of this problem is:

    Input: A sequence S = a1,a2,...,an (you can assume that the sequence is stored in an array) of length n, where each ai is a real number.

    Output: Your pseudo-code should print the following output:

    1. The length L of the longest strictly decreasing subsequence in S, and
    2. The longest (length = L) strictly decreasing subsequence in S (or one of them, if more than one exists).

    Solve this problem following the steps below.

    1. (12 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail how you plan to divide this problem into subproblems, in what order you plan to solve the subproblems so that the solutions to smaller subproblems are available to larger subproblems, and how you plan to use the solutions of these subproblems to produce a solution to the original problem.

      Solution

      Given a sequence a1...an, we divide the problem into the following n overlapping subproblems:
      SubPbm 1: Find the longest strictly decreasing subsequence in a1
                that ends in a1
      SubPbm 2: Find the longest strictly decreasing subsequence in a1 a2
                that ends in a2
      SubPbm 3: Find the longest strictly decreasing subsequence in a1 a2 a3
                that ends in a3
      ...
      SubPbm j: Find the longest strictly decreasing subsequence in a1 a2 a3 ... aj
                that ends in aj
      ...
      SubPbm n: Find the longest strictly decreasing subsequence in a1 a2 a3 ... aj... an
                that ends in an
      
      We will use an array OPT[0..n] to store the solution to each of these subproblems:

      P[j] = Length of the longest strictly decreasing subsequence in a1...aj that ends in aj.

      • Boundary condition: P[0]=0

      • Recurrence: We will solve problem j using the solutions to problems 0,...,j-1 as follows: The longest subsequence in in a1 a2 a3 ... aj that ends in aj would result from concatenating the longest subsequence in a1 a2 a3 ... a(j-1) that ends in an element that is strictly greater than aj. In other words:

        OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) As an illustration, note that for the given example,

        Sequence:  7  3  4  9  2  8  4  5  2  1  6  3  10 
        Index:     1  2  3  4  5  6  7  8  9 10 11 12  13 
        we have:
        
        OPT[0]=0
        OPT[1]=1 the longest strictly decreasing subsequence in 7 
                 ending in 7 has length 1 (namely 7)
        OPT[2]=2 the longest strictly decreasing subsequence in 7 3 
                 ending in 3 has length 2 (namely 7 3)
        OPT[3]=2 the longest strictly decreasing subsequence in 7 3 4 
                 ending in 4 has length 2 (namely 7 4)
        OPT[4]=1 the longest strictly decreasing subsequence in 7 3 4 9
                 ending in 9 has length 1 (namely 9)
        OPT[5]=3 the longest strictly decreasing subsequence in 7 3 4 9 2
                 ending in 2 has length 3 (namely 7 3 2 or 7 4 2)
        OPT[6]=2 the longest strictly decreasing subsequence in 7 3 4 9 2 8
                 ending in 8 has length 2 (namely 9 8)
        OPT[7]=3 the longest strictly decreasing subsequence in 7 3 4 9 2 8 4
                 ending in 4 has length 3 (namely 9 8 4)
        
        and so on.  Note for instance that 
        
        OPT[7] = 1 + (max over all i < 7 with ai > 4 {OPT[i]})
               = 1 + (max {OPT[1],OPT[4],OPT[6]})
               = 1 + (max {1,1,2})
               = 1 + 2 = 3
        

      • Proof of Correctness of this Recurrence: Let's prove that this recurrence is correct. As expected, we'll prove it by induction.
        1. Base Case: For j=0: OPT[0]=0 correctly as the lenght of the longest strictly decreasing subsequence of an empty is 0.
        2. Induction Step: Let 0 ≤ j ≤ n.
          Induction Hypothesis: Assume that for each i < j we have that P[i] correctly contains the length of the longest strictly decreasing subsequence in a1...ai that ends in ai.
          Now let's prove that this property holds for j too.
          OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]})  by definition of OPT[j]
          
                 = 1 + (max over all i < j with ai > aj {length of the longest strictly decreasing
                                                         subsequence in a1...ai that ends in ai} 
                                                         by the induction hypothesis
          
                 = length of the longest subsequence in a1...aj-1 that ends in a number greater
                   than aj and since we can concatenate aj to this subsequence keeping it
                   strictly decreasing, then we add 1 to obtain the length of the resulting
                   subsequence
          
                 = length of the longest strictly decreasing subsequence in a1...aj 
                   that ends in aj 
          
          Hence, the property holds for j too. 
          
      • Solution to Full Problem: Once that all the P[j]'s are computed for 1 ≤ j ≤ n, the solution to the full problem (the lenght of the longest strictly decreasing subsequence in S) is equal to the maximum value in this array:

        max over all i, 1 ≤ i ≤ n {OPT[i]}

        In the example above, the maximum value in OPT[0...n] will be OPT[10]=5 as 9 8 5 2 1 (or equivalently, 9 8 5 2 1) is the longest strictly decreasing subsequence.

      • Longest Subsequence: We can optionally use an additional array to keep track of the longest subsequence (not just of its length): PREV[0...n] where:

        PREV[j] = Index of the element in a1...a(j-1) that comes right before aj in the longest strictly decreasing subsequence in a1...aj that ends in aj.

        For instance, PREV[7]=6 in the example above. PREV[5]=2 if the subsequence 7 3 2 is chosen over 7 4 2 or PREV[5]=3 if vice versa.

        We could find the optimal subsequence without keeping the PREV array as it will be shown in the algorithm below.


    2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

      Solution

      Find-longest-strictly-decreasing-subsequence(a1...an) {
      
        Array OPT[0...n] of integers 
        Array PREV[0...n] of integers 
      
        OPT[0]:=0                                                       O(1)
        PREV[0]:=0                                                      O(1)
      
        For j := 1 to n do {                                          n*O(1)
      
            // here it would be enough to say: 
               OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) 
               but below we provide a detailed implementation of this recurrence //
            
            max-so-far := 0                                           n*O(1)
            best-prev-so-far := 0                                     n*O(1)
            For i := 1 to j-1 do {                                    n2*O(1)
                If ai > aj Then {                                     n2*O(1)
                    If OPT[i] > max-so-far Then {                     n2*O(1)
                       max-so-far := OPT[i]                           n2*O(1)
                       best-prev-so-far := i                          n2*O(1)
                    }
                }
            }
            OPT[j]:= 1 + max-so-far                                   n*O(1)
            PREV[j] := best-prev-so-far                               n*O(1)
           
           //Alternatively, we could define a graph in which each j is a node
             and there is an edge from j to i IFF i < j AND ai > aj. Hence,
             OPT[j] = 1 + (max over all i < j with ai > aj {OPT[i]}) can be
             easily calculated as:
             OPT[j] = 1 + (max over all i such that (j,i) exists {OPT[i]}) 
           
        }
      
        Let k be the index of the maximum value in the array OPT[1...n]
        (or such one index if the maximum value appears more than once in the array)
                                                                       O(n)
      
        Print that the length of the longest strictly decreasing subsequence in
        a1...an is OPT[k]                                              O(1)
      
        Call Print-longest-strictly-decreasing-subsequence1 with array PREV[0...n] and k                                            
                                                                       O(n)
      
        or alternatively
        Call Print-longest-strictly-decreasing-subsequence2 with array OPT[0...n] and k 
                                                                       O(n)
      }
      
      Print-longest-strictly-decreasing-subsequence1(array PREV[0...n], index k) {
      
         If k != 0 Then {
             Print-longest-strictly-decreasing-subsequence1(PREV[0...n], PREV[k]) 
             Print ak
         }
      }
            
      
      or alternatively:
      
      Print-longest-strictly-decreasing-subsequence2(array OPT[0...n], index k) {
      
         If k != 0 Then {
      
            // here it would be enough to say: 
               let i be the index that gives us the maximum in: 
               OPT[k] = 1 + (max over all i < k with ai > ak {OPT[i]}) 
               but below we provide a detailed implementation of this statement //
            
            best-prev-so-far := 0
            For i := 1 to k-1 do {
                If ai > ak Then {
                    If (OPT[i] + 1) = OPT[k] Then {
                       best-prev-so-far := i
                    }
                }
            }
      
            Print-longest-strictly-decreasing-subsequence2(OPT[0...n], best-prev-so-far) 
            Print ak
         }
      }
      
      
      Note that Print-longest-strictly-decreasing-subsequence1 and Print-longest-strictly-decreasing-subsequence2 are both O(n) since the longest strictly increasing subsequence has at most n elements and these procedures are called recursively once for each element of the subsequence.

    3. (13 Points) Correctness. Prove in detail that your algorithm is correct with respect to the input-output specification above.

      Solution

      We already proved by induction above that our recurrence is correct. Hence the only thing that remains to be proven is that our algorithm faithfully implements the recurrence. Given a j between 1 and n, note that the inner For loop ranges over the i's that are less than j, and for those for which ai > aj, it selects the one with maximum OPT[i], as the recurrence requires.

    4. (13 Points) Time Complexity. Analyze in detail the runtime T(n) of your algorithm. Remember to explicitly state what the size of the input is. Find the tightest asymptotic upper bound g(n) for T(n) you can, so that T(n) = O(g(n)).

      Solution

      See the line by line runtime analysis above next to the algorithm. The total runtime is T(n)=O(n2), where n is the length of the input sequence.

  2. (50 Points) Problem 2. Consider the problem of finding paths in a grid. For that, imagine that you're in a city where avenues (vertical lines) and streets (horizontal lines) form a perfect grid. Imagine that you're located at the origin of the grid, that is at the intersection of avenue 0 and street 0: (0,0), which is the south-west corner of the city. Given a pair (n,m) denoting the intersection of avenue n with street m, you need to determine how many different paths exist between your current position (0,0) and (n,m).

    A path from (0,0) to (n,m) is a sequence (0,0)=(a0,b0),(a1,b1),(a2,b2),...,(ak,bk)=(n,m) satisfying the following constraints:

    1. You can only walk one block to the east (right) or one block to the north (up) at a time, and only on the avenues and on the streets (no diagonal moves allowed). For instance, a possible path to go from (0,0) to (2,3) is: (0,0), (0,1), (1,1), (1,2), (1,3), (2,3). The sequence (0,0), (1,1), (2,2), (2,3) is NOT a valid path, because it "cuts corners", and the sequence (0,0),(2,0),(2,3) is NOT a valid path because it skips intersections. Hence, for every i < k in the path:

      • a(i+1) = ai + 1 and b(i+1) = bi, (walking one block east) or
      • a(i+1) = ai and b(i+1) = bi + 1 (walking one block north).

    2. You cannot walk east of avenue n or north of street m. In other words, ai ≤ n and bi ≤ m, for all ai, bi with i ≤ k.

    Assume that there is exactly one path to go from a grid position to itself. The input-output description of this problem is:

    Input: Two integers n and m, with n ≥ 0, m ≥ 0.

    Output: The total number of different paths on the grid from (0,0) to (n,m) satisfying the two constraints above.

    Solve this problem following the steps below.

    1. (12 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail how you plan to divide this problem into subproblems, in what order you plan to solve the subproblems so that the solutions to smaller subproblems are available to larger subproblems, and how you plan to use the solutions of these subproblems to produce a solution to the original problem.

      Solution

      First observe that Paths(n,m) = the total number of paths between (0,0) and (n,m) satisfying the two given constraints can be defined recursively as follows:
      Paths(n,m) = {
                     1, if n=0 or m=0,
                     Paths(n-1,m) + Paths(n,m-1), otherwise
                   }
      
      The subproblems to solve in this case is the number of paths to the two points immediately to the left and immediately to the bottom of the current grid point. The base case here is the first row and column where we know there can exist only one path as going down and left are not permitted. The correctness of this recursive definition is proved in a following subsection.
                                Paths(i,j)
           --------------------------------------------------
        n | 1  |n+1 |    |    |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
      n-1 | 1  | n  |    |    |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
      ... | 1  |    |    |    |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
        i | 1  |i+1 |    |    |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
      ... | 1  |    |    |    |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
        3 | 1  | 4  | 10 | 20 |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
        2 | 1  | 3  | 6  | 10 |  ...  |    |  ...  |    |    |      
           --------------------------------------------------
        1 | 1  | 2  | 3  | 4  |  ...  |j+1 |  ...  | m  |m+1 |      
           --------------------------------------------------
        0 | 1  | 1  | 1  | 1  |  ...  | 1  |  ...  | 1  | 1  |
           --------------------------------------------------
            0    1    2    3     ...    j     ...   m-1   m
      

    2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

      Solution

      Number-of-path-in-the-grid(n,m) {
      
      2D array Paths[0...n,0...m] of integers
      
        // Initialize all elements in the first column as 1 //
      
        For i := 0 to n do {  
            Paths[i,0] := 1
        }
      
        // Initialize all elements in the first row as 1 //
      
        For j := 0 to m do {
            Paths[0,j] := 1
        }
                
        // Use the recurrence for all other i's and j's in the matrix//
      
        For i := 1 to n do {
            For j := 1 to m do {
                Paths[i,j] := Paths[i-1,j] + Paths[i,j-1]
            }
        }
      
        return Paths[n,m]
      
      }
      
      Note that the order in which we are traversing the matrix guarantees that Paths[i-1,j] and Paths[i,j-1] already contain their correct values when they are used to calculate Paths[i,j].

    3. (13 Points) Correctness. Prove in detail that your algorithm is correct with respect to the input-output specification above.

      Solution

      Proof by induction on (k,l)
      • Base Cases (k=0 or l=0): We can observe that the first row and column of the matrix holds correct values as there is always only one path to points on the grid at these locations, either straight up or straight right from (0,0).
      • Inductive Step:
        Inductive hypothesis (for any integer k,l): Assume that number of paths to (i,j) is correct for all i ≤ k and j ≤ l.
        Prove for (k+1,l+1): Given the constraints, there are only two ways to reach point (k+1,l+1), either from (k,l+1) or from (k+1,l). From (k,l+1) to (k+1,l+1) there is only one way, right, and the paths are the ones to (k,l+1) plus the point (k+1,l+1) therefore the number of paths stays the same. Similarly for the case of coming up from (k+1,l). Finally we observe that the paths from these two points are distinct because their last points are different. Thus the total number of paths to (k+1,l+1) is the sum of the number of paths to (k,l+1) and (k+1,l) and the algorithm is correct.

    4. (13 Points) Time Complexity. Analyze in detail the runtime T(n,m) of your algorithm. Remember to explicitly state what the size of the input is. Find the tightest asymptotic upper bound g(n,m) for T(n,m) you can, so that T(n,m) = O(g(n,m)).

      Solution

      Initializing the first column takes O(n) time, initializing the first row takes O(m) time, and calculating the remaining entries of the matrix takes O(nxm) time, as each position on the grid must be calculated one by one until (m,n) is reached. Therefore the runtime of the whole algorithms is O(m*n).