Sir's On Dynamic Programming

Two Paradigms:1 Divide and Conquer VS Dynamic Programming • D-C uses a top-down strategy: – Split the original problem into small subproblems; – Solve each subproblem independently; – Merge the subproblems’ solutions to obtain a solution of the original. • Many algorithms in sorting and binary search are based on divide and conquer • DP uses a bottom-up strategy: – Define a generalized form of the problem; – Define an ordering on these problems such that a problem can be solved using solutions to ones before it in the sequence; – The first few problems should be trial to solve; – Solve the problems in order and use a table to store all the solutions to previously solved problems and the original problem.

Two Paradigms:2

Divide and Conquer

Dynamic Programming

The airplane problem

Problem:Given a country with n+1 cities,numbered from 0 to n and equally spaced along a line. Suppose you are in city 0 and want to get to n. Few rules are as follows: 1. You can only travel by plane. 2. You can only take one flight per day. The fare is determined by the distance Air cost[i]. 3. Staying one night in a city costs:Hotel cost[i]. Goal: Minimize the cost to get to city n. Ignore the time it takes.

We further assume that the hotel cost Hotel cost[i] is nonnegative for all i and the fair function Air cost[i] is increasing with respect to i. The solution is trivial if the cost function is linear.

Airplane problem A divide and conquer solution

Function mincost(i) Input:

Functions Air cost[i] and Hotel cost[i];

Output: The minimal cost mincost(n); begin If i=0 then Return (0); else

Return( min Air cost(i − k) 0≤k≤i−1

+mincost(k) + Hotel cost(k)); end Analysis: T (n) :=

n−1 X

T (i) + Θ(n);

i=0

From this we can conclude T (n) = 2T (n − 1) + Θ(1),

∀n ≥ 2.

This indicates that the complexity of the algorithm is O (2n )!

Airplane Problem A Dynamic programming Approach

Function M incost(i) Input:

Functions Air cost[i] and Hotel cost[i];

Output: The minimal cost M incost(n); begin Mincost[0]:=0; For i = 1 to n do M incost[i] :=

min Air cost(i − k) + M incost(k)

0≤k≤i−1

+Hotel cost(k);

end


The complexity of the algorithm is O n2 ! Example: i

Hotel cost(1)

1

2

2

2

3

5

i

Air cost(i)

1

1

2

4

3

9

4

16

Final solution: 0 → 2 → 3 → 4?

Critical Paths Problem: Given a job including several tasks, each requires a certain execute time. Each task has a set of prerequisites, which must be completed before it. This can be represented by a directed acyclic graph (DAG). The problem is to find the cost of critical path,i.e., the path from the start node to the final node with maximal cost. t1=5 t3=3 t5=5 t0 t4=3 t2=11

t7=1

t6=6

End

Directed Acyclic Graph

DP approach for DAG Assume the DAG is stored as follows: 1. Nodes are in order, i.e., i is a predececessor of j if i < j. The start node is 0, the final node n. 2. Cost[i], the execute time of task i. 3. Edge[i, j] = 1 if there is an edge from i to j, and 0 if not. To find the max. path from 1 to n, we define maxpath(i) := cost[i] +

max Edge[j,i]=1

{maxpath[j]}.

Exercise: Find the critical path in the DAG. t1=5 t3=3 t5=5 t0 t4=3 t2=11

t7=1

t6=6

End

Final Critical Path?

Optimal Binary Search Tree Problem: Given n keys {1, . . . n} with the key i having the probability pi of being accessed. Find a binary search tree such that the expected cost of accessing all the keys is minimized. Definition: The expected cost of a tree is n X

pi ∗ depth(i).

i=1

Here the depth of a node equals to 1 adding the distance from the root to this node. Example: p(a)=.1,p(b)=.2,p(c)=.3,p(d)=.4. c

a

d

b

The total expected cost is 1.9!

Defining The Cost Function:1 Question: How to define the cost function recursively? Let c(i, j) be the minimum cost tree consisting of nodes i, . . . , j. To calculate c(i, j), we must find the best choice for the root. We assume the root is k for some i ≤ k ≤ j and there are two subtrees consisting of the set of nodes {i, . . . , k − 1} and {k + 1, . . . , j} respectively. By the choice of the optimal tree, these two subtrees are both the optimal trees for the given sets of nodes. Note that the cost for these two subtrees can be denoted by c(i, k − 1) and c(k + 1, j). Assume a tree T with two subtrees TL, TR . Then cost(T ) = cost(i, j) =

