Annotaed slides for dynamic programming algorithm

Dynamic programming presentation that includes many examples such as Knapsack problem, fibonacci sequence which is a mathematical known problem

1. Algorithms Analysis & Design Dynamic Programming I Idea + Examples

2. Announcement Next Lecture will be ONLINE @Teams isA TIME: MON 16 MAY from 4:00 pm to 6:00 pm isA Midterm REMAKE: TIME: SUN 15 MAY from 2:30 pm to 3:30 pm isA LOC: Sa’ed Lec . Hall CONTENT: till Lec05 (inclusive)

3. GENERAL NOTE Hidden Slides are Extra Knowledge Not Included in Exams

4. Roadmap

5. Pre-Test In Recursive Fib(5), how many times the Fib(3) is called? What are the differences bet. Recursive & Loop solution of Fib? Idea behind spell checker? ALGORITHM1 F(n) if n≤1 return n else return F(n-1)+F(n-2) ALGORITHM2 F(n) F[0] = 0; F[1] = 1 for i = 2 to n do F[ i ] = F[i-1] + F[i-2] return F[n]

6. Agenda Dynamic Programming Paradigm Ex.1: Fibonacci Ex.2: Longest Common Subsequence Questions Idea Naïve Solution DP Solution Analysis Trace Example PART I PART II

7. Learning Outcomes For dynamic programming strategy, identify a practical example to which it would apply. Use dynamic programming to solve an appropriate problem. Determine an appropriate algorithmic approach to a problem. Examples that illustrate time-space trade-offs of algorithms Trace and/or implement a string-matching algorithm.

8. References Chapter 15 Section 15.3 (Elements of DP) Section 15.4 (Longest Common Subsequence)

9. Algorithm Design Techniques: 3

10. 10 Randomization Iterative Improvement Brute Force & Exhaustive Search Greedy Dynamic Programming Transformation Divide & Conquer Algorithm Design Techniques follow definition / try all possibilities break problem into distinct sub-problems convert problem to another one break problem into overlapping sub-problems repeatedly do what is best now use random numbers repeatedly improve current solution

11. 11 Randomization Iterative Improvement Brute Force & Exhaustive Search Greedy Dynamic Programming Transformation Divide & Conquer follow definition / try all possibilities break problem into distinct sub-problems convert problem to another one break problem into overlapping sub-problems repeatedly do what is best now use random numbers repeatedly improve current solution Algorithm Design Techniques

12. Dynamic Programming What? DP is “Careful brute-force” DP is D&C D&C solved in top-down [recursive] DP stores the previous solutions while D&C do not. . . . 1) Divide . . . 2) Conquer . . . . . . . . . . . . . . . . . . . . . 3) Combine . . . . . . . . . D&C 2 times 3 times 3 times DP 1 time 1 time 1 time 1 time 1 time 1 time 1 time 1 time 1 time 1 time with overlapped sub-problems Extra Storage P 1 P 2 … P K . . . . . . . . . . . . while DP usually solved in bottom-up [loop]

13. Dynamic Programming Why? leads to efficient solutions (usually turns exponential  polynomial) When to use? Often in optimization problems, in which there can be many possible solutions , Need to try them all . wish to find a solution with the optimal (e.g. min or max) value. How to solve? Top-down Bottom-up Save solution values Recursive Called “ memoization ” Used when NO need to solve ALL subproblems Save solution values Loop Called “building table” Used when we need to solve ALL subproblems

14. Dynamic Programming Conditions? Optimal substructure: Optimal solution to problem contains within it optimal solutions to TWO or MORE sub-problems i.e. Divide and Conquer Overlapping sub-problems Optimal Solution Optimal Sol. To Subprob.1 Optimal Sol. To Subprob.2 Optimal Sol. To Subprob.K . . . . . . . . .

15. Dynamic Programming Solution Steps: Define the problem: Characterize the structure of the optimal sol (params & return) D&C Solution: Recursively define the value of an optimal sol. Check overlapping Switch D&C to DP Solution: OPT1: top-down ( recurse ) + memoization OPT2: bottom-up (loop) + building table Extract the Solution: Construct an optimal solution from computed information . . . . . . . . . Problem Fun(…) …. …. Fun(…), Fun(…), … …. …. Fun(…) loop loop …. …. Extra Storage P 1 P 2 … P K . . . . . . . . . . . . F(N) F(N 2 ) F(N 1 ) . . . dictionary . . . N 3 N 2 N 1 . . . NIL NIL NIL . . . . . . Sol. F(N 3 ) CASE1: Not Exist Calc. & Save CASE2: Exist Retrieve

