# 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