j X

pl ∗ depthT (l),

l=i

cost(TL) =

k−1 X

pl ∗ depthTL (l).

l=i

Similarly we can define cost(TR ).

Defining The Cost Function:2 By direct calculus, we have depthT (l)

= depthTL (l) + 1 if i ≤ l ≤ k − 1;

depthT (l)

= depthTR (l) + 1 if k + 1 ≤ l ≤ j. Pj

Let w(i, j) = l=i pl , one can define the cost function c(i, j) via the following procedure: Function cost(i, j) Input:

Probalities p(i);

Output: The optimal tree and cost(1, n); begin Compute the matrix W ; For i := 1 to n + 1 do c(i, i − 1) := 0; While “sequencing thru (i,j) pairs” do c(i, j) := min c(i, k−1)+c(k+1, j)+w(i, j); i≤k≤j

end

Computing c(i, j): Solution 1 Function cost(i, j) Input:

Probalities p(i);

Output: The optimal tree and cost(1, n); begin For i := 1 to n do w(i, i) := p(i); For j := i + 1 to n do w(i, j) := w(i, j − 1) + p(j); End-for For j := 1 to n do For i := j down to 1 do c(i, j) = min c(i, k−1)+c(k+1, j)+w(i, j); i≤k≤j

End-for end

Possible orders in the computation of c(i, j): 1

3

6

10

2

5

9

4

8

7

8

9

10

6

5

4

3

2

7 Solution 1

1 Incorrect

1

5

8

10

2

6

9

3

7 4

Solution 2

Solution 2 Function cost(i, j) Input:

Probalities p(i);

Output: The optimal tree and cost(1, n); begin For i := 1 to n do w(i, i) := p(i); For j := i + 1 to n do w(i, j) := w(i, j − 1) + p(j); End-for For s := 1 to n do For i := 1 to n − s + 1 do j := i + s − 1; k := arg min c(i, k − 1) + c(k + 1, j); i≤k≤j

c(i, j) := c(i, k−1)+c(k+1, j)+w(i, j); r(i, j) = k; End-for End-for end Note the matrix R = [r(i, j)] contains the roots of all the optimal subtrees consisting of the set of nodes {i, . . . , j}. Complexity: The inner loop takes time Θ(n). It is executed Θ(n2) times. Therefore, in total Θ(n3 ).

Example: Steps 1 and 2 Node

A

B

C

D

prob ∗ 10

1

4

2

3

Consider

The first step is trivial.

A B

9

6 B

A

B

C

12

8

C

B

C

D 8 7

C D

Size=2, fat font indicates the root.

Example:Step 3 A

C

B

B

B A

15

10

C

C

13 A

Case for {A,B,C}

D B

C B

D 16

C

B 16

D

Case for {B,C,D}

Size=3, fat font indicates the root.

17 C

Final Solution A

B C A B

D

18

D

26

C

D

C D B B

C 19 A

A

Size=4, fat font indicates the root.

20

Product of Matrices Problem: Given a set of matrices. We want to compute the product M = M1 × M2 . . . × Mn , where the matrix Mi is an ri−1 × ri matrix. The task is to find the optimal order to compute M . The difference of the number of operations using different orders is huge. For instance, consider the problem M = M10,20 × M20,50 × M50,1 × M1,100 . Evaluating M1 × (M2 × (M3 × M4)) requires 125000 operations while (M1 × (M2 × M3 )) × M4 needs only 2200 operations! Let us denote mij the minimum cost of computing the product Mi × Mi+1 . . . × Mj . If i = j then mij = 0. Otherwise we need to compare all the possible order mij = min {mik + mk+1,j + ri−1 · rk · rj }. i≤k≤j

The algorithm The algorithm Input:

A set of matrices Mi;

Output: The optimal order of computing Qn i=1 Mi; begin For i := 1 to n do mii = 0; For l := 1 to n − 1 do For i := 1 to n − l do j := i + l; mij := mini≤k≤j {mik +mk+1,j + ri−1 · rk · rj }; End-for End-for Return m1n. end