16. Dynamic Programming DETAILS OF STEP#2 ( Hint: Explain it during the examples ) D&C solution: recursively define value of solution Guess the possibilities (trials) for the current problem Formulate their subproblems Define base case Relate them in a recursive way

17. Dynamic Programming DETAILS OF STEP#4 ( Hint: Explain it during the examples ) Switch D&C to DP [ Memoization ]: Define extra storage (hash table OR array) (array dimensions = # varying parameters in the function) Initialize it by NIL Solve recursively (top-down) If not solved (NIL): solve & save If solved: retrieve Return solution of main problem Θ (??) = # subproblems × time/ subprob

18. Dynamic Programming DETAILS OF STEP#4 ( Hint: Explain it during the examples ) Switch D&C to DP [Building Table]: Define extra storage (dictionary OR array) (array dimensions = # varying parameters in the function) Equation to fill-in this table Solve iteratively (bottom-up) If base case: store it else: calculate it Return solution of main problem Θ (??) = # iterations × Θ (Body)

19. Dynamic Programming DETAILS OF STEP#5 ( Hint: Explain it during the examples ) Extract the Solution Save info about the selected choice for each subproblem Define extra array (same dim’s as solution storage) to store the best choice at each subproblem Use these info to construct the solution Backtrack the solution using the saved info starting from the solution of main problem

20. Agenda Dynamic Programming Paradigm Ex.1: Fibonacci Ex.2: Rod Cutting Questions Idea Naïve Solution DP Solution Analysis Trace Example PART I PART II

21. Dynamic Programming Ex.1: Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, … F(0)=1, F(1)=1 F(n)= F(n-1) +F(n-2) for n>1 Solution Define the problem: structure of the solution D&C solution: recursively define value of solution Fib (n) if n≤1 return 1 else return Fib(n-1)+Fib(n-2) Value = Fib (index) Fib(N) Fib(N-2) Fib(N-1)

22. Dynamic Programming Fib(N) Fib(N-1) Fib(N-2) Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-4) Fib(N-3) Fib(N-4) Fib(N-4) Fib(N-5) Fib(N-4) Fib(N-5) Bounded by: … Overlapped subproblems Top-down (Recursive) Exponential Complexity Check overlapping

