Weekly Topic: Dynamic Programming

What is Dynamic Programming

• You divide a big problem into several smaller (overlapping) problems
• Difference to divide and conquer: subproblems are not disjoint

Calculating Fbonacci Series

• Definition: $F_0=1, F_1 = 1, F_n = F_{n-1} + F_{n-2} \text{ for } n\geq 2$

• If we use the definition to calculate the sequence, the time complexity will be $O(exp(n))$

  def fib(n) :
      if n == 0 or n == 1 :
          return 1
      else :
          return fib(n-1) + fib(n-2)
  

• “Memorization”: We can memorize the computed value to improve the time complexity : $O(n)$.

  def _fib(n) :
      if n == 0 or n == 1 :
          return 1
      else :
          return fib(n-1) + fib(n-2)
  checked = dict()
  def fib(n) :
      if n not in checked :
          checked[n] = _fib(n)
      return checked[n]
  

Longest Common Subsequences

• Example

  • The longest common subsequences of abcsequence and xsequenyce is sequence. (Note that the sequence does not need to be continuous; only the order matters)

• Algorithm

  • We can maintain a function with two parameter $f(i,j)$, the longest common subsequence if we only consider the first $i$ characters in the first string and the first $j$ characters in the second.

  • If we want to find the longest common subsequences of aaabbab and babaaba, then we need to find $f(6,6)$.

  • $f(6,6) = \max\{f(5,6), f(6,5)\}$ if the string at 6 is different, or $f(5,5) + 1$ if not

• Similar problem: Edit distance. We can see it as an generalization.

Bit Operations

• Example

  • 1 << 3 == 8, since 1000 in binary is 8. (bit-wise left-shifting)
  • 5|6 == 7, since the bit-wise OR of 101 and 110 is 111
  • Other example: XOR, NOT, etc.

• Why Bit-wise?

  • Can be used to represent a set / subset.
  • {apple, banana, orange}: 101 represents the subset {apple, orange}

Traveling Salesman

• Suppose you have three locations, given the distance between locations. You want to visit any single location (with arbitrary starting and ending location) while keeping the distance minimum.

• If we use a brute force algorithm, the time complexity will be $O(n!)$

• The infomation to track is where I am, and where I’ve been to (complement to where I need to go)

• We will maintain a table dp with $n$ rows of location and $2^n$ columns of bit masks, where dp[i][j] represents the minimum amount of distance we still need to travel.

• We already know that the last column is all 0, since we have visited all the locations. Then we can calculate the table backwards (ignoring invalid states). dp$[i][(111)_2]$ = 0

• (2, 100) can go to (1, 110) or (0, 101). What do I do? It is better to go to (0, 101) since the total cost is smaller.

• There are $n \cdot 2^n$ entries in the table, and $O(n)$ operations need to compute each entry. So the overall time complexity is $O(n^2\cdot2^n)$

• Note: If the set has more than 30 items, don’t use int. If the set has more than 60 items, don’t use long.