CS2223 Algorithms. D-2008     Exam 3 Solutions - April 28, 2008

Prof. Carolina Ruiz. Department of Computer Science. Worcester Polytechnic Institute.

Solutions by Prof. Ruiz

Problem I. Divide-and-Conquer (50 points)

Consider the following search problem: 
    Input:
    - An array A[1...n] of n positions, containing a sorted (in ascending order) sequence of 
       numbers. That is  A[1] ≤ A[2] ≤ ... &le A[n].
    - A value v.

    Output:
    - An index i such that v = A[i], OR
       the message "v is not in A" if v doesn't appear in A.
Consider the following divide-and-conquer solution to this problem. This solution is called binary search: Compare the element in the midpoint of the array A with v and eliminate half of the array from further consideration, until either v is found in A, or no elements in A remain under consideration. 
For example, let:

      -------------------------------------------------
 A = | 3 | 3 | 4 | 6 | 7 | 10 | 12 | 17 | 25 | 32 | 41 | 
      -------------------------------------------------
index: 1   2   3   4   5   6    7    8    9    10   11

 n = 11

Our Binary-Search(A,v,1,n) algorithm would work as follows:

Solve this problem following the steps below.

  1. (20 Points) Algorithm. Write detailed pseudo-code implementing this Binary-Search(A,v,1,n) divide-and-conquer, recursive solution described above. Explain your work

  2. (10 Points) Correctness. Prove that your pseudo-code is correct with respect to its input-output specification (that is, it always returns the right answer for the given input).

  3. Time Complexity. Analyze the time complexity of your algorithm.

Solution

See the solutions to HW5 Problem 4 (By Piotr Mardziel) of my offering of CS2223 in B term 2005.

Problem II. Dynamic Programming (50 points)

Consider the problem of finding the length of the longest strictly decreasing CONTIGUOUS 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 CONTIGUOUS subsequence in this sequence is: 3, and in the maximal such subsequence is: 
  5  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 CONTIGUOUS subsequence in S, and
  2. The longest (length = L) strictly decreasing CONTIGUOUS subsequence in S (or one of them, if more than one exists).

Solve this problem following the steps below.

  1. (30 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem.

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

    Solution

    Find-longest-strictly-decreasing-contiguous-subsequence(a1...an) {

  Array OPT[1...n] of integers 

  OPT[1]:=1                                                       O(1)

  For j := 2 to n do {                                          n*O(1)

      If a(j-1) > aj Then {                                     n*O(1)
                                                    _
          OPT[j]:= 1 + OPT[j-1]                      |
      }                                              |          n*O(1)
      Else {                                         |
          OPT[j]:= 1                                 |
      }                                             -
  }

  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 contiguous subsequence in
  a1...an is OPT[k]                                              O(1)

  Call Print-longest-strictly-decreasing-contiguous-subsequence with array OPT[0...n] and k 
                                                                 O(n)
}

Print-longest-strictly-decreasing-contiguous-subsequence(array OPT[0...n], index k) {

   If OPT(k) > 1 Then {
       Print-longest-strictly-decreasing-contiguous subsequence2(OPT[0...n], k-1) 
   }
   Print ak
}
    Note that runtime of Print-longest-strictly-decreasing-contiguous-subsequence is O(n) since the longest strictly increasing contiguous subsequence has at most n elements and this procedure is called recursively once for each element of the contiguous subsequence.

  3. (3 Points) Correctness of your Algorithm. Prove that your pseudo-code is correct with respect to the input-output specification above.
    (Hint: Since you already proved that your base case and recurrence are correct, the only thing that remains to be done is to prove that your pseudo-code faithfully implements your base case and recurrence.)

    Solution

    The algorithm starts by assigning 1 to OPT[1], correctly implementing the base case. Given a value of j between 2 and n in the For loop, note that the body of this loop assigns OPT[j-1]+1 to OPT[j], if aj < a(j-1); and assigns 1 to OPT[j], if aj ≥ a(j-1) as the recurrence requires.

  4. (7 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)). (You can do so above neatly next to each instruction of the algorithm, or below in the space provided.)

    Solution

    See the line by line runtime analysis above next to the algorithm. The total runtime is T(n)=O(n), where n is the length of the input sequence. Furthermore, note that in this case, T(n)=Θ(n) as the algorithm has to process each of the n element in the input sequence and so T(n)=&Omega(n).