All shortest path k Problem: For a given graph G = (V, E), define Cij the length of shortest path from vertex i to j which passes through no vertex higher than k. The graph might have edges with negative values, but no negative cycles. k = min{C k−1 , C k−1 + C k−1 }. We have Cij ij ik kj

Floyd-Warshall Algorithm Input:

A matrix of distance L = [L(i, j)];

Output:

n ]; The matrix of shortest path C = [Cij

begin For 1 ≤ i, j ≤ n do 0 = L(i, j); Cij End-for For k := 1 to n do For 1 ≤ i, j ≤ n do k := min{C k−1 , C k−1 + C k−1 }; Cij ij ik kj End-for End-for end The total complexity of the algorithm is Θ(n3 ). Compare Floyd-Warshall algorithm with Dijkstra’s algorithm.

Asymptotically the same complexity as n

calls to Dijkstra’s method, but Floyd-Warshall algorithm works practically better!

Approximate String Matching String matching is a key task in text processing. What will happen if there exist typos in the text and pattern? Let k be a nonnegative integer. A k-approximate match is a match of P in T that has at most k differences of the following three types:

(1) The corresponding characters in P and T are different—substitution. (2) P is missing a character that appears in T —deletion that in T . (3) T is missing a character in P —insertion.

The problem looks to be very complicated. What information we would like to have for the final decision? We would like to change as less as possible!

Defining the cost function Let D(i, j) be the minimum differences between the substring P1 . . . Pi and the segment of T ending at j, T1 . . . Tj . D(i, j) is the minimum of the three possible ways to extend smaller strings:

(1) If Pi = Tj , then D(i − 1, j − 1), else D(i − 1, j − 1) + 1. This means we either match or substitute the last characters. (2) D(i−1, j)+1. This means that there is an extra character in the pattern to account for, so we do not advance the text pointer and do an insertion. (3) D(i, j − 1) + 1. This means that there is an extra character in the text to remove, so we do not advance the pattern pointer and do deletion.

Approximate String Matching Initialization: • D(i, 0) = i; • D(0, i) = i if we consider possible deletions; • D(0, i) = 0 if only the occurrence of the pattern in the text is required. The algorithm can be described as follows. EditDistance (P,T) Input:

A pattern P and text T ;

Output: The min. dif. D(m, n) between P and T ; begin For i = 1 to n do D(i, 0) := D(0, i) := i; End-for For i := 1 to n do For j := 1 to n do D(i, j) := min{D(i−1, j −1)+f (Ti , Pj ), D(i−1, j)+1, D(i, j−1)+1}; End-for end Here the function f (Ti , Pj ) = 0 if Ti = Pj , otherwise f = 1.

Example Consider two strings: P=”bcdeffghix”, T=”abcdefghij”, b

c

d

e

f

f

g

h

i

x

0

1

2

3

4

5

6

7

8

9

10

a

1

1

2

3

4

5

6

7

8

9

10

b

2

1

2

3

4

5

6

7

8

9

10

c

3

2

1

2

3

4

5

6

7

8

9

d

4

3

2

1

2

3

4

5

6

7

8

e

5

4

3

2

1

2

3

4

5

6

7

f

6

5

4

3

2

1

2

3

4

5

6

g

7

6

5

4

3

2

2

2

3

4

5

h

8

7

6

5

4

3

3

3

2

3

4

i

9

8

7

6

5

4

4

4

3

2

3

j

10

9

8

7

6

5

5

5

4

3

3

Traveling salesman:Revisit Problem: to find the minimum cost cycle in a directed graph. L(i, j) denote the length from i to j. For this kind of problems, greedy algorithm might fail to find the optimal solution. Let G = (V, E) with V = {1, . . . , n}. be the length of the shortest path from i to 1 that passes exactly once through in S ⊂ {2, . . . , n}. The optimal solution g(1, {2, . . . , n}).

Let g(i, S) the vertex each node should be

Some relations are as follows: g(1, {2, . . . , n}) = min {L(1, j) + g(j, {2, . . . , n} − {j})}. 2≤j≤n

We can specify g(i, ⊘) = L(i, 1), i = 2, . . . , n. For i 6∈ S and S 6= ⊘, we have g(i, S) := min{L(i, j) + g(j, S − {j})}. j∈S

The time complexity is Θ(n2 2n)! count all the possibilities.

But better than