Lecture 3

Dynamic programming

When we cannot find a good Greedy Choice, the only thing we can do is to iterate all choices.

Example 1: Edit distance

Input: 2 sequences of some character set, e.g.

$S=ABCADA$ , $T=ABADC$

Goal: Computer the minimum number of insertions or deletions you could do to convert $S$ into $T$

We will call it Edit Distance(S[1...n],T[1...m]). where n and m be the length of S and T respectively.

Idea: computer difference between the sequences.

Observe: The difference we observed appears at index 3, and in this example where the sequences are short, it is obvious that it is better to delete 'C'. But for long sequence, we donot know that the later sequence looks like so it is hard to make a decision on whether to insert 'A' or delete 'C'.

Use branching algorithm:

def editDist(S,T,i,j):
    if len(S)<=i:
        return len(T)
    if len(T)<=j:
        return len(S)
    if S[i]==T[j]:
        return editDist(S,T,i+1,j+1)
    else:
        return min(editDist(S,T,i+1,j),editDist(S,T,i,j+1))

Correctness Proof Outline:

~~Greedy Choice Property~~
Complete Choice Property:
- The optimal solution makes one of the choices that we consider
Inductive Structure:
- Once you make any choice, you are left with a smaller problem of the same type. Any first choice + feasible solution to the subproblem = feasible solution to the entire problem.
Optimal Substructure:
- If we optimally solve the subproblem for a particular choice c, and combine it with c, resulting solution is the optimal solution that makes choice c.

Correctness Proof:

Claim: For any problem $P$ , the branking algorithm finds the optimal solution.

Proof: Induct on problem size

Base case: $|S|=0$ or $|T|=0$ , obvious
Inductive Case: By inductive hypothesis: Branching algorithm works for all smaller problems, either $S$ $S$ is smaller or $T$ $T$ is smaller or both
- For each choice we make, we got a strictly smaller problem: by inductive structure, and the answer is correct by inductive hypothesis.
- By Optimal substructure, we know for any choice, the solution of branching algorithm for subproblem and the choice we make is an optimal solution for that problem.
- Using Complete choice property, we considered all the choices.

Using tree graph, the left and right part of the tree has height n, but the middle part of the tree has height 2n. So the running time is $\Omega(2^n)$ , at least $2^n$ .

How could we reduce the complexity?

There are overlapping subproblems that we compute more than once! Number of distinct subproblems is polynomial, we can share the solution that we have already computed!

store the result of subprolem in 2D array

Use dp:

def editDist(S,T,i,j):
    m,n=len(S),len(T)
    dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(n):
        dp[i][m]=n-i
    for i in range(m):
        dp[n][j]=m-i
    for i in range(m):
        for j in range(n):
            if S[i]==T[j]:
                dp[i][j]=dp[i+1][j+1]
            else:
                # assuming the cost of insertion and deletion is 1
                dp[i][j]=min(1+dp[i][j+1],1+dp[i+1][j])

We can use backtracking to find out how do we reach our final answer. Then the new runtime will be the time used to complete the table, which is $T(n,m)=\Theta(mn)$

Example 2: Weighted Interval Scheduling (IS)

Input: $P=\{p_1,p_2,...,p_n\}$ , $p_i=\{s_i,f_i,w_i\}$ $s_i$ is the start time, $f_i$ is the finish time, $w_i$ is the weight of the task for job $i$

Goal: Pick a set of non-overlapping intervals $\Pi$ such that $\sum_{p_i\in \Pi} w_i$ is maximized.

Trivial solution ( $T(n)=O(2^n)$ )

# p=[[s_i,f_i,w_i],...]
p=[]
p.sort()
n=len(p)
def intervalScheduling(idx):
    res=0
    if i>=n:
        return res
    for i in range(idx,n):
        # pick when end
        if p[idx][1]>p[i][0]:
            continue
        res=max(intervalScheduling(i+1)+p[i][2],res)
return intervalScheduling(0)

Using dp ( $T(n)=O(n^2)$ )

def intervalScheduling(p):
    p.sort()
    n=len(p)
    dp=[0]*(n+1)
    for i in range(n-1,-1,-1):
        # load initial best case: do nothing
        dp[i]=dp[i+1]
        _,e,w=p[i]
        for j in range(bisect.bisect_left(p,e,key=lambda x:x[0]),n+1):
            dp[i]=max(dp[i],w+dp[j])
    return dp[0]

Example 3: Subset sums

Input: a set $S$ of positive and unique integers and another integer $K$ .

Problem: Is there a subset $X\subseteq S$ such that $sum(X)=K$

Brute force takes $O(2^n)$ .

def subsetSum(arr,i,k)->bool:
    if i>=len(arr): 
        if k==0:
            return True
        return False
    return subsetSum(i+1,k-arr[i]) or subsetSum(i+1,k)

Using dp $O(nk)$

def subsetSum(arr,k)->bool:
    n=len(arr)
    dp=[False]*(k+1)
    dp[0]=True
    for e in arr:
        ndp=[]
        for i in range(k+1):
            ndp.append(dp[i])
            if i-e>=0:
                ndp[i]|=dp[i-e]
        dp=ndp
    return dp[-1]

Cse347 L2 Cse347 L4