hw3 dynamic programming

Algorithms › 6.006 algorithms

key word: state, dependency

ps8

  1. Problem 1: reduce state? We can easily think of at lease one state in this case which is the number of peppers Peter can pick.

  2. (Rethink dp problem in a week)

    • Problem 1.1: in which way sorting affect the results?

      -> data structures/algorithms

    • problem 2: how to make it acyclic?

      in building block problem, the key problem is pre-processing part.

  3. princess plum: define subproblems?

    a bottom-up way:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def count_paths(F):
        '''
        Input:  F | size-n direct access array of size-n direct access arrays
                  | each F[i][j] is either 't', 'm', or 'x'
                  | for tree, mushroom, empty respectively
        Output: m | the number of distinct optimal paths in F
                  | starting from (0,0) and ending at (n-1,n-1)
        '''
        n = len(F)
        K = [[-float('inf')] * (n+1) for _ in range(n + 1)]
        X = [[0] * (n + 1) for _ in range(n+1)]
        for i in range(n + 1):
            for j in range(n + 1):
                if F[i - 1][j - 1] == 't':
                    continue
                if i == 1 and j == 1:
                    K[1][1], X[1][1] = 0, 1
                    continue
                if F[i - 1][ j - 1] == 'm': m = 1
                else: m = 0
                K[i][j] = max(K[i-1][j], K[i][j-1]) + m
                if K[i][j-1] + m == K[i][j]: X[i][j] += X[i][j-1]
                if K[i-1][j] + m == K[i][j]: X[i][j] += X[i-1][j]
        return X[n][n]

ps9

reminder

Techniques:

  1. store parent pointers to track info.

recitation

Problem: state, dependency?

  1. longest increasing subsequence

Iterative / recursive

a Fibonaccci example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def fib(n):
    a0 = 0
    a1 = 1
    if n == 0:
    	print(a0)
    if n == 1:
        print(a1)
    else:
        for i in range(2, n+1):
            sum = a0 + a1
            a0 = a1
            a1 = sum
        print(sum)
        
def fib(n):
  # without memoization recursive version
  if n == 0:
    return 0
  if n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

Partitions

  1. subset sum: solve with dp in O(nS) time

Complexity

problem: how does running time compare to input?

  1. Decision problems: assignment of inputs to No (0) or Yes (1).
    • Classes: R, EXP, P(focus in this class)
  2. Decidablilitiy: problem is decidable if runtime of existing program is finite.
  3. Reductions: solve problem A -> by solving problem B we know how to solve