Dynamic Programming

Question 1

LongestIncreasingSubsequence (Length)

Answer 1

Input: S = {x1,x2,…xn}
Output: L, the length of the LIS of S
Constraints: L(i) includes xi

LIS:
   L := 0
   for each xi in S:
      m := 1
      for each j in [1,i):
           if xi > xj and L(j) >= m then
              m = L(j)
           end if
      end for
      L(i) = m + 1
  end for
  return max(L)
end

Running time: O(n^2), Space: O(n)

Question 2

LongestCommonSubsequence (Length)

Answer 2

Input: X = {x1, x2, .., xn}, a series of letters/numbers
Input: Y = {y1, y2, .., ym}, another series of letters/numbers
Output: L, length of the longest common subsequence of X and Y.

LCS:
    L(n,m) = {0}  //empty list
    for i from 1 to n:
       for j from 1 to m:
           if x(i) == y(j):
              L(i,j) = 1 + L(i-1, j-1)
           else
              L(i,j) = max[ L(i, j-1), L(i-1, j)]
           end if
       end for
    end for
    return L(n,m)
end

Running time: O(n^2)

Question 3

Properties/When to use Longest Increasing Subsequence?

Answer 3

• problem has only a single array
• problem comparing to itself
• problem looks back 1 element at a time

Question 4

Properties/When to use Longest Common Subsequence?

Answer 4

• problem comparing between two arrays
• problem is looking for something in common
• normally a 2D table

Question 5

Properties/When to use Knapsack?

Answer 5

• follow a formulation where selection is the optimal objects from a list that fits some criteria.
• values have a weight associated with them.

Question 6

Knapsack (no repetition)

Answer 6

Input: W = {w1, w2, …, wn} List of object weights
Input: V = {v1, v2, …, vn} List of object values
Input: B, the capacity
Output: K, collection of objects resulting in max total value without exceeding B.

Knapsack:
    K(n+1, B+1) = 0
    for i from 1 to n:
         for b from 1 to B:
             x=K(i-1,b)
             if wi <= b:
                 K(i,b) = max[ x, vi+K(i-1, b-wi)]
             else:
                 k(i,b) = x
              end if
         end for
    end for
    return K(n,B)
end

Running time: O(nB)

Question 7

Knapsack (with repetition)

Answer 7

Input: W = {w1, w2, …, wn} List of object weights
Input: V = {v1, v2, …, vn} List of object values
Input: B, the capacity
Output: K, collection of objects (possibly with duplicates) resulting in max total value without exceeding B.

Knapsack:
    K = 0
    for b from 1 to B:
        K(b) = 0
        for w in W: 
             if wi <= b:
                 K(b) = max[ K(b), vi+K(b-wi)]
         end for
    end for
    return K(B)
end

Running time: O(nB)

Question 8

Chain Matrix Multiply

Answer 8

Input: [m1 ,m2, … mn] Set of sizes corresponding to matrix dimensions
Output: Lowest-cost matrix multiplication possible

Chain Multiply:
   M(n,m) = null
   for i in 1 to n:
       M(i, i) = 0
   end for

   for d in 1 to (n-1):
      for i in 1 to (n-d):
         j = i + d
        M(i,j) = inf
        for k in i to (j-1):
           current = M(i, k) + M(k+1, j) + m(i-1)*mk*mj
           if current < M(i,j)
               M(i,j) = current
           end if
        end for
     end for
  end for
  return M(1,n)
end

Running time: O(n^3)

Question 9

Steps to solve a Dynamic Programming Problem

Answer 9

1. Define the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is…
3. Define a Recurrence relationship - Based on a subproblem to the main problem. (hint: use a prefix of the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time Function notation here => T(n) = T(n/2) + 1…

Question 10

In Bellman-Ford, how would you detect a negative weight cycle?

Answer 10

Check if iteration i (since bellman-ford does i -1 iteration) decreases a previous row result.

Question 11

In Floyd-Warshall, how would you detect a negative weight cycle?

Answer 11

Check if the diagonal values have any negative values. This is because if we the length to and from the same node should be 0, not negative!

Question 12

The main difference between Bellman-Ford and Floyd-Warshall?

Answer 12

Run time difference (mN^2 vs n^3) and Bellman-Ford computes the shortest path between two nodes, where Floyd-warshall does them all.

Question 13

what takes more time, longest increasing subsequence or longest common subsequence?

Answer 13

longest increasing subsequence

Question 14

LIS Variations: O(n) lookback

Answer 14

• need to check all previous elements
• need to check all previous elements < or > some requirement
• Results in O(n^2)

Question 15

LIST variations: O(1) lookback

Answer 15

• need to check 1 element back.
• need to check constant # elements back.
• restriction moves forward with 1
• if you need to care the max, sum, count, etc. forward (this means you only compare with i-1)
• Results in O(n)

Question 16

LCS variations: substring

Answer 16

• matches need to be consecutive.
• add 1 (or other #) if comparisons succeeds.
• 1+T(i-1,j-1)
• reset to 0 when comparison fails.
• solution is max of T()
• results in O(mn) or O(n^2) (depend if arrays are same size.)

Question 17

LCS variations: subsequence

Answer 17

• comparision skips mismatches
• add 1 (or other #) if comparisons succeeds.
• 1 + T(i-1,j-1)
• max of either side if comparison fails.
• max{T(i,j-i), T(i-1,j)}
• solution is final results T(n,m) or T(n,n)
• results in O(mn) or O(n^2) (depend if arrays are same size.)

Question 18

Edit Distance

Answer 18

• considered 3rd variation of LCS

- compares 2 arrays

Question 19

Recurrence relation d>log_b a

Answer 19

O(n^d)

Question 20

Recurrence relation d=log_b a

Answer 20

O(n^d log n)

Question 21

Recurrence relation d

Answer 21

O(n^(log_b a))

Question 22

Master Theorem

Answer 22

T(N) = aT(n/b) + O(n^d)

Question 23

Multiplication (a+bi)(c+di)

Answer 23

(a+b)(c+d) - ac - bd

Question 24

T(n) generalized

Answer 24

T(n) = work due to subproblem proliferation + work done to merge subproblem results
T(n) = aT(n/b) + O(n^d)

Question 25

i, and powers of i

Answer 25

``` i=root(-1) i^2 = -1 i^3 = -i i^4 = 1 i^5 = i i^6=-1 ```