23. Dynamic Programming Switch D&C to DP [ Memoization ]: Define extra storage (dictionary OR array) (array dimensions = # varying parameters in the function) Initialize it by NIL (here NIL can be 0) Solve recursively (top-down) If not solved (NIL): solve & save If solved: retrieve Return solution of main problem Fib (n) if n≤1 return 1 else return Fib(n-1)+Fib(n-2) Fib(N) Fib(N-2) Fib(N-1) . . . 1 param 1D N N-1 . . . 1 NIL NIL . . . NIL NIL . . . . . . 1 1 Fib(0) Fib(1) Fib(N) F[0…N] = 0’s //Initialize Fib (n) if F[n]≠NIL, return F[n] //Retrieve if n ≤ 1 return F[n] = 1 return F[n]=Fib(n-1) + Fib(n-2) // Memoize Θ (??) = # subproblems × time/ subprob = N × Θ (1) = Θ (N) Fib(N-1) Fib(N)

24. 24 1 1 Example of Memoized Fib NIL NIL NIL NIL F 1 2 3 4 5 2 3 5 Fib(5) Fib(4) Fib(3) Fib(2) returns F[2]= F[1]+F[0] = 1+1 = 2 F[3] = F[2] + F[1] = 2 + 1 = 3 returns F[3] F[4] = F[3] + F[2] = 3 + 2 = 5 returns F[4] F[5] = F[4] + F[3] = 5 + 3 = 8 returns F[5] NIL NIL 8 F[0…N] = 0’s //NIL Fib (n) if F[n]≠NIL, return F[n] //Retrieve if n ≤ 1 return F[n] = 1 return F[n]=Fib(n-1) + Fib(n-2) // Memoize Fib(1) returns F[1] = 1 Fib(0) returns F[0] = 1

25. CSCE 411, Spring 2013: Set 5 25 Get Rid of the Recursion Recursion adds overhead !! extra time for function calls extra space to store information on the runtime stack about each currently active function call Avoid the recursion overhead by filling in the table entries bottom up, instead of top down.

26. Dynamic Programming Switch D&C to DP [Building Table]: Define extra storage (hash table OR array) (array dimensions = # varying parameters in the function) Equation to fill-in this table Solve iteratively (bottom-up) If base case: store it else: calculate it Return solution of main problem Fib (n) if n≤1 return 1 else return Fib(n-1)+Fib(n-2) . . . 1 param 1D N . . . 2 1 1 1 F[N] Fib (n) For i =0 to n if i ≤ 1 F[ i ] = 1 else F[ i ] = F[i-1] + F[i-2] Return F[n] F[ i ] = 1 If i ≤ 1 F[i-1]+F[i-2] else 2 Θ (??) = # iterations × Θ (Body) = N × Θ (1) = Θ (N) Can perform application-specific optimizations save space by only keeping last two numbers computed F[N]

27. QUIZ1.1 Suppose we are walking up N stairs. At each step, you can go up 1 stair, 2 stairs or 3 stairs. Our goal is to compute how many different ways there are to get to the top (level N ) starting at level 0. We can ’t go down and we want to stop exactly at level N. Design an efficient DP solution to the problem, and answer the following:

28. QUIZ1.2 You are an amazing super thief. You have scoped out a line of N houses that you would like to rob tonight. However, as the super thief that you are, you've done your homework and realized that you want to avoid robbing two adjacent houses because this will minimize the chance that you get caught. You've also scouted out the hood, so for every house i , you know that the net worth you will gain from robbing that house is V[ i ]. Thus, You want to try to maximize the amount of money that you can rob.

29. BREAK

30. Agenda Dynamic Programming Paradigm Ex.1: Fibonacci Ex.2: Longest Common Subsequence Questions Idea Naïve Solution DP Solution Analysis Trace Example PART I PART II

31. Dynamic Programming Ex.2: Longest Common Subsequence (LCS) Given: two sequences x [1 . . m ] and y [1 . . n ] , Required: find a longest subsequence that’s common to both of them. Subsequence of a given sequence is the given sequence with zero or more elements left out Indices are strictly increasing x: A B C B D A B y: B D C A B A LCS(x, y) = BCBA or BCAB

32. A substrings are consecutive parts of a string, while subsequences need not be. Hence, a substring always a subsequence, but NOT vice versa Substring Vs. Subsequence

33. What’s the LCS of the following: S1 = HIEROGLYPHOLOGY S2 = MICHAEL ANGELO LCS = HELLO S1 = H I E ROG L YPHO LO GY S2 = MIC H A EL ANGE LO Longest Common Subsequence Example

34. String similarity (e.g. correction in spell checker) Machine translation DNA matching Sequence alignment Information retrieval … Longest Common Subsequence Applications

35. Subsequences have applications in  Bioinformatics , where computers are used to compare, analyze , and store  DNA  strands. Take two strands of DNA, say : ORG 1 =ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA ORG 2 =CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases:  adenine ,  guanine ,  cytosine  and  thymine . Longest Common Subsequence Applications

36. Analysis and Design of Algorithms Longest common subsequence ( LCS ): Given two sequences x[1..m] and y[1..n], find the longest subsequence which occurs in both? Brute-force algorithm: For every subsequence of x: Check if it’s a subsequence of y? If yes, maximize the length How many subsequences of x are there? What will be the running time of the brute-force alg ? Longest Common Subsequence Brute Force Solution

37. Analysis and Design of Algorithms 2 m subsequences of x, each is checked against y (size n) to find if it is a subsequence  O( n 2 m ) Exponential!! Can we do any better? Longest Common Subsequence Brute Force Solution

38. Dynamic Programming Solution Define the problem: structure of the solution Find length of longest common subsequence between 2 strings D&C solution: recursively define value of solution Guess the possibilities (trials) for the current problem Length of LCS = LCS (n, m) LCS( n,m ) … X 1 2 n … Y 1 2 m = Add 1 to LCS + Find LCS bet. X[1…n-1] & Y[1…m-1] … X 1 2 n … Y 1 2 m ≠ Select max bet. 2 options X[1:n], Y[1:m-1] X[1:n-1], Y[1:m] 2 possible choices

39. Dynamic Programming Solution Define the problem: structure of the solution Find length of longest common subsequence between 2 strings D&C solution: recursively define value of solution Guess the possibilities (trials) for the current problem Formulate their subproblems Base case? LCS( n,m ) … X 1 2 n … Y 1 2 m = Add 1 to LCS + Find LCS bet. X[1…n-1] & Y[1…m-1] … X 1 2 n … Y 1 2 m ≠ Select max bet. 2 options X[1:n], Y[1:m-1] X[1:n-1], Y[1:m] LCS (n-1, m-1) + 1 Max: LCS (n, m-1) LCS (n-1, m) LCS (0, m) = 0 LCS (n, 0) = 0

40. Dynamic Programming Solution Define the problem: structure of the solution Find length of longest common subsequence between 2 strings D&C solution: recursively define value of solution Guess the possibilities (trials) for the current problem Formulate their subproblems Base case: LCS (0, m) = 0, LCS (n, 0) = 0 Relate them in a recursive way LCS (n-1, m-1) + 1 Max: LCS (n, m-1) LCS (n-1, m) LCS ( n,m ) if n=0 OR m=0 ret if X[n] = Y[m] ret LCS (n-1, m-1) + 1 else ret max ( LCS (n, m-1) ,LCS (n-1, m)) LCS( n,m ) LCS(n,m-1) LCS(n-1,m) LCS(n-1,m-1)

41. Dynamic Programming Solution Check overlapping… LCS( n,m ) LCS(n, m-1) LCS(n-1, m) LCS(n, m-2) LCS(n-1, m-1) LCS(n-1, m-1) LCS(n-2, m) T(N) = 2 T(N-1) + Θ (1) Complexity = Θ (2 N )

42. LCS Which is better here? WHY? TOP-DOWN or BOTTOM-UP

43. Dynamic Programming Switch D&C to DP [ Memoization ] [ self-study ] Define extra storage (hash table OR array) (array dimensions = # varying parameters in the function) Initialize it by NIL (here: NIL can be -1) Solve recursively (top-down) If not solved (NIL): solve & save If solved: retrieve Return solution of main problem LCS( n,m ) LCS(n-1,m) LCS(n,m-1) … … . . . . . . . . . … … 2 params 2D 1 . . . n-1 n NIL NIL NIL NIL . . . . . . NIL NIL NIL NIL . . . . . . LCS(0,0) LCS(0,m) LCS ( n,m ) Θ (??) = # subproblems × time/ subprob = n × m × O(1) = Θ (nm) = Θ (N 2 ) LCS ( n,m ) if n=0 OR m=0 ret if X[n] = Y[m] ret LCS (n-1, m-1) + 1 else ret max ( LCS (n, m-1) ,LCS (n-1, m)) LCS ( n,m ) if R[ n,m ]!=NIL ret R[ n,m ] //retrieve if n=0 OR m=0 ret R[ n,m ] = 0 if X[n] = Y[m] R[ n,m ] = LCS (n-1,m-1) + 1 Else R[ n,m ]= Max ( LCS (n,m-1), LCS (n-1,m)) return R[ n,m ] LCS( n,m ) m

44. Dynamic Programming Switch D&C to DP [Building Table]: Define extra storage (dictionary OR array) (array dimensions = # varying parameters in the function) Equation to fill-in this table Solve iteratively (bottom-up) If base case: store it else: calculate it Return solution of main problem Θ (??) = # iterations × Θ (Body) = n × m × O(1) = Θ (nm) = Θ (N 2 ) … … . . . . . . . . . … … 2 params 2D 1 . . . n-1 n R[ n,m ] LCS ( n,m ) if n=0 OR m=0 ret if X[n] = Y[m] ret LCS (n-1, m-1) + 1 else ret max ( LCS (n, m-1) ,LCS (n-1, m)) LCS ( n,m ) for i =0 to n for j=0 to m if i =0 OR j=0, R[ i,j ] = 0 else if X[ i ] = Y[j] R[ i,j ] = R[i-1,j-1] + 1 Else R[ i,j ] = Max (R[i,j-1], R[i-1,j]) return R[ n,m ] R[ n,m ] m R[ i,j ]= 0 If i =0 OR j=0 R[i-1,j-1] +1 if x[ i ]=y[j] Max: else R[i,j-1], R[i-1,j] R[1,m]

45. Dynamic Programming Switch D&C to DP [Building Table]: Define extra storage (dictionary OR array) (array dimensions = # varying parameters in the function) Equation to fill-in this table Solve iteratively (bottom-up) If base case: store it else: calculate it Return solution of main problem Θ (??) = # iterations × Θ (Body) = n × m × O(1) = Θ (nm) = Θ (N 2 ) … … . . . . . . . . . … … 2D 1 . . . n-1 n R[ n,m ] LCS ( n,m ) for i =0 to n for j=0 to m if i =0 OR j=0, R[ i,j ] = 0 else if X[ i ] = Y[j] R[ i,j ] = R[i-1,j-1] + 1 Else R[ i,j ] = Max (R[i,j-1], R[i-1,j]) return R[ n,m ] R[ n,m ] m R[ i,j ]= 0 If i =0 OR j=0 R[i-1,j-1] +1 if x[ i ]=y[j] Max: else R[i,j-1], R[i-1,j] R[1,m] Can we switch the order of the loops? WHY?

46. Dynamic Programming Extract the Solution Save info about the selected choice for each subproblem Define extra array b[0…n,0…m] to store the best choice per subproblem Use these info to construct the solution LCS ( n,m ) for i =0 to n for j=0 to m if i =0 OR j=0, R[ i,j ] = 0 else if X[ i ] = Y[j] R[ i,j ] = R[i-1,j-1] + 1 Else R[ i,j ] = Max (R[i,j-1], R[i-1,j]) return R[ n,m ] ; b[ i,j ] = “ ↖” If R[i,j-1] > R[i-1,j] R[ i,j ] = R[i,j-1] Else R[ i,j ] = R[i-1,j] ; b[ i,j ] = “←” ; b[ i,j ] = “↑” b[0…n,0…m] COMPLEXITY?

47. LCS Trace example DYNAMIC PROGRAMMING

48. Analysis and Design of Algorithms We’ll see how LCS algorithm works on the following example: X = ABCB Y = BDCAB LCS Example LCS(X, Y) = BCB X = A B C B Y = B D C A B What is the Longest Common Subsequence of X and Y?

49. LCS Example (0) j 0 1 2 3 4 5 1 2 3 4 i Xi A B C B Yj B B A C D X = ABCB; m = |X| = 4 Y = BDCAB; n = |Y| = 5 Allocate array c[5,4] – from 0-5, from 0-4 ABCB BDCAB Analysis and Design of Algorithms R[ i,j ]= 0 If i =0 OR j=0 R[i-1,j-1] +1 if x[ i ]=y[j] Max: else R[i,j-1], R[i-1,j]

50. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 3 ABC B BDCA B LCS Example (15) j 0 1 2 3 4 5 Complete Animated Trace @ END of slides

51. Analysis and Design of Algorithms Finding LCS j 0 1 2 3 4 5 1 2 3 4 i Xi A B C Yj B B A C D 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 3 B Yj B B A C D B C B LCS (reversed order): LCS (straight order): B C B A palindrome!

52. Agenda Dynamic Programming Paradigm Ex.1: Fibonacci Ex.2: Longest Common Subsequence Questions Idea Naïve Solution DP Solution Analysis Trace Example PART I PART II

53. DP Sheet 4 solved problems 7 unsolved problems 3 online problems ( Uva ) 5 General Questions (Trace Convert D&C DP…)

54. 1 2 3 4 i Xi A B C B Yj B B A C D for i = 1 to m c[i,0] = 0 for j = 1 to n c[0,j] = 0 ABCB BDCAB LCS Example (1) j 0 1 2 3 4 5 Analysis and Design of Algorithms

55. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[ i,j ] = c[i-1,j-1] + 1 else c[ i,j ] = max( c[i-1,j], c[i,j-1] ) A BCB B DCAB LCS Example (2) j 0 1 2 3 4 5

56. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) A BCB B D CAB LCS Example (3) j 0 1 2 3 4 5

57. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) A BCB B D CAB LCS Example (4) j 0 1 2 3 4 5

58. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 A BCB BDC A B LCS Example (5) j 0 1 2 3 4 5

59. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 A BCB BDCA B LCS Example (6) j 0 1 2 3 4 5

60. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 A B CB B DCAB LCS Example (7) j 0 1 2 3 4 5

61. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 1 1 1 A B CB B DCA B LCS Example (8) j 0 1 2 3 4 5

62. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 1 1 1 2 A B CB BDCA B LCS Example (9) j 0 1 2 3 4 5

63. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 2 1 1 1 1 1 1 AB C B BD CAB LCS Example (10) j 0 1 2 3 4 5

64. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 2 1 1 1 1 1 2 AB C B BD C AB LCS Example (11) j 0 1 2 3 4 5

65. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 2 1 1 1 1 2 1 2 2 AB C B BDC AB LCS Example (12) j 0 1 2 3 4 5

66. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 2 1 1 1 1 2 1 2 2 1 ABC B B DCAB LCS Example (13) j 0 1 2 3 4 5

67. Analysis and Design of Algorithms 1 2 3 4 i Xi A B C B Yj B B A C D if ( X i == Y j ) c[i,j] = c[i-1,j-1] + 1 else c[i,j] = max( c[i-1,j], c[i,j-1] ) 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 ABC B B DCA B LCS Example (14) j 0 1 2 3 4 5