Algorithms in Spring 2025: Design & Analysis with Jianer Chen

csce 411 n.w
1 / 26
Embed
Share

Explore the world of algorithms with Jianer Chen in the Spring of 2025. Dive into topics such as dynamic programming, RadixSort, and the Longest Common Subsequence problem. Uncover the intricacies of sorting in linear time and learn how to find the longest common subsequence in sequences X and Y. Join this educational journey today!

  • Algorithms
  • Spring 2025
  • Jianer Chen
  • Dynamic Programming
  • RadixSort
rayaanacharya
lynd_200 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 10: Dynamic programming

  2. Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 2. Stable sorting is essential. 3. The elements do not have to be integers. For example, they can be character strings. 4. It can be generalized to sort integers in [0..n4-1]: Hint: each integer r in [0..n4-1] can be written as: R = c3n3 + c2n2 + c1n + c0 or (c3, c2, c1, c0) where 0 ch n - 1 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from right) \\ so 0 k 9 Running time = O(d n)

  3. Dynamic Programming

  4. Dynamic Programming Longest Common Subsequence

  5. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA

  6. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA

  7. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y.

  8. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. Observation 1. If X[n] = Y[m], then LCS(X[1..n], Y[1..m]) = LCS(X[1..n-1], Y[1..m-1]) X[n], so |LCS(X[1..n], Y[1..m])| = |LCS(X[1..n-1], Y[1..m-1])|+1. X[n] X X[1..n-1] Y Y[1..m-1] Y[m]

  9. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. Observation 1. If X[n] = Y[m], then LCS(X[1..n], Y[1..m]) = LCS(X[1..n-1], Y[1..m-1]) X[n], so |LCS(X[1..n], Y[1..m])| = |LCS(X[1..n-1], Y[1..m-1])|+1. Observation 2. If X[n] Y[m], then LCS(X[1..n], Y[1..m]) is the longer of LCS(X[1..n-1], Y[1..m]) and LCS(X[1..n], Y[1..m-1]) X[n] X X X[1..n-1] X[1..n] Y Y Y[1..m] Y[1..m-1] Y[m]

  10. Dynamic Programming Longest Common Subsequence Example. X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA Y = GTCGTTCGGAATGCCGTTGCTCTGTAAA Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. Observation 1. If X[n] = Y[m], then LCS(X[1..n], Y[1..m]) = LCS(X[1..n-1], Y[1..m-1]) X[n], so |LCS(X[1..n], Y[1..m])| = |LCS(X[1..n-1], Y[1..m-1])|+1. Observation 2. If X[n] Y[m], then LCS(X[1..n], Y[1..m]) is the longer of LCS(X[1..n-1], Y[1..m]) and LCS(X[1..n], Y[1..m-1]) LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m].

  11. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m].

  12. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2).

  13. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2). Rec-LCS(7,5) Rec-LCS(6,5) Rec-LCS(7,4) Rec-LCS(7,3) Rec-LCS(5,5) Rec-LCS(6,4) Rec-LCS(6,4) R-LCS(4,5) R-LCS(5,4) R-LCS(5,4) R-LCS(6,3) R-LCS(5,4) R-LCS(6,3) R-LCS(6,3) R-LCS(7,2)

  14. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2). Rec-LCS(7,5) Rec-LCS(6,5) Rec-LCS(7,4) Rec-LCS(7,3) Rec-LCS(5,5) Rec-LCS(6,4) Rec-LCS(6,4) R-LCS(4,5) R-LCS(5,4) R-LCS(5,4) R-LCS(6,3) R-LCS(5,4) R-LCS(6,3) R-LCS(6,3) R-LCS(7,2) Subroutines (such as R-LCS(5,4) and R-LCS(6,3)) are repeatedly called and executed, thus, taking computational time.

  15. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2). Rec-LCS(7,5) Rec-LCS(6,5) Rec-LCS(7,4) Rec-LCS(7,3) Rec-LCS(5,5) Rec-LCS(6,4) Rec-LCS(6,4) R-LCS(4,5) R-LCS(5,4) R-LCS(5,4) R-LCS(6,3) R-LCS(5,4) R-LCS(6,3) R-LCS(6,3) R-LCS(7,2) Subroutines (such as R-LCS(5,4) and R-LCS(6,3)) are repeatedly called and executed, thus, taking computational time.

  16. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2). This is the main idea of dynamic programming

  17. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Rec-LCS(i, j) \\ compute LCS for X[1..i] and Y[1..j] 1. if (i<=0 or j<=0) return(empty sequence); 2. if (X[i] == Y[j]) return(Rec-LCS(i-1, j-1) X[i]); else S1 = Rec-LCS(i-1,j); S2 = Rec-LCS(i,j-1); if (|S1| > |S2|) return(S1); else return(S2). Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1].`

  18. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 n 0 Time = O(nm)

  19. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 C[n,m] n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] Time = O(nm)

  20. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 C[n,m] n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Time = O(nm)

  21. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 C[n,m] n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Use another array B[0..n,0..m] to indicate the matching symbols in X[1..n] and Y[1..m] Time = O(nm)

  22. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; B[i,0] = ; 2. for (j=0; j<=m; j++) C[0,j] = 0; B[0,j] = ; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; B[i,j] = ; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; B[i,j] = ; else C[i,j] = C[i,j-1]; B[i,j] = . i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Use another array B[0..n,0..m] to indicate the matching symbols in X[1..n] and Y[1..m] Time = O(nm)

  23. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. Print-LCS(B[0..n,0..m]) \\ use array B[0..n,0..m] to print LCS 1. i=n; j=m; 2. while (i>0 & j>0) if (B[i,j]== ) LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. print(X[i]); i = i 1; j = j 1; else if (B[i,j]== ) i = i 1; else j = j 1. Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix B[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; B[i,0] = ; 2. for (j=0; j<=m; j++) C[0,j] = 0; B[0,j] = ; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; B[i,j] = ; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; B[i,j] = ; else C[i,j] = C[i,j-1]; B[i,j] = . i-1 0 B[i-1,j-1] B[i-1,j] 0 i i+1 B[i,j-1] 0 n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Use another array B[0..n,0..m] to indicate the matching symbols in X[1..n] and Y[1..m] Time = O(nm)

  24. Dynamic Programming \\ use array C[0..n,0..m] to print LCS 1. i=n; j=m; 2. while (i>0 & j>0) if (X[i]==Y[j]) print(X[i]); i = i 1; j = j 1; else if (C[i-1,j] == C[i,j]) i = i 1; else j = j 1. Print-LCS(C[0..n,0..m]) Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. Print-LCS(B[0..n,0..m]) \\ use array B[0..n,0..m] to print LCS 1. i=n; j=m; 2. while (i>0 & j>0) if (B[i,j]== ) LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m])) if X[n] Y[m]. print(X[i]); i = i 1; j = j 1; else if (B[i,j]== ) i = i 1; else j = j 1. 0 1 2 j-1 j j+1 m Instead, we may execute each subroutine only once and save the result. When we need the result later, we can use it directly, instead of re-running the subroutine. Matrix C[0..n,0..m] 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; B[i,0] = ; 2. for (j=0; j<=m; j++) C[0,j] = 0; B[0,j] = ; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; B[i,j] = ; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; B[i,j] = ; else C[i,j] = C[i,j-1]; B[i,j] = . i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Use another array B[0..n,0..m] to indicate the matching symbols in X[1..n] and Y[1..m] Time = O(nm)

  25. Dynamic Programming \\ use array C[0..n,0..m] to print LCS 1. i=n; j=m; 2. while (i>0 & j>0) if (X[i]==Y[j]) print(X[i]); i = i 1; j = j 1; else if (C[i-1,j] == C[i,j]) i = i 1; else j = j 1. Print-LCS(C[0..n,0..m]) Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Matrix C[0..n,0..m] 0 1 2 j-1 j j+1 m 0 1 2 0 0 0 0 0 0 0 0 0 Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. i-1 0 C[i-1,j-1] C[i-1,j] 0 i i+1 C[i,j-1] C[i,j] 0 n 0 C[n,m] gives the length of LCS(X[1..n],Y[1..m] How do we compute the actual sequence? Use another array B[0..n,0..m] to indicate the matching symbols in X[1..n] and Y[1..m] Time = O(nm)

  26. Dynamic Programming Problem LCS. Given two sequences X[1..n] and Y[1..m], find the longest common subsequence LCS(X[1..n], Y[1..m]) of X and Y. LCS(X[1..n-1], Y[1..m-1]) X[n], if X[n] = Y[m]; LCS(X[1..n], Y[1..m]) = Longer(LCS(X[1..n-1], Y[1..m]), LCS(X[1..n], Y[1..m-1])) if X[n] Y[m]. Time = O(nm) Dyn-LCS(X[1..n], Y[1..m]) \\ array C[0..n,0..m] records the length \\ of LCS(X[1..i],Y[1..j]) for all i, j. 1. for (i=0; i<=n; i++) C[i,0] = 0; 2. for (j=0; j<=m; j++) C[0,j] = 0; 3. for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (X[i]==Y[j]) C[i,j] = C[i-1,j-1]+1; else if (C[i-1,j] > C[i,j-1]) C[i,j] = C[i-1,j]; else C[i,j] = C[i,j-1]. Print-LCS(C[0..n,0..m]) \\ use array C[0..n,0..m] to print LCS 1. i=n; j=m; 2. while (i>0 & j>0) if (X[i]==Y[j]) print(X[i]); i = i 1; j = j 1; else if (C[i-1,j] == C[i,j]) i = i 1; else j = j 1. Main 1. Dyn-LCS(X[1..n], Y[1..m]); 2. Print-LCS(C[0..n,0..m]); 3. reverse the sequence of step 2 and output. Dynamic programming algorithm for Longest-Common-Subsequence

Related


N10-008 Dumps PDF: Up-to-Date and Verified Study Material

N10-008 Dumps PDF: Up-to-Date and Verified Study Material

Emma3

More Related Content