Dynamic Programming: Examples

Bart Massey

Pseudocode and Midterm 2

  • Given: Array a of n positive integers

  • Find: Rearrangement of a such that

    1. All odd numbers are in increasing order

    2. All even numbers are in increasing order

    3. Every pair of even numbers of the form n, n + 2 is separated by an odd number

    Fail otherwise

  • Part A: Find an O(n2) time O(1) space algorithm

    • Strategy: Use modified selection sort to put consecutive elements in place; try to place the even elements first, subject to the constraints

        for i in 0..n-1
            j <- index of the minimum even element in a[i]..a[n-1]
            if j exists and (i = 0 or a[i-1] =/= a[j] - 2)
                 swap a[i] with a[j]
                 continue
            j <- index of the minimum odd element in a[i]..a[n-1]
            if j exists
                 swap a[i] with a[j]
                 continue
            fail
      
  • Part B: Find an O(n lg n) time O(n) space algorithm

    • Strategy: Sort the evens and odds separately, then take from them one at a time in the right order.

          a_odd <- copy of odd elements of a
          a_even <- copy of even elements of a
          sort a_odd and a_even
          for i in 0..n-1
              if a_even is nonempty
                  candidate <- first element in a_even
                  if (i = 0 or a[i - 1] =/= candidate - 2)
                      a[i] <- candidate
                      delete candidate from a_even
                      continue
              if a_odd is nonempty
                  a[i] <- first element in a_even
                  delete first element from a_even
                  continue
              fail
      

Longest Increasing Subsequence

  • Sequence: A sequence s can be thought of as a function from index to element, which can in turn be thought of as a set of tuples.

      s = [5, 9, 7, 4]
      {(0, 5), (1, 9), (2, 7), (3, 4)}
    
  • Subsequence: A subsequence t of s is a subset of the map of s, with the indices compressed to be sequential.

      t = {(0, 9), (1, 4)}
      [9, 4]
    
  • Given: Sequence s of integers

  • Find: Longest subsequence t of s such that for all i in 1..|t|-1 we have t[i-1] < t[i]

  • Strategy: Recursion / induction on prefix of s. Specifically, find the LIS ending at s[i] by finding an LIS of s[0]..s[i-1] that ends with a number smaller than s[i]

  • Dynamic programming reduces complexity to O(n2) time O(n) space

  • O(n lg n) algorithm is https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

    The basic idea is to keep track of a bunch of sequences sequences, and binary search on the current value to figure out which can be extended and which must be dropped.

Integer Partition

  • Given: Sequence s of positive integers. Partition count k.

  • Find: Splitpoints p[1]..p[k-1] minimizing

      max[i=1..k] sum(s[p[i-1]]..s[p[i] - 1])
    

    where p[0] = 0, p[k] = |s| + 1

  • Strategy: For each possible first partition, find the best remaining k-1 partitions and their maximum sum.

  • Dynamic Programming: Remember the partition values and sums for each starting point and each k

Other Problems from Skiena

  • Morphing

  • Parsing

  • Triangulation

  • Unification

  • Bar Codes

Optimality Principle

  • Partial solution can be extended in some pre-determined order

  • Extension is function only of some metric of previous partial solutions